Knuth計算機編程的藝術ex 1.1.8

我不明白Knuth在第1.1章練習8中的含義。Knuth計算機編程的藝術ex 1.1.8

的任務是使兩個正整數m和n的有效GCD算法，用他的符號theta[j]，phi[j]，b[j]和a[j]其中θ和phi是字符串，a和b - 這表示在這種情況下計算步驟正整數。

讓輸入爲形式爲a^mb^n的字符串。

Knuth算法的一個很好的解釋由schnaader here給出。

我的問題是如何可以在運動給他使用算法E在書中與原r（餘）鑑於|m-n|和n通過min(m,n)替補的方向進行連接。

來源

2014-11-04 Maksim Bondaruk

此問題可能更適合[程序員堆棧交換]（http://programmers.stackexchange.com/）站點。 – Kohlbrr 2014-11-04 18:44:45

我認爲這裏可以，也可以在cs.stackexchange.com上。 – eleanora 2014-11-04 20:16:05

當克努特說：「讓輸入的字符串a^mb^n代表」，他的意思是，輸入應採取的m數量a S和n數b S中的形式。因此輸入f((m,n))其中m = 3和n = 2將由字符串aaabb表示。

花點時間回顧一下他在這一章中的等式3，它代表了Markov algorithm。（下）

 f((σ,j)) = (σ,a_j)  if θ_j does not occur in σ 
     f((σ,j)) = (αφ_jω,b_j) if α is the shortest string for which σ = αθ_jω 
     f((σ,N)) = (σ,N)

所以我們的想法是爲每個變量j, θ_j, φ_j, a_j & b_j定義序列。這樣，使用上述馬爾可夫算法，您可以指定輸入字符串發生了什麼，具體取決於j的值。

現在，爲了解決您的主要問題;

我的問題是，這可能如何與練習中給出的方向聯繫起來，使用他的算法E給出的書中給出的原始r（餘數）替換爲| m-n |並用min（m，n）代替n。

Knuth在這裏說的基本上是你不能用上面的馬爾可夫算法進行分割。那麼最接近師的是什麼？那麼，基本上我們可以從較大的數字中減去較小的數字，直到剩下剩下的數字爲止。例如;

10 % 4 = 2與做以下相同;

 10 - 4 = 6  Can we remove another 4? Yes. Do it again. 
     6 - 4 = 2  Can we remove another 4? No. We have our remainder.

現在我們有我們的剩餘。這實質上就是他希望你對我們的輸入字符串做什麼，例如aaabb。

如果你通過這本書和工作，通過幾個例子後面Knuth的建議復讀，你會看到，這基本上是什麼，他是通過除去對ab做，然後加入c直到沒有更多的對ab存在。以我在頂部使用的示例爲例，我們得到了被操縱的字符串aaabb, aab, caab, ca, cca, ccb, aab (then start again)

這與r = m % n, m = n, n = r (then start again)相同。不同的是，在上面我們已經使用了模運算符和除法，但在上面的例子中我們只使用了減法。

我希望這會有所幫助。我的博客上實際上是wrote a more in-depth analysis of Knuth's variation on a Markov algorithm。所以如果你仍然覺得有點卡住，請閱讀本系列。

來源

2015-01-30 23:22:09

Knuth計算機編程的藝術ex 1.1.8

回答

相關問題