フィボナッチ数列において無限ループが発生してしまう

Question

条件

f(0)=3,
f(1)=0,
f(2)=2,
f(n)=f(n-2)+f(n-3)
で表されるフィボナッチ数列をn=1から繰り返したときに、
f(n)がnで割り切れるnを小さい方からkとし、その値をh(k)としたときに、h(32)の値を知りたいです。

該当のソースコード

#include<stdio.h>
#define N 10000

int fibo(int n){
    if(n==0) return 3;
    if(n==1) return 0;
    if(n==2) return 2;
    if(n>=3){
        return fibo(n-2)+fibo(n-3);
    }
}

int main(void){
    int k,num,cnt=0;
    while(cnt<=32){
        for(num=1;num<N;num++){
            k=fibo(num);
            if(k%num==0){
                cnt++;
            }
        }
    }
    printf("%d",k);
    return 0;
}

###発生している問題
ループが発生して正しい答えが得られません。分かる方いたら解答をお願いします。

Comments

[episteme]

ループが発生しているのはどこですか?

[katkey]

デバックの使い方が分からないので、ループの発生個所が分かりません。申し訳ないです。

[episteme]

mainのfor-loop内でcntをプリントしてみよう。cntが32に達しないためにwhile-loopを抜けられないのでは?

[katkey]

cntの値が22で止まってしまいます。

[episteme]

だからでしょ。そもそもcntの意味は?

Answer 1

• f(n)の値がf(77)から32ビット符号付き整数の範囲を超えてしまうため、intが32ビット符号付き整数の処理系では正常に計算が行なわれない。long long intに変更すれば、今回の答えは得られる。
• main()での処理がおかしい。forループでnumの値を1からN-1まで増やしながら、条件にあうnumの値が見つかったらcntを1増やせばいい。
• fibo()を呼び出すたびにフィボナッチ数列を再帰計算しているが、それまでの計算結果をキャッシュしておけば、処理にかかる時間がてきめんに減る。

#include <stdio.h>
#define N 10000

long long int answer_cache[N];

long long int fibo(int n)
{
    if (n == 0) return 3;
    if (n == 1) return 0;
    if (n == 2) return 2;
    if (n >= 2) {
        if (answer_cache[n] == 0) {
            answer_cache[n] = fibo(n - 2) + fibo(n - 3);
        }
        return answer_cache[n];
    }
}

int main(void)
{
    int cnt = 0;
    for (int num = 1; num < N; num++) {
        long long int k = fibo(num);
        if (k % num == 0) {
            cnt++;
            printf("fibo(%d) = %lld (cnt %d)\n", num, k, cnt); /* 途中経過 */
        }
        if (cnt == 32) {
            printf("%lld", k);
            break;
        }
    }
    return 0;
}

Comments

[katkey]

while文を使うのではなく、breakでループを抜けた方がよいということでしょうか？
また、キャッシュというのは配列に数字を保存するということでよいでしょうか？

[Daregada]

元々のコードでは、mainの中でforループをwhileループで囲んで2重の繰り返しをしていますが、意味がありません。1回のforループですべての答えが見つかります。

キャッシュは、「値をどこかに保存しておいて後でまた使う」ぐらいの意味合いで、今回は記述を簡単にするためにグローバルな配列を利用していますが、値を保存しておけるならどのような方法でも構いません。

[katkey]

解答ありがとうございます。