3. 피보나치 수열

   #include<stdio.h> #define COUNT 40 // about 47~ more scope than Int  int main() { 	int num[COUNT]; 	int i; 	 	num[0] = num[1] = 1; 	 	for(i = 1; i < COUNT; i++) 	{ 		num[i+1] = num[i] + num[i-1]; 		printf("%d ", num[i-1]); 	} 	printf("%d", num[COUNT-1]); 	 	return 0; }

피보나치 수열이 이렇게 빨리 늘어나는지 새삼스레 깨달았당.

재귀를 사용한 피보나치

Python version

full_count = 0

def fibo(num) :
    global full_count
    full_count += 1

    if num <= 1 :
        return 1
    else :
        return fibo(num-1) + fibo(num-2)

if __name__ == "__main__" :
    print(fibo(40))

    # for i in range(20) :
    #     print(fibo(i))

    print("full_count :: {}".format(full_count))

미친 듯이 불러댄다. 이러니 지수시간이 나오지

165580141
full_count :: 331160281

 

선형재귀를 사용한 피보나치

Python version

full_count = 0

def fibo(num) :
    global full_count
    full_count += 1

    if num <= 1 :
        return (num, 0)
    else :
        (i, j) = fibo(num-1)
        return (i + j, i)

if __name__ == "__main__" :
    # print(fibo(40))

    for i in range(40) :
        print('{}번째 fibo :: {}'.format(i, fibo(i)[0]))

    print("full_count :: {}".format(full_count))

0번째 fibo :: 0
1번째 fibo :: 1
2번째 fibo :: 1
3번째 fibo :: 2
4번째 fibo :: 3
5번째 fibo :: 5
6번째 fibo :: 8
7번째 fibo :: 13
8번째 fibo :: 21
9번째 fibo :: 34
10번째 fibo :: 55
11번째 fibo :: 89
12번째 fibo :: 144
13번째 fibo :: 233
14번째 fibo :: 377
15번째 fibo :: 610
16번째 fibo :: 987
17번째 fibo :: 1597
18번째 fibo :: 2584
19번째 fibo :: 4181
20번째 fibo :: 6765
21번째 fibo :: 10946
22번째 fibo :: 17711
23번째 fibo :: 28657
24번째 fibo :: 46368
25번째 fibo :: 75025
26번째 fibo :: 121393
27번째 fibo :: 196418
28번째 fibo :: 317811
29번째 fibo :: 514229
30번째 fibo :: 832040
31번째 fibo :: 1346269
32번째 fibo :: 2178309
33번째 fibo :: 3524578
34번째 fibo :: 5702887
35번째 fibo :: 9227465
36번째 fibo :: 14930352
37번째 fibo :: 24157817
38번째 fibo :: 39088169
39번째 fibo :: 63245986
full_count :: 781

full_count가 말도 안되게 줄었음. 심지어 저건 1~39까지의 합인데도

사실 이 두번째 방법은 재귀를 사용하면서도 첫번째 C코드처럼 동적 계획법을 적용한 셈이 되었다.