プログラミングの問題です。

質問

プログラミングの問題です。
C++です、教えてください。

n番目の「トリボナッチ数」Tnを以下で再帰的に定義する。
T(0)=0, T(1)=0, T(2)=1, T(n+3)=T(n+2)+T(n+1)+T(n) (n≧0)
2以上の整数
をscanfで入力し、それがn番目のトリボナッチ数T(n)と等しい場合はnを表示し、どのトリボナッチ数とも一致しない場合はNOとprintfで表示するプログラムを書け。

回答No.3

katorea21

_kappe_さんの方法は、再帰呼び出しの過程で同じ計算を繰り返し行ってしまうため非効率です。その欠点を補ったものを載せます。

class Bonacci{
protected:
int bonacci[1024] = {0};
public:
virtual int calc(int n) = 0;
};

class Tribonacci:public Bonacci{
public:
virtual int calc(int n);
};

int Tribonacci::calc(int n){
if(n == 0 || n == 1){
return 0;
}else if(n == 2){
return 1;
}else if(bonacci[n] != 0){
return bonacci[n];
}else{
bonacci[n] = calc(n - 1) + calc(n - 2) + calc(n - 3);
return bonacci[n];
}
}

n=35で334745777となりますが、ほぼ一瞬で計算が終わりました。前の方法では30秒以上かかります。

トリボナッチ数の一般項をnから求める公式はあるようですが、その逆算が代数的に可能かどうかは私には分かりません。いずれにしても本題の趣旨(恐らく「再帰」の理解が問われている)からは離れてしまいますので、上の関数でn=0から順次トリボナッチ数を求めていくしかないでしょう。

(※)本回答を丸写しして宿題の回答にされるか、噛み砕いて理解しご自身の糧にされるかは質問者の判断に委ねます。

回答No.2

_kappe_

直接の答えにならない範囲で参考までに、T(n)の値を返すC/C++言語の関数です。
unsigned int tribonacci(unsigned int n) {
if (n == 0 || n == 1) return 0;
else if (n == 2) return 1;
else return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3);
}

回答No.1

_kappe_

宿題は自分でやってください。
ここで質問するならせめて丸投げを避けて、「こういうプログラムを書きましたが思った通りに動きません。どこが間違っていますか。」くらいの体裁を整えましょう。