2

フィボナッチ数列の n 桁目を見つけるための対数時間手順を定義する演習用に読んだソリューションを理解しようとしています。問題は、コンピュータ プログラムの構造と解釈 (SICP) の 1.19 です。

ネタバレ注意:この問題の解決策については、以下で説明します。

Fib(n) は次のように線形時間で計算できます。 a = 1 および b = 0 から開始します。Fib(n) は常に b の値に等しくなります。したがって、最初は n = 0 で、Fib(0) = 0 です。次の変換が適用されるたびに、n は 1 ずつインクリメントされ、Fib(n) は b の値に等しくなります。

   a <-- a + b
   b <-- a

これを対数時間で行うために、問題の説明では変換 T を次のように定義します。

a' <-- bq + aq + ap
b' <-- bp + aq

ここで、最初は p = 0 および q = 1 であるため、この変換は上記のものと同じです。

次に、上記の変換を 2 回適用すると、新しい値 a'' と b'' を a と b の元の値で表すことができます。

a'' <-- b'q + a'q + a'p = (2pq + q^2)b + (2pq + q^2)a + (p^2 + q^2)a
b' <-- b'p + a'q = (p^2 + q^2)b + (2pq + q^2)a

次に、演習では、変換を 2 回適用するこのようなアプリケーションを「変換の 2 乗」と呼びます。私の理解は正しいですか？

この演習の解法は、上記の二乗変換の値を使用する手法を適用して、対数時間で実行される解を生成します。問題は対数時間でどのように実行されますか? 二乗変換を適用した結果を使用するたびに、2 回ではなく 1 回の変換を行う必要があるように思えます。では、どのようにしてステップ数を毎回半分に減らしていくのでしょうか?

schemewiki.org からの解決策は以下に掲載されています。

 (define (fib n) 
   (fib-iter 1 0 0 1 n)) 
 (define (fib-iter a b p q count) 
   (cond ((= count 0) b) 
         ((even? count) 
          (fib-iter a 
                    b 
                    (+ (square p) (square q)) 
                    (+ (* 2 p q) (square q)) 
                    (/ count 2))) 
         (else (fib-iter (+ (* b q) (* a q) (* a p)) 
                         (+ (* b p) (* a q)) 
                         p 
                         q 
                         (- count 1))))) 

 (define (square x) (* x x))
4

2 に答える 2

1

次に、演習では、変換を 2 回適用するこのようなアプリケーションを「変換の 2 乗」と呼びます。私の理解は正しいですか？

はい、変換を 2 乗するということは、それを 2 回適用すること、または (この演習の解決策の場合のように) 2 回適用することと同等の別の変換を見つけることを意味します。

問題は対数時間でどのように実行されますか? 二乗変換を適用した結果を使用するたびに、2 回ではなく 1 回の変換を行う必要があるように思えます。では、どのようにしてステップ数を毎回半分に減らしていくのでしょうか?

p与えられた変換を 2 乗すると、元の変換よりも 2 乗変換の方がとの値qがはるかに速く増加するため、ステップ数を削減できます。これは、乗算を繰り返すよりも連続した 2 乗を使用して指数を計算する方法に似ています。

では、どのようにしてステップ数を毎回半分に減らしていくのでしょうか?

これは、指定されたコードにあります。countが偶数のときはいつでも(/ count 2)、次の反復で count に渡されます。n最初の反復で渡される値に関係なく、交互の反復でも同じになります (最悪の場合)。

この演習で 2 乗変換の導出を段階的に確認したい場合は、 SICP 演習 1.19: フィボナッチ数の計算に関する私のブログ投稿を読むことができます。

于 2013-02-17T03:07:03.717 に答える
0

@Bill-the-Lizard は素晴らしい証拠を提供してくれますが、変換に関して「2 回」という言葉と「2 乗」という言葉について自分が考えていることと矛盾することを許しています。

a) T の 2 倍の計算、つまり T の 2 倍は、乗算のケースです。乗算のプロセスは、各ステップで T を定数値だけインクリメントする単純なプロセスです。ここで、定数値は元の項そのものです。

しかし対照的に：

b) 与えられたフィボナッチ変換は、(定数値の使用とは対照的に) 操作の各ステップで項 T の最新の状態を使用する必要があるプロセスです。そして、操作の式は単純なインクリメントではなく、実際には 2 次式です (つまり、連続する各ステップで 2 乗する必要があります)。

ビルが言うように、この連続する 2 乗効果は、デバッガーでステップ実行すると非常に明確になります (どこかで行き詰まるたびに、いくつかの単純なケースを手動で計算することを好みます)。

このプロセスを別の方法で考えてみましょう。

目的地に到達するには、次のステップで現在の距離の 2 乗をカバーできますが、それでも各ステップを完了するのに一定の時間を費やすことができれば、一定のステップを踏む場合よりも速く目的地に到達できます。 、それぞれ一定時間。

于 2013-04-06T06:34:46.490 に答える