30

演習 1.11 :

関数は、 ifとiffというルールによって定義されます。再帰的なプロセスによって計算する手続きを書きなさい。反復プロセスによって計算する手続きを書きなさい。f(n) = nn < 3f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)n > 3ff

再帰的に実装するのは簡単です。しかし、それを繰り返し行う方法がわかりませんでした。与えられたフィボナッチの例と比較してみましたが、類推として使用する方法がわかりませんでした. だから私はあきらめて（私に恥をかかせて）、説明を求めてグーグルで調べました。そして、私はこれを見つけました：

(define (f n)
   (if (< n 3)
       n
       (f-iter 2 1 0 n)))

(define (f-iter a b c count)
   (if (< count 3)
       a
       (f-iter (+ a (* 2 b) (* 3 c))
               a
               b
               (- count 1))))

読んだ後、コードとその仕組みを理解しました。しかし、私が理解していないのは、関数の再帰的定義からこれに到達するために必要なプロセスです。誰かの頭の中でコードがどのように形成されたのかわかりません。

解決策にたどり着くまでに必要な思考プロセスを説明していただけますか?

4

6 に答える 6

36

一部のアキュムレータで状態をキャプチャし、反復ごとに状態を更新する必要があります。

命令型言語の経験がある場合は、while ループを記述し、ループの反復ごとに変数内の情報を追跡することを想像してください。どのような変数が必要ですか? それらをどのように更新しますか？これはまさに、Scheme で反復 (末尾再帰) 呼び出しのセットを作成するために必要なことです。

つまり、これを再帰的な定義ではなく、while ループとして考え始めると役立つかもしれません。最終的には、再帰的 -> 反復的変換に十分に精通し、始めるのに特別な助けを必要としなくなります。

この特定の例では、3 つの関数呼び出しを詳しく調べる必要があります。これは、それらを表現する方法がすぐには明確ではないためです。ただし、考えられる思考プロセスは次のとおりです: (命令性を強調するための Python 擬似コード)

各再帰ステップは、次の 3 つのことを追跡します。

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)

したがって、 の現在、最後、最後から 2 番目の値を追跡するには、3 つの状態が必要ですf。(つまり、f(n-1), f(n-2) and f(n-3).) それらを呼び出しますa, b, c。各ループ内でこれらの部分を更新する必要があります。

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

ニューバリューとは？の表現が得られたf(n-1), f(n-2) and f(n-3)ので、これは単なる再帰方程式です。

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

あとは の初期値を求めるだけですa, b and c。しかし、それは簡単ですf(n) = n if n < 3。

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

まだSchemeの反復版とは少し違いますが、思考過程を見ていただければ幸いです。

于 2010-03-02T19:45:34.440 に答える
20

「デザインパターン」の外で、アルゴリズムを自然に発見する方法を尋ねていると思います。

各 n 値での f(n) の展開を見るのは役に立ちました。

f(0) = 0  |
f(1) = 1  | all known values
f(2) = 2  |

f(3) = f(2) + 2f(1) + 3f(0)
f(4) = f(3) + 2f(2) + 3f(1)
f(5) = f(4) + 2f(3) + 3f(2)
f(6) = f(5) + 2f(4) + 3f(3)

f(3) をよく見ると、既知の値からすぐに計算できることがわかります。f(4) を計算するには何が必要ですか?

少なくとも f(3) + [残り] を計算する必要があります。しかし、f(3) を計算するとき、f(2) と f(1) も計算します。これは、たまたま f(4) の [残り] を計算するために必要です。

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)

したがって、任意の数 n について、f(3) の計算から開始し、f(3) の計算に使用した値を再利用して f(4) を計算できます...そしてパターンは続きます...

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)
            ↘       ↘
f(5) = f(4) + 2f(3) + 3f(2)

再利用するので、a、b、c という名前を付けましょう。現在のステップを添字として付け、f(5) の計算を実行します。

  ステップ 1: f(3) = f(2) + 2f(1) + 3f(0) または f(3) = a 1 + 2b 1 +3c 1

どこ

1 = f(2) = 2、

b 1 = f(1) = 1、

c 1 = 0

f(n) = n for n < 3.

したがって：

f(3) = a 1 + 2b 1 + 3c 1 = 4

  ステップ 2: f(4) = f(3) + 2a 1 + 3b 1

