数列

[编程题]数列

热度指数：10951 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

某种特殊的数列a1, a2, a3, ...的定义如下：a1 = 1, a2 = 2, ... , a_n = 2 * a_{n − 1} + a_{n - 2} (n > 2)。

给出任意一个正整数k，求该数列的第k项模以32767的结果是多少？

输入描述:

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k < 1000000)。

输出描述:

n行，每行输出对应一个输入。输出应是一个非负整数。

示例1

输入

2
1
8

输出

1
408

算法知识视频讲解

Python

Re:煙花ゼロから易冷

n = int(input())
in_list = [1, 2]
for i in range(n):
    x = int(input())
    while len(in_list) < x:
        in_list.append((2*in_list[-1] + in_list[-2]) % 32767)
    print(in_list[x-1])

发表于 2019-03-15 21:11:29 回复(0)

Python

华科平凡

python解法

res = [1, 2]

for i in range(int(input())):
    k = int(input())  # 数列的第k项
    while len(res) < k:
        res.append(2 * res[-1] + res[-2])
    print(res[k - 1] % 32767)

运行时间：910ms

可以将模运算放在循环体中：

res = [1, 2]

for i in range(int(input())):
    k = int(input())  # 数列的第k项
    while len(res) < k:
        res.append((2 * res[-1] + res[-2])% 32767)
    print(res[k - 1] )

运行时间：367ms

发表于 2019-02-24 14:15:21 回复(0)