태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

Fib(n) = Fib(n-1) + Fib(n-2), Fib(1) = Fib(2) = 1

Tech 2007.11.02 23:26
재귀호출이나 반복문의 예제로 자주 나오는 피보나치 수열. 이렇게 구할 수도 있다. 음, recursion tree의 terminal node를 세면(그럴싸한 방법이지?) fib(n) = pi^n / sqrt(5) 에 가장 근접한 정수, pi = (1+sqrt(5))/2  와 같은 식을 얻을 수 있다(고 한다). 이걸 보니 정말? 이라는 생각이 들어 C로 만들어 봤다... sqrt 함수를 직접 만들어 썼더니 fib(63) 에서 1의 오차가 생겼고, sqrt 를 math.h 에서 가져다 썼더니 fib(72) 에서 1의 오차가 생기기 시작... 대략 잘 맞는다. 신기하구먼 ㅎㅎㅎ

#include <stdio.h>
#include <math.h>

typedef long long ll;

ll fibo(int n) {
        double pi = 0.5*(1.0 + sqrt(5));
        double t = 1.0;
        int i;

        for (i = 0; i < n; i++)
                t *= pi;

        return (ll)((t + 0.5)/sqrt(5));
}

int main(int argc, char ** argv) {
        int n = atoi(argv[1]);

        printf("%llu\n", fibo(n));

        return 0;
}

이나이 되도록 이런것도 모르고... 공부좀 더 해야겠다. ㅠ_ㅠ

'Tech' 카테고리의 다른 글

하둡의 퍼포먼스 (삽질기)  (7) 2007.11.09
Fibo2 ...  (3) 2007.11.05
Fib(n) = Fib(n-1) + Fib(n-2), Fib(1) = Fib(2) = 1  (4) 2007.11.02
Nutch Crawler, briefly  (1) 2007.10.31
String matching  (3) 2007.10.31
SSH Key distribution  (2) 2007.10.24
tags : ,
Trackbacks 0 : Comments 4