Go to the first, previous, next, last section, table of contents.


書替え 練習問題 2 解答「フィボナッチ規則の別解」

これがその規則集合です。

[ fib(n) := fib(n, 1, 1) :: integer(n) :: n >= 1,
  fib(1, x, y) := x,
  fib(n, x, y) := fib(n-1, y, x+y) ]

最初の規則は人々の好む 1 引数の fib を 計算をより容易にする 3 引数の fib に変換します。 第2 の規則は、計算が終わったら 3 引数形式からもとにもどします。 第3 の規則が計算自体を実行します。 その基本的に意味するところは、 xy が連続するフィボナッチ数ならば、 yx+y は次の(重複した)フィボナッチ数の対であるということです。

n が第1 規則によって「検査済」なので、 入力が不正である限り決して使われない他の規則群には条件を付加する必要が無い事に 注目してください。 余分の条件があらゆるステップで検査される必要が無いので、 計算はさらに速くなります。

実のところ、意地悪なユーモアセンスを持つユーザーは、 不正な 3 引数の fib 呼出しを直接入力することができました。 例えば `fib(0, 1, 1)' は規則群を無限ループに陥らせます。 偶然のハプニングからこれを守る対策の一つは、 fib に代えて `ZzFib' のような名前を 3 引数関数の名前として使うことでしょう。


Go to the first, previous, next, last section, table of contents.     利用度数