Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 3월 9일 금요일

[Project Euler] 25. 피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?

25. 피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?
피보나치 수열은 아래와 같은 점화식으로 정의됩니다.

Fn = Fn-1 + Fn-2  (단, F1 = 1, F2 = 1).
이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
수열의 값은 F12에서 처음으로 3자리가 됩니다.

피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까?

Click
정확한 수는 알 필요 없으므로 10의 자리가 넘을때마다 10으로 나눠주는 대신 자릿수를 1씩 증가시켜주며 자릿수를 계산.
<script>
function p025(limit){
    var fib = new Array(1,1);
    
    var n = 2;
    var digit = 1;
    while(digit < limit){
        n++;
        fib[n%2] = piv[0] + piv[1];
        if(piv[n%2]>10){
            digit ++;
            fib[0] /= 10;
            fib[1] /= 10;
        }
    }
    return n;
}
</script>

댓글 없음:

댓글 쓰기