태터데스크 관리자

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

태터데스크 메시지

저장하였습니다.

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

Tech 2007. 11. 2. 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
  1. Favicon of http://etnalry.tistory.com etnalry 2007.11.04 17:27 신고 Modify/Delete Reply

    return (ll) ((t + 0.5) / sqrt(5)); ==> return (ll) (t / sqrt(5) + 0.5);
    이렇게 해보면?

  2. Favicon of http://deisys.net deisys 2007.11.04 20:57 Modify/Delete Reply

    얼라? 그러게... 왜 저게 안에 있었지? (;;; 나 바보 ?)

    근데 그렇게 바꿔도 72에서 오차 생기기 시작하는건 같군. ㅎㅎ

  3. Favicon of http://waityet.tistory.com waityet 2008.03.07 22:52 Modify/Delete Reply

    심심해서 둘러보다가.
    피보나치라..중3때인가. 난데없이 선형대수책을 들고와서 일반항을 구하는 짓을
    누군가가 해줬던거 같은데.. 대체 왜 그랬는지는 기억이 없지만.
    수학적으로 equivalent한 것들에 대한 새로운 경험이었던 것으로 기억됨.

Write a comment