練習問題 8.4

参照と繰り返しの構文 (while, for)を使って、フィボナッチ数を求める関数を定義しなさい。

解答

let fib n =
  if (n < 3) then 1
  else
    let mem1 = ref 1;
    and mem2 = ref 1;
    and mem3 = ref 1
    in
    let x = ref 3 in
    while (!x <= n) do
      mem1 := !mem2;
      mem2 := !mem3;
      mem3 := (!mem1 + !mem2);
      x := !x + 1
    done;
    !mem3;;

書き換え可能なデータとして、mem1, mem2, mem3 を用意する。

初期値には、3つとも 1 への参照をいれておく。

x も書き換え可能なデータで、カウント用である。

!x = 3 のとき、

mem1 に mem2 が参照している値 1 を代入。
mem2 に mem3 が参照している値 1 を代入。
mem3 には、今、mem1 と mem2 にセットされた値の合計、すなわち 2 を代入する。

そして、x が参照している値を +1 しておく。

もし、n が 3 ならば、!x = n となるので、mem3 すなわち 2 が答えとして返される。

ちがうならば、!x = 4 の段階にはいる。

mem1 に mem2 が参照している値 1 が代入される。
mem2 に mem3 が参照している値 2 が代入される。
mem3 には、!mem1 と !mem2 の合計、すなわち 3 が代入される。

もし、n が 4 ならば、!mem3 すなわち 3 が答えとなる。

このように処理がすすんでいく。

Tweet