相关疑难解决方法(0)

我刚开始阅读TAOCP第1卷,我无法理解风格.

Knuth提到一种计算方法是四倍(Q,I,Omega,f) - 但我无法理解这些方法的目的是什么.我理解他的第一个例子,但不理解他的第二个例子

我正在看第三版的第8页.

在本章的最后,有一个算法,讨论字符串集.

(我用一些更容易输入的希腊变量替换了 - 对不起)

设A是一组有限的字母,让A*为A上所有字符串的集合.想法是对计算的状态进行编码,使它们用A*的字符串表示

Q = (s,j) where s is in A* and j is an integer, 0 <= j <= N 
I = subset of Q with j = 0
Omega = subset with j = N
f = function below  

(注意p&w是字符串)如果和s是A*中的字符串,我们说如果s的字符串p和w为字符串p,则T出现在s中.

f(s,j) = (s,aj)             if Tj does not occur in s;
f(s,j) = (pYjw,bj)   if p is the shortest possible string for which s = …

我正在练习TAOCP第1版第3版,并且无法理解下面练习答案中使用的语法.

第1章练习8

通过指定T _j,s _j,a _j,b _j来计算正整数m&n的最大公约数

让你的输入用字符串a ^m b ^n表示(ma后跟n b)

回答:

设A = {a,b,c},N = 5.该算法将以字符串a ^{gcd(m,n)结束}

    j     Tj     sj    bj    aj
    0     ab  (empty)  1    2   Remove one a and one b, or go to 2.
    1   (empty)  c     0    0   Add c at extreme left, go back to 0.
    2     a      b     2    3   Change all a's to b's
    3     c      a     3    4   Change all c's …