そう：

a 2 = f(3) = 4 (上記の手順 1 で計算)、

b 2 = a 1 = f(2) = 2、

c 2 = b 1 = f(1) = 1

したがって：

f(4) = 4 + 2*2 + 3*1 = 11

  ステップ 3: f(5) = f(4) + 2a 2 + 3b 2

そう：

a 3 = f(4) = 11 (上記の手順 2 で計算)、

b 3 = a 2 = f(3) = 4、

c 3 = b 2 = f(2) = 2

したがって：

f(5) = 11 + 2*4 + 3*2 = 25

上記の計算を通して、前の計算で状態を取得し、次のステップに渡します。特に:

ステップ= ステップの結果 - 1

bステップ= aステップ - 1

cステップ= bステップ -1

これを見たら、反復バージョンを思い付くのは簡単でした。

于 2011-02-14T18:28:24.883 に答える
4

リンク先の投稿では解決策について多くのことが説明されているため、補足的な情報のみを提供するようにします。

(末尾ではない) 再帰定義が与えられた場合、Scheme で末尾再帰関数を定義しようとしています。

再帰の基本ケース (f(n) = n if n < 3) は両方の関数で処理されます。なぜ著者がこれを行うのか、私にはよくわかりません。最初の関数は次のようになります。

(define (f n)
   (f-iter 2 1 0 n))

一般的な形式は次のとおりです。

(define (f-iter ... n)
   (if (base-case? n)
       base-result
       (f-iter ...)))

f-iter のパラメーターをまだ入力していないことに注意してください。最初に、ある反復から別の反復に渡す必要がある状態を理解する必要があるためです。

ここで、f(n) の再帰形式の依存関係を見てみましょう。f(n - 1)、f(n - 2)、および f(n - 3) を参照するため、これらの値を維持する必要があります。そしてもちろん、n 自体の値が必要なので、繰り返しをやめることができます。

これが末尾再帰呼び出しを思いつく方法です: f(n) を計算して f(n - 1) として使用し、f(n - 1) を f(n - 2) および f(n - 2) に回転します。 f(n - 3) に、カウントをデクリメントします。

それでも解決しない場合は、より具体的な質問をしてみてください。すでに比較的十分な説明がなされているため、「わからない」と書くと、答えるのが非常に難しくなります。

于 2010-03-02T19:51:09.483 に答える
3

ここでの他の回答とは少し異なるアプローチでこれに取り組み、コーディングスタイルがこのようなアルゴリズムの背後にある思考プロセスを理解しやすくする方法に焦点を当てます。

あなたの質問で引用されているビルのアプローチの問題は、状態変数 、、、によって伝えられる意味がすぐには明確にならないことです。彼らの名前からは何の情報も得られず、Bill の投稿では、彼らが従う不変規則やその他の規則については説明されていません。状態変数が相互の関係を説明するいくつかの文書化された規則に従う場合、反復アルゴリズムの定式化と理解の両方が容易になると思います。abc

これを念頭に置いて、まったく同じアルゴリズムの次の別の定式化を検討してください。これは、 と の変数名がより意味のあるものであるという点だけが Bill のものと異なりa、b減少cするカウンター変数の代わりに増加するカウンター変数です。

(define (f n)
    (if (< n 3)
        n
        (f-iter n 2 0 1 2)))

(define (f-iter n 
                i 
                f-of-i-minus-2
                f-of-i-minus-1
                f-of-i)
    (if (= i n)
        f-of-i
        (f-iter n
                (+ i 1)
                f-of-i-minus-1
                f-of-i
                (+ f-of-i
                   (* 2 f-of-i-minus-1)
                   (* 3 f-of-i-minus-2)))))

突然、アルゴリズムの正しさ (およびその作成の背後にある思考プロセス) を簡単に見て説明できるようになりました。計算するにはf(n):

  • i2 から始まり まで上昇しn、 への呼び出しごとに 1 ずつ増加するカウンタ変数がありますf-iter。
  • f(i)途中の各ステップで、 、f(i-1)およびを追跡します。f(i-2)これは、 を計算するのに十分f(i+1)です。
  • 一度i=n、完了です。
于 2014-06-08T21:22:07.560 に答える