用Python编程佩尔数列pell数列循环结构

Question

佩尔数列是一个整数数列。它的第一项为0，第二项为1，第3项是第2项的2倍再加上第1项，第4项是第3项的2倍再加上第2项，……。最初几个佩尔数是：0,1,2,5,12,29,70,169, 408, 985, 2378……。
请编写程序从键盘输入整数n，求出佩尔数列第n项。

Answer 1

可以使用递归的方法写一个pell函数，看起来很简洁，但效率很低，因为是非线性递归，大概连pell(50)都算不出来（千万不要尝试）。

>>> def pell(n):
    if n == 1 or n == 2:
        return n-1
    else:
        return 2*pell(n-1) + pell(n-2)

    
>>> def test():
    while True:
        n = input('请输入一个正整数，直接回车则退出：').strip()
        if n:
            print(pell(int(n)))
        else:
            print('Bye')
            break

        
>>> test()
请输入一个正整数，直接回车则退出：5
12
请输入一个正整数，直接回车则退出：6
29
请输入一个正整数，直接回车则退出：7
70
请输入一个正整数，直接回车则退出：8
169
请输入一个正整数，直接回车则退出：15
80782
请输入一个正整数，直接回车则退出：
Bye

用循环的方式，虽然麻烦，但效率要高很多。

>>> def pell(n):
    if n == 1 or n == 2:
        return n-1
    pre = [0, 1]
    for i in range(2, n):
        pre = [pre[1], 2*pre[1]+pre[0]]
    return pre[-1]

>>> test()
请输入一个正整数，直接回车则退出：8
169
请输入一个正整数，直接回车则退出：15
80782
请输入一个正整数，直接回车则退出：50
2015874949414289041
请输入一个正整数，直接回车则退出：500
35770251205239459058076978435454985387873104128075398558406456207924399347082619617800934850824773906764543436814644745942616003093485810768803240499620489953405811359584564548662057576598709
请输入一个正整数，直接回车则退出：
Bye