SICP 演習 1.11 の解き方がわからない
https://stackoverflow.com/questions/2365993
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
機能
fという規則によって定義されますf(n) = nもしn < 3そしてf(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)もしn > 3. 。計算するプロシージャを書くf再帰的なプロセスによって。計算するプロシージャを書くf反復プロセスによって。
再帰的に実装するのは非常に簡単です。しかし、それを繰り返し実行する方法がわかりませんでした。与えられたフィボナッチの例と比較してみましたが、それをどのように例えればよいのかわかりませんでした。それで私は諦めて（恥ずかしながら）グーグルで検索しました 説明, で、こんなものを見つけました。
(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))))
読んだ後、コードとそれがどのように機能するかを理解しました。しかし、私が理解していないのは、関数の再帰定義からこれに至るまでに必要なプロセスです。人の頭の中でどうやってコードが形成されたのか理解できません。
解決策に到達するために必要な思考プロセスを説明していただけますか?
解決
あなたは、いくつかのアキュムレータの状態をキャプチャし、各繰り返しでの状態を更新する必要があります。
は、命令型言語の経験をお持ちの場合は、whileループを書くと、ループの各反復中の変数で追跡情報を想像してみてください。あなたはどのような変数が必要でしょうか？どのようにそれらを更新しますか？それはまさにあなたがスキームのコールの反復（末尾再帰）のセットを作るために何をすべきかです。
言い換えれば、それは、whileループの代わりに、再帰的な定義としてこの考え方を開始するために役立つかもしれません。結局あなたは再帰的で流暢に十分だろう - 。あなたが始めるために余分なヘルプを必要としないこと>反復変換
<時間> それはそれらを表現する方法をすぐにはっきりしないので、この例では、あなたは、3つの関数呼び出しをよく見ています。しかし、ここではそう思考プロセスがあります：（Pythonの擬似コードでimperativenessを強調するために）
f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 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
だから、NEWVALUEは何ですか？さて、今私たちは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
他のヒント
私はあなたの1は、自然に「デザインパターン」の外にアルゴリズムを発見する方法を求めていると思います。
私は、各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（4）の[休止]を計算するため必要に起こるF（2）及びf（1）同様に、計算する。
f(3) = f(2) + 2f(1) + 3f(0)
↘ ↘
f(4) = f(3) + 2f(2) + 3f(1)
そうでは、任意の数のN、IはF（3）を計算することにより開始し、そしてIが計算F（4）への計算F（3）に使用する値を再利用...パターンは...
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）の計算を歩くステップで添字ます：
Step 1: f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a1 + 2b1 +3c1
ここで、
<サブ> 1 = F（2）= 2、
B <サブ> 1 = F（1）= 1、
C <サブ> 1 0
F（N）以降= N nに対する<3。
したがってます：
F（3）= <サブ> 1 + 2B <サブ> 1 + 3C <サブ> 1 = 4
Step 2: f(4) = f(3) + 2a1 + 3b1
ですからます：
2 = F（3）= 4（ステップ1において上で計算される）、
B 2 = <サブ> 1 = F（2）= 2、
C 2 = B <サブ> 1 = F（1）= 1
したがってます：
F（4）= 4 + 2×2 + 3 * 1 = 11
Step 3: f(5) = f(4) + 2a2 + 3b2
ですからます：
<サブ> 3 = F（4）= 11（ステップ2において上で計算された）、
B <サブ> 3 = 2 = F（3）= 4、
C <サブ> 3 = B 2 = F（2）= 2
したがってます：
F（5）= 11 + 2 * 4 + 3 * 2 = 25
上記の計算を通じて、我々は、前の計算状態をキャプチャし、次のステップに渡します particularilyます：
ステップの<サブ>ステップ =結果 - 1
B <サブ>ステップ = <サブ>ステップ - 1
C <サブ>ステップ = B <サブ>ステップ-1
私はこれを見たら、、その後、反復バージョンを考え出すのは簡単だった。
は、ソリューションについて多くのことを説明するためにリンクされ、ポストので、私は唯一の補完的な情報を提供しようとするでしょう。
あなたは（非尾）再帰的定義を与えます。
、ここではSchemeで末尾再帰関数を定義しようとしています再帰の基本ケース（F（N）= N 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）は（N - 1）Fとして使用するためには、回転F（N - 1）からf（N - 2）とf（nは - nはF（2） - 。3）、及びデクリメント数
。それはあなたがすでに比較的完全な説明与えられた「私は理解していない」書き込み時に答えることは本当に難しい -これはまだ助けがない場合は、より具体的な質問をしてみてください
ここでは、他の回答とは少し異なるアプローチでこれに取り組み、コーディングスタイルによってこのようなアルゴリズムの背後にある思考プロセスがどのように理解しやすくなるかに焦点を当てます。
のトラブル ビルのアプローチ, あなたの質問で引用されているのは、それが何であるかすぐには明らかではないということです。 意味 状態変数によって伝えられ、 a, b, 、 そして c. 。彼らの名前は何の情報も伝えておらず、ビルの投稿には彼らが従う不変条件やその他の規則については記述されていません。状態変数が相互の関係を説明する文書化されたルールに従っている場合、反復アルゴリズムを定式化することも理解することも容易になることがわかります。
これを念頭に置いて、まったく同じアルゴリズムのこの代替定式化を検討してください。このアルゴリズムは、より意味のある変数名を持つ点だけが 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):
- カウンタ変数があります
iそれは 2 から始まり、n, を呼び出すたびに 1 ずつ増加します。f-iter. - 途中の各ステップで、次のことを追跡します。
f(i),f(i-1)そしてf(i-2), を計算するには十分です。f(i+1). - 一度
i=n, 、終わりました。
は、関数
fは、ルールそのf(n) = n, if n<3とf(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3によって定義されます。再帰的な処理によってfを計算手順を記述します。
これはがはすでに書かれます：
f(n) = n, (* if *) n < 3
= f(n - 1) + 2f(n - 2) + 3f(n - 3), (* if *) n > 3
信じられないかもしれませんが、な言語に一度ありました。別の言語でこのダウンを書き込むには、構文だけの問題です。ところで、あなた（MIS）などの定義が、それは現在、非常に明白でかつ明確であるバグを、持っている引用します。
計算する反復プロセスによって
fこと手順を記述します。
反復は行くの前方のに（の意味しますのご説明があります）再帰のが行くとは対照的に、の後方の最初に：！
f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)
= a + 2b + 3c
f(n+1) = f(n ) + 2f(n - 1) + 3f(n - 2)
= a' + 2b' + 3c' a' = a+2b+3c, b' = a, c' = b
......
このは、このように
のように、問題の状態遷移を記述する (n, a, b, c) -> (n+1, a+2*b+3*c, a, b)
私たちは、
としてそれをコーディングすることができg (n, a, b, c) = g (n+1, a+2*b+3*c, a, b)
もちろん、それは今まで停止しないでしょう。我々は、代わりに
を持っている必要がありますので、f n = g (2, 2, 1, 0)
where
g (k, a, b, c) = g (k+1, a+2*b+3*c, a, b), (* if *) k < n
g (k, a, b, c) = a, otherwise
これはまさにあなたがアップ構文に、について尋ねられたコードのように、すでにある。
コーナーケースと可能なオフ対1のエラーは、エクササイズ非興味深い専門的として除外されます。
