克努特的计算机编程前1.1.8艺术 [英] Knuth the art of computer programming ex 1.1.8

问题描述

我想不出什么意思克努特在他的指示从第1.1章练习8。

I can't figure out what Knuth meant in his instructions for an exercise 8 from Chapter 1.1.

的任务是使两个正整数高效的GCD算法 M 和 N 用自己的形式 THETA [J] ，披[J] ， B [J] 和 A [J] 其中theta和披是字符串， A 和 B - 从而重新在这种情况下，present计算步骤的正整数

The task is to make an efficient gcd algorithm of two positive integers m and n using his notation theta[j], phi[j], b[j] and a[j] where theta and phi are strings and a and b - positive integers which represent computational steps in this case.

让输入的形式为字符串 A ^ MB ^ N 。

Let an input be the string of the form a^mb^n.

Knuth的算法，一个优秀的解释是由 schnaader <给定href="http://stackoverflow.com/questions/575215/the-art-of-computer-programming-exercise-question-chapter-1-question-8/575315?s=15%7C2.9207#575315">here.

An excellent explanation of Knuth's algorithm is given by schnaader here.

我的问题是，如何可能与行使给使用他的算法E在书中给出的方向连接原始的研究 （余）通过取代 | MN | 和 N 按分取代（M，N） 。

My question is how this may be connected with the direction given in the exercise to use his Algorithm E given in the book with original r (remainder) substituted by |m-n| and n substituted by min(m,n).

推荐答案

当克努特说：让我们用字符串 A ^ MB ^ N ，他的意思是，输入应采取 M 数 A 和<$ C形式对 B 取值$ C> N 号。因此，输入 F（（M，N）），其中 M = 3 和 N = 2 将被重新$ P $的字符串 aaabb psented。

When Knuth says "Let the input be represented by the string a^mb^n", what he means is that the input should take the form of m number of as and n number of bs. So the input f((m,n)) where m = 3 and n = 2 would be represented by the string aaabb.

花一点时间来回顾一下他的方程3该章中，从而重新presents一个马尔科夫算法。 （下同）

Take a moment to look back at his equation 3 in that chapter, which represents a Markov algorithm. (below)

        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，a_j和放大器; b_j 。通过这种方式，使用上述马尔科夫的算法，可以指定发生在你输入​​的字符串是什么，这取决于Ĵ的值

So the idea is to define the sequence for each variable j, θ_j, φ_j, a_j & b_j. This way, using the above Markov's algorithm you can specify what happens to your input string, depending on the value of j.

现在，让到你的主要问题;

Now, to get onto your main question;

我的问题是如何可以用在锻炼; Tibial给使用他的算法E与原来的R（余）地被这本书中给出的方向连接| MN |和n由分（M，N）取代。

My question is how this may be connected with the direction given in the excercise to use his Algorithm E given in the book with original r (remainder) substituted by |m-n| and n substituted by min(m,n).

从本质上讲是什么克努特这里说的是，你不能做除法上述马尔科夫算法。那么什么是最接近划分？好了，基本上我们可以从较大的​​数量，直到我们留下了一个余数减去较小的数字。例如;

Essentially what Knuth is saying here, is that you can't do division with the above Markov's algorithm. So what's the closest thing to division? Well, essentially we can subtract the smaller number from the larger number until we're left with a remainder. For example;

10％，4 = 2 是一样的执行以下操作;

10 % 4 = 2 is the same as doing the following;

        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（再启动）

If you read through Knuth's suggested answer in the back of the book and work through a couple of examples you will see that this is essentially what he is doing by removing the pairs ab and then adding a c until no more pairs ab exist. Taking the example I used at the top we get the string being manipulated as such aaabb, aab, caab, ca, cca, ccb, aab (then start again)

这是一样的 R = M％N，M = N，N = R（再启动）。所不同的是当然，在上面我们已经使用模数运算符和分裂的，但在上面的例子中，我们只用减法。

Which is the same as r = m % n, m = n, n = r (then start again). The difference is of course that in the above we have used the modulus operator and division, but in the example above that we have only used subtraction.

我希望这有助于。我其实写了一个更深入的分析Knuth的变化对马尔可夫算法在我的博客。所以，如果你仍然感觉有点粘有一个通过一系列的阅读。

I hope this helps. I actually wrote a more in-depth analysis of Knuth's variation on a Markov algorithm on my blog. So if you're still feeling a little stuck have a read through the series.

这篇关于克努特的计算机编程前1.1.8艺术的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！