質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

1回答

1715閲覧

C言語 動的計画法の処理速度、向上

tamura0425

総合スコア37

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2021/07/30 09:42

以下の改題をだされたのですが、作成したコードでは処理時間の判定に引っかかってしまいます。

コードをどのように書き直したらよいでしょうか?

作成コード

#include <stdlib.h> #define MAX 46 long int fib[MAX]; int ck[MAX]={0}; long int f_c; long int f(int n); // n番目(n>=0)のフィボナッチ数を返す int main(int argc, char *argv[]){ if(argc==1) return 0; int i; int from=atoi(argv[1]); int to=from; if(argc==3){ from=atoi(argv[1]); to=atoi(argv[2]); } if(from>to) return 0; for(i=from; i<=to; i++){ if(i==0){ printf("f(%d)=%ld [%d times]\n",i,f(i),2); } else if(i>=0){ printf("f(%d)=%ld [%d times]\n",i,f(i),i*2); } } return 0; } long int f(int n){ f_c++; if( n<=1 ) return n; return f(n-1)+f(n-2); }

問題
フィボナッチ数を計算する関数

long int f(int n)

を再帰呼出しを使って実装したものにトップダウンの動的計画法を適用した場合を考える。与えられた非負整数 n を引数とする関数呼出し f(n) を行なったときに生じる関数呼出し( f 自身の呼出し、および、そこから(直接に/再帰的に)呼び出される関数の呼出し)の回数を数え、 計算されたフィボナッチ数とともにその回数を標準出力に書き出すプログラムを作れ。

プログラムの仕様はつぎの通りとする。

コマンドライン引数に非負整数値が1個または2個与えられる。  
1個与えられた場合、その値 n を引数として呼出し f(n) を行う。
2個与えられた場合、それらの値を m1、m2 とすると m 1 ≦ n ≦ m 2 である全ての値 n について小さい方から順に関数呼出し f(n) を行う。 m1>m2 のときは関数呼出しは何も行わずに実行を終了する。
出力は、関数呼出し f(n) を行うごとにその結果をつぎの形式で1行として標準出力に書き出す。
f(n)=v [c times]
v はフィボナッチ数の値、 c はその関数呼出し回数
v と [ の間、c と times の間には、それぞれ空白1文字をおくこと。
数値 n、v、c それぞれは、必要最小限の桁数で書き出すこと。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

BeatStar

2021/07/30 09:48

インデントが滅茶苦茶で読みづらい。 それに質問にあるコードのf関数はどー見てもDP(動的系計画法)じゃないし…
int32_t

2021/07/30 09:59

問題文のとおり、「再帰呼出しを使って実装したものにトップダウンの動的計画法を適用」してください。
guest

回答1

0

ベストアンサー

1: 要素数 n+1 のtable(表/配列)を用意し、f(n)の結果をtable[n]にセットすることとする。
初めに table[0] = 0, table[1] = 1, table[2~n] = -1 をセットする 値:-1 はtableに載っていないことを意味する。

2: 関数 f(n) →
2.1: f(n) の結果がtableに載っているか調べる。載っていたらその値をそのまま返す。
2.2: 載っていなかったら f(n-2) と f(n-1) の和をtableに載せ、それを返す。

投稿2021/07/30 23:13

episteme

総合スコア16612

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

tamura0425

2021/07/31 01:12

ご教示ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問