「080121」の編集履歴（バックアップ）一覧はこちら

「080121」(2008/01/29 (火) 01:16:59) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*080121
2008年第一発。

**フィボナッチ数を返す関数
フィボナッチ数を返す関数を書いて下さい。
また、以下の仕様を満たすことを条件とします。

-unsigned long(unsigned long int)型の引数を一つ受け取り、unsiged long型の整数を返す。
-関数名を仮に fib とすると、fib(0) は 0、fib(1) は 1とする。

**出力例
出力はありません

**提出
niha28(atmark)gmail.com

*080121
2008年第一発。

**フィボナッチ数を返す関数
フィボナッチ数を返す関数を書いて下さい。
また、以下の仕様を満たすことを条件とします。

-unsigned long(unsigned long int)型の引数を一つ受け取り、unsiged long型の整数を返す。
-関数名を仮に fib とすると、fib(0) は 0、fib(1) は 1とする。

**出力例
出力はありません

**提出
niha28(atmark)gmail.com

**回答例
 unsigned long fib(unsigned long n){
   if (n == 0){
     return 0;
   } else if(n == 1) {
     return 1;
   } else {
     return fib(n-1) + fib(n-2);
   }
 }

**説明
今回のキモは、渡された引数による条件分岐と、関数の再帰です。
if 文と関数の再帰呼び出しさえ理解できていれば解けたと思います。
ちなみにループを使っても解けますが、できれば出題者の意図を汲んで欲しいところです。
さて、例えばfib(3)を呼び出したとき、関数fibは全部で何回呼ばれるでしょうか。
fib(3)と、fib(3)からよばれるfib(1)と、fib(3)からよばれるfib(2)から呼ばれるfib…
ややこしいので図で説明すると
 fib(3)
  |
 fib(2) - fib(1)
  |
 fib(1) - fib(0)
5回ですね。これがfib(30)ならどうでしょう。
 fib(30)
  |
 fib(29) - fib(28) ----
  |                   |
 fib(28) - fib(27)  fib(27) - fib(26)
  |          |        |          |
以降も延々と増えつづけます。
つまり、渡された引数をNとすると、大体2^Nだけ関数が呼ばれるわけです。
関数の呼び出しはノーコストでは行えません。それ自体に計算が必要になるため、
Nがある程度大きくなると関数呼び出しにかかるコストも馬鹿になりません。
具体的には、回答例のコードでは、fib(30)はfib関数が実に2692537回（！）も呼び出されます。
回答例のコードの問題点は、同じフィボナッチ数を何度も計算してしまっている点にあります。
それなら、計算結果をとっておいて、既に計算している結果に関してはとっておいた値を返すようにすれば、
関数の呼び出し回数は格段に少なくなるはずです。
 unsigned long fib_memoize(unsigned long n){
   static unsigned long memo[100] = {0}; /* 関数ローカルな静的変数 */
   if (memo[n]){
     return memo[n];
   } else if (n == 0){
     return 0;
   } else if (n == 1){
     return memo[1] = 1;
   } else {
     return memo[n] = fib_memoize(n-1) + fib_memoize(n-2);
   }
 }
ということでそれを実装したのが上のコードです。
fib_memoize(30)におけるfib_memoizeの呼び出し回数は、たったの59回です。勿論計算速度も早いです。

このように同じ問題を解くにしても、実装方法によって全く計算量が違ってくることがあります。
ハードが進歩したとはいえ、非効率的な実装は当然避けるべきです。
ゲームプログラミングは、そういったテクニックをそれなりに必要とするため、一般にレベルは決して低くありません。
みんながんばれ :-)

ちなみに、今回のように計算結果を記憶しておく手法を、「関数のメモ化（memoize）」と呼びます。
純粋述語関数（引数によってのみ結果が決まる関数）にしか使えないという制限はありますが、
関数の呼び出し回数が多かったり、一回の計算量が多い場合などは非常に有効な手法です。

**採点
:タチコマ|main関数とは分けて実装して欲しかったんですが…
:イクラ|これだと引数の大小に係わらず毎回fib(MXNUM)を計算してしまいますね。
:タケ|問題なし。
:ウヒト|問題なし。