[数据结构与算法]Python实现：P1720 月落乌啼算钱（斐波那契数列）

题目

源代码

#法1：公式代入
n = int(input())
g = 5 ** 0.5
f = (((1 + g) / 2) ** n - ((1 - g) / 2) ** n) / g
print('%0.2f' % f)

#法2：斐波那契数列法
n = int(input())
a = b = 1
for i in range(1, n):
    c = a + b
    a = b
    b = c
if n != 0:
    print("%.2f" % a)
else:
    print("%.2f" % 0.00)

解题思路

1）公式代入：根据手写公式依次代入数进行运算，其中5的平方根等于五的0.5次方，可以求出根号5的大小，在Python中**是乘方，代入公式即可求出代数式的值。

2）利用斐波那契数列特性进行递归求解：根据观察该表达式是斐波那契数列求和表达式，因此可以使用递归方式进行计算第N项的和。

格式化输出指定小数位数

%m.nf

m表示最小宽度，n为小数精度，m可以省略，但.不可省略