Fibonacci array (斐波那契数列)的编程实现
golden section/ratio 黄金分割/比 : 0.618
$A_n = A_{n-1} + A_{n-2} $
$limlimits_{nto infty} frac{A_{n-1}}{A_n}=frac{sqrt{5}-1}{2} $
$ begin{eqnarray}F(n)= begin{cases} 1, &n=1 cr 1, &n=2 cr F(n-1)+F(n-2), &n>2 end{cases}end{eqnarray} $
利用迭代和递归两种算法来求出n = 20 时，F(n)=?
Iteration :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def Fibonacci(n):
n1 = 1
n2 = 1
n3 = 1
if n < 1:
print('输入有误!')
return -1
while n > 2:
n3 = n2 + n1
n1 = n2
n2 = n3
n -= 1
return n3
number = int(input('Please input an interger:'))
result = Fibonacci(number)
print("n=%d时斐波那契数列值为：%d" % (number, result))
|
Recursion(divide and conquer algorithm) :
1
2
3
4
5
6
7
8
9
10
11
12
|
def Fibonacci(n):
if n < 1:
print('输入有误!')
return -1
elif n == 1 or n==2:
return 1
else:
return Fibonacci(n-1) + Fibonacci(n-2)
number = int(input('Please input an interger:'))
result = Fibonacci(number)
print("n=%d时斐波那契数列值为：%d" % (number, result))
|
近期评论