Ich mache die Übungen zu TAOCP Band 1 Ausgabe 3 und habe Probleme beim Verständnis der Syntax, die in der Antwort auf die folgende Übung verwendet wird.
Kapitel 1, Übung 8
Berechnen des größten gemeinsamen Teilers positiver Ganzzahlen m & amp; n durch Spezifizieren von T j, s j, a j, b j
Lassen Sie Ihre Eingabe durch die Zeichenfolge a m b n dargestellt werden (m a folgt von n b)
Antwort:
Sei A = {a, b, c}, N = 5. Der Algorithmus wird mit der Zeichenfolge a gcd (m, n)
enden %Vor%Der Teil, den ich nicht verstehen kann, ist einfach, wie man diese Tabelle interpretiert. Auch wenn Knuth sagt, dass dies mit der Zeichenkette a gcd (m, n) enden wird - warum die Hochstellung für gcd (m, n)?
Danke für jede Hilfe!
Bearbeitet mit mehr Fragen:
Was ist T j - beachten Sie, dass T = Theta
Was ist s j - beachten Sie, dass s = phi
Wie interpretieren Sie die Spalten b j und a j ?
?Warum wechselt Knuth eine neue Notation in der Lösung zu einem Beispiel, das er im Text nicht erklärt? Einfach frustrierend. Danke !!!
Hier ist eine Implementierung dieser Übungsantwort. Vielleicht hilft es.
Übrigens scheint die Tabelle einen Markov-Algorithmus zu beschreiben.
Soweit ich soweit verstanden habe, beginnen Sie mit dem ersten Befehlssatz, j = 0. Ersetzen Sie alle Vorkommen von T j durch s j und springen Sie zu nächste Befehlszeile abhängig davon, ob Sie etwas ersetzt haben (in diesem Fall zu b j springen, wenn nichts ersetzt wurde, springen Sie zu einem j ).
BEARBEITEN: Neue Antworten:
A = {a, b, c} scheint der Zeichensatz zu sein, mit dem Sie arbeiten können. c kommt während des Algorithmus hinzu (wird links hinzugefügt und später wieder durch a ersetzt).
Theta und phi könnte ein griechischer Charakter sein, den Sie normalerweise für etwas wie "Original" und "Ersatz" verwenden, obwohl ich nicht wissen würde, dass sie das sind.
b j und a j sind die Tabellenzeilen, die als nächstes ausgeführt werden. Dies stimmt mit den von Menschen lesbaren Beschreibungen in der letzten Spalte überein.
Das einzige, was ich nicht beantworten kann, ist, warum Knuth diese Notation ohne irgendwelche Erklärungen benutzt. Ich habe die ersten Kapitel und die Lösungen im Buch noch einmal durchgeblättert und nirgendwo erwähnt.
EDIT2: Beispiel für gdc (2,2) = 2
%Vor%Übrigens, ich denke, die Beschreibung zu Zeile 1 sollte "Remove one" ab "sein, oder gehe zu 2." Dies macht die Dinge ein wenig klarer.
Die Hochstellung für gcd (m, n) hängt davon ab, wie Zahlen in dieser Tabelle dargestellt werden.
Zum Beispiel: m = & gt; a ^ m n = & gt; b ^ n
gcd (m, n) = & gt; a ^ gcd (m, n)
Es sieht so aus, als ob der Euclids-Algorithmus implementiert wird. d. h.
%Vor%Die Zahlen werden als Potenzen dargestellt, um die Modulo-Operation m% n ausführen zu können.
Zum Beispiel wird 4% 3 wie folgt berechnet: 4 'a (a ^ 4) mod 3' b (b ^ 3), was 1 'a' (a ^ 1) zurücklässt.
Der Begriff eines m ist wahrscheinlich eine Vorstellung von Eingabezeichenfolgen im Kontext der Zustandsmaschine.
Dieser Begriff wird verwendet, um sich auf m Instanzen von aufeinanderfolgenden a zu beziehen, d.h.:
a 4 = aaaa
b 7 = bbbbbbb
a 4 b 7 a 3 = aaaabbbbbbbaaa
Und was ein gcd (m, n) bedeutet, ist, dass nach dem Ausführen des (Lösungs-) Zustandsautomaten der resultierende String gcd(m,n) Instanzen von a
Mit anderen Worten, die Anzahl von a im Ergebnis sollte gleich dem Ergebnis von gcd(m,n)
Und ich stimme @schnaader darin zu, dass es wahrscheinlich eine Tabelle ist, die die Verwendung des Markov-Algorithmus beschreibt.