再帰の問題が分かりません。

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: 再帰の問題が分かりません。

Re: 再帰の問題が分かりません。

#3

by ピオーネ » 7年前

よく考えてみるとそうでした。
ありがとうございます。
ちなみに、再帰は実際によく使われるものですか？ループと比べた時のメリットはあるのでしょうか。

Re: 再帰の問題が分かりません。

#2

by かずま » 7年前

ピオーネ さんが書きました:このコードを元に、と書いてありますが、求め方が全く異なるのに、どういうアルゴリズムにすればよいのでしょうか？
全く異なると言えますか？　異なるのは次の2点だけ。
  • 2つ前と 1つ前の和か、2つ前と 3つ前の和か。
  • 初期値が 0,1 か、3, 0, 2か。
コードの変更点は、

コード: 

4行目
long long f[1000] = { 3, 0, 2 };
9,10行目
     if (n <= 2) // 脱出条件　0,1,2なら f[n]を返す
         return f[n];
13行目
     f1 = fib(n - 3);//再帰1
26行目 (表示を fib から perrin に変えるだけ)
         printf( "perrin(%d) = %lld\n", n, f );     
27行目 (オーバーフローの検出。元が間違っている)
         if (f < 0 )
fib という関数名が残っているのは変なので

コード: 

#include <stdio.h>

long long p[1000] = { 3, 0, 2 };

long long per(int n) 
{ 
    printf("呼び出し前 n = %d\n", n);
    if (n <= 2 || p[n] > 0) return p[n];
    return p[n] = per(n - 2) + per(n - 3);
} 
 
int main(void)
{
    for (int n = 1; n < 1000; n++) {
        long long p = per(n);
        printf("perrin(%d) = %lld\n", n, p);     
        if (p < 0) break;
    }   
    return 0;
}

再帰の問題が分かりません。

#1

by ピオーネ » 7年前

現在、再帰を利用した問題を解いています。
p0 = 3, p1 = 0, p2 = 2, pn = pn−2+ pn−３ (n≥3) によって定まる数列 pn をペロン数列という。
前問のフィボナッチ数列のプログラムを元 に、再帰的にペロン数を計算 する関数 perrin(int n )を書き 、main関数でn=3以上で呼び 出し、
下のように値を表示す るプログラムを作成せよ。
perrin(3) = 3
perrin(4) = 2
perrin(5) = 5
perrin(6) = 5
perrin(7) = 7
perrin(8) = 10
perrin(9) = 12
perrin(10) = 17
perrin(11) = 22
perrin(12) = 29
perrin(13) = 39
perrin(14) = 51
perrin(15) = 68

以下が前問で作成したプログラムになります。

コード: 

//前問
#include <stdio.h>
// フィボナッチ数の計算
long long f[1000] = {0};
long long fib( int n ) 
{ 
	long long f1, f2;
	printf( "呼び出し前 n = %d\n", n );
    if (n <= 1) // 脱出条件　0なら0 1なら1を返す
	 	return n;
	if ( f[n] > 0 )
		return f[n];
	f1 = fib(n - 1);//再帰1
	f2 = fib(n - 2);//再帰2
	f[n] = f1 + f2;
	return f1 + f2;
} 

int main()
{
	long long f;
	int n;
	for ( n = 1; n < 1000; n++ )
	{
		f = fib(n);
		printf( "fib(%d) = %lld\n", n, f );		
		if ( p  < 0 ) 
			break;
	}	

	return 0;
}
このコードを元に、と書いてありますが、求め方が全く異なるのに、どういうアルゴリズムにすればよいのでしょうか？

ページトップ