피보나치 수열은 위키피디아에 보면 다음과 같이 정의되어 있습니다.
그럼 이 수열을 파이썬에서 구현하면 어떻게 될까요?
다음과 같이 재귀함수를 이용해서 구현할 수 있습니다.
또한 아래와 같이 generator를 이용할 수도 있습니다.
결과출력.
피보나치 수가 처음 언급된 문헌은 기원전 5세기 인도의 수학자 핑갈라가 쓴 책이다. 한편 유럽에서 피보나치 수를 처음 연구한 것은 레오나르도 피보나치로 토끼 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다. n 번째 달의 토끼 수는
* 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
* 두 달 이상이 된 토끼는 번식 가능하다.
* 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
* 토끼는 절대 죽지 않는다.
이때 n번째 달에 a 쌍의 토끼가 있었고, 다음 n+1 번째 달에는 새로 태어난 토끼를 포함해 b 쌍이 있었다고 하자. 그러면 그다음 n+2 번째 달에는 a+b 쌍의 토끼가 있다.
그럼 이 수열을 파이썬에서 구현하면 어떻게 될까요?
다음과 같이 재귀함수를 이용해서 구현할 수 있습니다.
>>> def Fibonacci(n):
if n<2: return n
else: return Fibonacci(n-1)+Fibonacci(n-2)
if n<2: return n
else: return Fibonacci(n-1)+Fibonacci(n-2)
또한 아래와 같이 generator를 이용할 수도 있습니다.
>>> def Fibonacci():
a,b=1,1
while 1:
yield a
a,b=b,a+b
a,b=1,1
while 1:
yield a
a,b=b,a+b
결과출력.
>>> for i,ret in enumerate(Fibonacci()):
if i<20: print(i,ret)
else: break
0 1
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
if i<20: print(i,ret)
else: break
0 1
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
