Knuth是计算机编程的艺术,见1.1.8

Question

我无法弄清楚Knuth在第1.1章的练习8的指示中的含义.

任务是让两个正整数的高效GCD算法m,并n使用他的符号theta[j],phi[j],b[j]和a[j]其中θ和phi是字符串,a以及b-正整数表示在这种情况下计算步骤.

让输入成为表单的字符串a^mb^n.

这里给schnaader 给出了Knuth算法的一个很好的解释.

我的问题是如何将这与练习中给出的方向联系起来,使用他在书中给出的算法E,其中原始r(余数)被替换为|m-n|和n替换min(m,n).

Answer 1

当Knuth说"让输入由字符串表示a^mb^n"时,他的意思是输入应该采用s 的m数量和as的n数量b.所以输入f((m,n))where m = 3和n = 2将由字符串表示aaabb.

花点时间回顾一下该章中的等式3,它代表马尔可夫算法.(下面)

        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.这样,使用上面的Markov算法,您可以指定输入字符串的内容,具体取决于值j.

现在,谈谈你的主要问题;

我的问题是如何将这与练习中给出的方向联系起来,以使用他在书中给出的算法E,其原始r(余数)被| mn |替换.n由min(m,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).不同的是,在上面我们使用了模数运算符和除法,但在上面的例子中我们只使用了减法.

我希望这有帮助.实际上,我在博客上写了一篇关于Knuth在Markov算法上的变化的更深入的分析.因此,如果你仍然感觉有点卡住,请阅读系列文章.