在Python中找出由无限序列生成的向量的数量积

在Python中找出由无限序列生成的向量的数量积

假设我们有三个整数c、m和n。我们必须生成一个无限序列,其中第一个值为0,第二个值为c,从第三个值起等于ki = (ki-2 + ki-1) mod m。我们必须生成序列中的所有值,直到k2n+1项。现在,从序列中的值中,我们将两个连续的值作为二维向量的x和y坐标,并生成n个向量。要注意的是,我们使用序列中的值从第三个值开始。还有另一组S,其中每个值都是向量i和向量j的数量积,其中1 <= i,j <= n且i!= j。我们必须找出集合S中不同余数的数量。如果值非常大,我们会将其模m。

因此,如果输入为5、6、4,则输出为3

生成的序列是:[0, 5, 5, 4, 3, 1, 4, 5, 3, 2]。

向量是:(5, 4),(3, 1),(4, 5),(3, 2)。

从向量的数量积中,集合S中的模6余数只有三个。

因此,结果为3 mod 6 = 3。

要解决这个问题,我们将按照以下步骤进行处理 −

  • 如果n与1相同,则
    • 返回0
  • 否则,
    • temp_arr:用0进行初始化的一个大小为2*n+2的新列表
    • temp_arr[0]:0
    • temp_arr[1]:c
    • arr2:一个新列表
    • 对于i在range(2, 2 * n+2)中,
      • temp_arr[i]:(temp_arr[i – 1] + temp_arr[i – 2]) mod m
    • 对于i在range(2, 2 * n-2)中,每次增加2,
      • temp:(temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) mod m
      • 将temp插入arr2的末尾
      • temp:(temp_arr[i] * temp_arr[i + 4] + temp_arr[i + 1] * temp_arr[i + 5]) mod m
      • 将temp插入arr2的末尾
    • temp:(temp_arr[2 * n-2] * temp_arr[2 * n] + temp_arr[2 * n-1] * temp_arr[2 * n+1]) mod m
    • 将temp插入arr2的末尾
    • 从arr2中删除重复项
    • 返回arr2的大小

示例

让我们看下面的实现以获得更好的理解 −

def solve(c, m, n):
   if (n == 1):
      return 0
   else:
      temp_arr=[0 for i in range(2 * n+2)]
      temp_arr[0] = 0
      temp_arr[1] = c
      arr2 = []
      for i in range(2, 2 * n+2):
         temp_arr[i] = (temp_arr[i - 1] + temp_arr[i - 2]) % m
      for i in range(2, 2 * n-2, 2):
         temp = (temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) % m
         arr2.append(temp)
         temp = (temp_arr[i] * temp_arr[i+4] + temp_arr[i+1] * temp_arr[i+5]) % m
         arr2.append(temp)
      temp = (temp_arr[2 * n-2] * temp_arr[2 * n] + temp_arr[2 * n- 1] * temp_arr[2 * n+1]) % m
      arr2.append(temp)
      arr2 = set(arr2)
      return len(arr2)

print(solve(5, 6, 4))

输入

5, 6, 4

输出

3

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程