0

私はコンピュータプログラミングの概念、技術、モデルを読んでいますが、最初に、どんなに頑張っても理解できないコードがあります。

declare Pascal AddList ShiftLeft ShiftRight

fun {Pascal N}
   if N==1 then [1]
   else
      L in
      L = {Pascal N-1} % Recursion
      {AddList {ShiftLeft  L}
               {ShiftRight L}}
   end
end

fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}  % Recursion
   else [0]
   end
end

fun {ShiftRight L}
   0 | L
end

fun {AddList L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2
      then
     H1+H2|{AddList T1 T2} % Recursion
      end
   else nil
   end
end

私は一種の言語構造を取得します（これはその紹介です）が、私の邪魔になるのは再帰です。

ここで何が行われるかを抽象的に示すラベルを各再帰呼び出しに付けようとしていますが、それを理解することはできません。

私が求めているのは、これらの機能がどのように機能するかについての明確で簡単な説明です。

4

2 に答える 2

0

N == 1から始めます：これは簡単です。結果はただ[1]です。

ここで、N==2を確認します。

First we calculate L = {Pascal N-1} = {Pascal 2-1} = {Pascal 1} = [1]
Now shifted to the left: [1 0]
Shifted to the right: [0 1]
AddList just adds elementwise. So the result for {Pascal 2} is [1 1].

ここで、N == 3の場合：

{Pascal 2} = [1 1]
Shifted left:  [1 1 0]
Shifted right: [0 1 1]
Added:         [1 2 1]

もちろん、プログラムは逆に機能します。それは、より大きなものから始まりNます。ただし、関数の開始時に、パラメータがになるPascalまでプログラムは繰り返し繰り返されます。このようなもの：N1

{Pascal 3}
   {Pascal 2}
      {Pascal 1}
      [1]
   [1 1]
[1 2 1]

編集：プログラムには実際にはある種の再帰があります。の最初のものはPascal整数で始まり、Nまで繰り返され1ます。

もう1つ（ヘルパーメソッド内）は、ヘッドとテールで構成されるリストで始まり、リストが空になるとすぐに停止します。つまり、もう分割できなくなります。（これは、本質的に再帰的なデータ型である、いわゆる短所リストを使用しています。）

于 2013-03-06T16:52:05.473 に答える
0

wmeyerの説明はとてもいいです。おそらく役立つ「視覚化」を追加したいだけです->

まず、本のオリジナル版（PDF）を使っていると思いますが、機能はこんな感じです->

declare Pascal AddList ShiftLeft ShiftRight
fun {Pascal N}
   if N==1 then [1]
   else
      {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}
   end
end

fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}
   else [0] end
end

fun {ShiftRight L} 0|L end

fun {AddList L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2 then
         H1+H2|{AddList T1 T2}
      end
   else nil end
end

パスカルの三角形の8行目を表示したいとします。次のように入力します。

{Browse {Pascal 8}}

つまり、本/ここで定義されているように、関数Pascalに8をフィードした結果を表示したいとします。

最初に、関数は渡された値が1であるかどうかをテストします（これは、再帰の最後の反復（または最後の再帰呼び出し）まで真ではありません。その時点で[1]（N =の場合から） = 1）は、THAT CALL OF Pascalの出力として返され、（Pascalの）実行の「チェーン」を最初に次の最新の呼び出しに戻します（その結果[1]は、の結果に追加されます。一致するShiftLeftまたはShiftRightを実行すると、その結果がチェーンに送り返され、最初の結果（Pascal 8）に到達するまで何度も繰り返されます。したがって、呼び出しは8レベル深くなり、応答は次のレベルまで返されます。あなたは最終的な答えを得る...しかし私は先にジャンプした。

わかりました。8をフィードしたため、テストN == 1は失敗します。したがって、「リスト」をシフトしてelse句にすぐに追加する代わりに、関数は未定義の用語でそれを行うことができません。 「方程式」では、「N-1を試してみます！それが最終的な答えになるかもしれません!!」と書かれています。（ShiftLeftおよびShiftRightの場合-したがって、この分岐はrecursinoが発生するたびに発生します）

したがって、関数はShiftLeftおよびShiftRight内のPascal N-1からのその応答を待機します...待機中、待機中...

ええと、{Pascal7}はN== 1にも当てはまらないので、Pascalの新しい呼び出し（「呼び出し」、2番目と3番目の呼び出し、左右！）は、両方とも「PascalN-1とは何ですか」と尋ねます。 「（今回は7-1）そして彼らは両方とも答えを待つでしょう...

これは何度も何度も繰り返されます....ああ、N == 1になるまで待ってください！

次に、リストである[1]が返されます。BACKUP THE CHAIN ...したがって、連続する待機中の関数呼び出しは、最新のものが最初に返されます（これらはすべて、「最下部」に到達するまでの途中でますます発生することに注意してください。ここで、分割が増えるにつれてN == 1（各呼び出しで一度にShiftLeftとShiftRightを呼び出すことにより）、ShiftLeftとShiftRightへの独自のプライベート呼び出しから待機していた回答を使用して最終的にAddList計算を行うことができます。

すべてが一番下まで行き、ますます多くの関数呼び出しに分割され、次に一番上に戻って、最終的に答えを返すことができます。その最終的な答えは、Pascal関数{Pascal 8}への最初の呼び出しのelse節です。これは、内部で（Pascalの三角形の8行目が[1 7 21 35 35 21 7 1]であるため）、次のようになります。

{AddList [1 7 21 35 35 21 7 0] [0 7 21 35 35 21 7 1]} <-少なくとも、追加される最終的なリストは次のようになります。

一度追加されたものは、最終的な回答として返され、表示される1つのリストです：[1 7 21 35 35 21 7 1]

于 2019-06-30T23:31:26.543 に答える