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 := 一个大小为2*n+2的新列表，初始化为0
    • temp_arr[0] := 0
    • temp_arr[1] := c
    • arr2 := 一个新列表
    • 对于范围从2到2 * n+2的i，执行：
      • temp_arr[i] := (temp_arr[i - 1] + temp_arr[i - 2]) mod m
    • 对于范围从2到2 * n-2，步长为2的i，执行：
      • 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

更新于：2021年10月20日

121 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告