9

TAOCP Volume 1 Edition 3 の演習を行っていますが、次の演習の回答で使用されている構文を理解するのに苦労しています。

第 1 章 演習 8

T j ,s j ,a j ,b jを指定して、正の整数 m & n の最大公約数を計算する

入力を文字列 a m b n (m a の後に n b が続く)で表します。

答え：

A = {a,b,c}、N=5 とします。アルゴリズムは文字列 a gcd(m,n) で終了します

    jTjsjbjaj _      _ _     _ _     _ _
    0 ab (空) 1 2 1 つの a と 1 つの b を削除するか、2 に進みます。
    1 (空) c 0 0 c を左端に追加し、0 に戻ります。
    2 ab 2 3 すべての a を b に変更
    3 ca 3 4 すべての c を a に変更
    4 bb 0 5 bが余ったら繰り返す

私が理解に苦しむ部分は、この表をどう解釈するかということです。また、Knuth がこれが文字列 a gcd(m,n) で終了すると言うとき、 なぜ gcd(m,n) の上付き文字なのですか?

助けてくれてありがとう！

より多くの質問で編集：

T jとは何ですか -- T = シータであることに注意してください

s jとは何ですか -- s = phi であることに注意してください

列 b jとa jをどのように解釈しますか?

なぜクヌースは、ソリューションの新しい表記法を、テキストで説明していない例に切り替えたのですか? ただイライラします。ありがとう！！！

4

3 に答える 3

4

これがその演習の答えの実装です。おそらくそれは役立ちます。

ちなみに、この表はマルコフアルゴリズムを表しているようです。

私がこれまでに理解している限りでは、最初のコマンド セット j = 0 から始めます。 T jの発生を s jに置き換え、何かを置き換えたかどうかに応じて次のコマンド ラインにジャンプします (その場合は b jにジャンプします)。 、何も置き換えられていない場合は、 a jにジャンプします)。

編集:新しい答え:

A = {a,b,c} は、操作できる文字セットのようです。アルゴリズム中に c が入ります (左に追加され、後で a に置き換えられます)。

Theta と phi は、「オリジナル」や「交換」などに通常使用するギリシャ文字かもしれませんが、それらが何であるかはわかりません。

b jと a jは、次に実行されるテーブル行です。これは、最後の列の人間が読める説明と一致します。

私が答えられない唯一のことは、クヌースが何の説明もなくこの表記法を使用する理由です。私は本の最初の章と解決策をもう一度閲覧しましたが、彼はそれについてどこにも言及していません.

EDIT2: gdc(2,2) = 2 の例

    入力文字列: aabb
    行 0: 1 つの a と 1 つの b を削除するか、2 に進みます。
    => ab => 1 へ
    1 行目: c を左端に追加し、0 に戻ります。
    => タクシー => 0 に行く
    行 0: 1 つの a と 1 つの b を削除するか、2 に進みます。
    => c => 1 へ
    1 行目: c を左端に追加し、0 に戻ります。
    => cc => 0 に移動
    行 0: 1 つの a と 1 つの b を削除するか、2 に進みます。
    ab が見つからないので、2 へ
    2 行目: すべての a を b に変更
    a が見つからないので 3 へ
    3 行目: すべての c を a に変更
    =>ああ
    4行目：bが残っていれば繰り返す
    bが見つからないので、5(終了)へ。

    => 答えは「aa」 => gdc(2,2) = 2

ちなみに、1行目の説明は「『ab』を1つ削除するか、2行目に」とすべきだと思います。これにより、物事が少し明確になります。

于 2009-02-22T17:13:06.453 に答える
1

gcd(m,n) の上付き文字は、この表で数値がどのように表されているかによるものです。

例: m => a^m n => b^n

gcd(m,n) => a^gcd(m,n)

Euclidsアルゴリズムが実装されているようです。すなわち

gcd(m,n):
  if n==0:
    return m
  return gcd(n,m%n)

モジュロ演算 m%n を実行できるように、数値は累乗で表されます。

たとえば、4 % 3 は次のように計算されます。

于 2009-02-22T17:12:05.237 に答える
1

mの概念は、おそらくステート マシン コンテキストの入力文字列の概念です。

このような概念はm、連続した のインスタンスを参照するために使用されますa。つまり、次のようになります。

a 4 = aaaa
b 7 = bbbbbbb
a 4 b 7 a 3 = aaaabbbbbbaaa

そして、gcd(m,n)が意味することは、(ソリューション) ステート マシンを実行した後、結果の文字列が次gcd(m,n)のインスタンスになることです。a

つまり、a結果の の数は、の結果と等しくなければなりません。gcd(m,n)

そして、おそらくマルコフアルゴリズムの使用法を説明する表であるという点で@schnaaderに同意します。

于 2009-02-22T17:52:38.900 に答える