dmsgh7678   10달 전

답은 맞는거 같은데... 어디가 문제인지 모르겠어요.. 피보나치 수열 사용해서 한건데 맞는거 같은데 ㅠㅠ

game2k   10달 전

100만번째 피보나치수는 확실히 int 범위를 벗어나겠네요...

dmsgh7678   10달 전

double로 고치면 될까요??

game2k   10달 전

for(i=2;i<n;i++)
            num[i]=num[i-1]+num[i-2];

부분에서 이미 int 범위를 벗어난 결과를 계산하고 있은 후

printf("%d\n",num[n-1]%15746); 를 하게 되면 int 값을 벗어난 값에 대해나머지 연산을 하므로 잘못된 답이 나옵니다.

(a+b)mod p = (a mod p + b mod p) mod p 를 이용해 보세요

dmsgh7678   10달 전

감사합니다. 고치니 해결되었어요 ㅎㅎ

alphago92   8달 전

한가지 참고하셨으면 하는 것은

굳이 배열을 선언해서 메모리 잡아먹을 필요없습니다

N=10000 이면 sizeof(int)*10000 byte의 메모리를 잡으신다는 건데


어차피 기본 concept은

f(n)=f(n-1)+f(n-2) 이지 않습니까


따라서 f(n)을 구하려면 그 전상태와, 그 전전 상태만 알고있으면 됩니다


가령

a=1,b=2,c=0;

for(i=3;i<=N;i++){
c=a+b;    //f(n)=f(n-2)+f(n-1)
a=b;        //전전상태를 저장하는 a변수에 전상태 b값을 저장
b=c;        //전상태를 저장하는 b변수에 현재상태 c값을 저장
}

이런 식으로 메모리 오버헤드를 기하급수적으로 줄일 수 있습니다

댓글을 작성하려면 로그인해야 합니다.