斐波那契数之和

Question

我在这里找到这个任务 这里。

给定第 i 个（1<=i<=35）斐波那契数 F(i)，计算从第 i 个到第 i+9 个的和，也就是 F(i)+F(i+1)+...+F(i+9)，以及第 i+246 个的最后一位数字 F(i+246)。

我一直在尝试用 Python 和一些技巧（比如比内特公式和一个巧妙的递推）来解决这个问题：

 f=lambda n:((1+5**.5)**n-(1-5**.5)**n)/(2**n*5**.5)
 exec"n=input();print int(55*f(n)+88*f(n+1)+f(n+6)%10);"*input()

但是我还没能把我的代码压缩到给定的源代码限制111，而我的代码是115，有什么建议可以改进我的解决方案吗？

我对 Python 还是个新手，所以任何能让我成功解决问题的帮助都非常感谢。

谢谢，

Answer 1

这里是110的解决方案，不过我重新写了公式，并且用了@Gareth的建议：

p=5**.5
f=lambda n:((1+p)**n-(1-p)**n)/(2**n*p)
exec "n=input();print int(f(n+11)-f(n+1)+f(n+6)%10);"*input()

现在又节省了一个符号，总共109个符号（通过对n进行操作，去掉了+11）：

p=5**.5
f=lambda n:((1+p)**n-(1-p)**n)/(2**n*p)
exec "n=input()+6;print int(f(n+5)-f(n-5)+f(n)%10);"*input()

编辑：新的计算特定数字的方法，节省了另外4个符号，并且可以避免使用int()：

def f(n):exec"a=b=1;"+"a,b=b,a+b;"*(n-1);return a
exec "n=input()+6;print f(n+5)-f(n-5)+f(n)%10;"*input()

Answer 2

你试过用这个求和公式吗？

http://en.wikipedia.org/wiki/Fibonacci_number#Second_identity（“第二个恒等式”）？

Answer 3

这里有一段代码：f = lambda n,t=5**.5:((1+t)**n-(1-t)**n)/(2**n*t)。这段代码用8个字符定义了一个变量t=5**.5，但通过这个变量可以节省12个字符，因为5**.5出现了三次，所以用t来代替它。这样一来，总共节省了4个字符，这正是你需要的。

[编辑：我修正了一个错误；之前我在分母里写成了2*n，其实应该是2**n。]

如果你想再节省一些字符，可以用另一种方式来写Binet公式：f=lambda n:round((1+5**.5)**n/5**.5/2**n)。