问题标签 [knuth]

我在 Knuth 的“计算机编程艺术”的评论中阅读了以下内容：

“非常‘实用性’意味着想成为 CS 专业的学生必须学习 Kernighan 在设计 C 时的错误，尤其是臭名昭著的事实，即 for 循环反复评估 for 条件，它重复 while 并且无法匹配大多数其他语言的行为它实现了一个 for 循环。”

（http://www.amazon.com/review/R9OVJAJQCP78N/ref=cm_cr_pr_viewpnt#R9OVJAJQCP78N）

这家伙在说什么？你怎么能实现一个 for 循环，而不仅仅是 for 循环的语法糖？

在 Donald Knuth 的Literate Programming中，如果我没记错的话，有一张图表显示了 TeX 的错误数量随时间的演变。该图在过去十年左右一直保持平稳，这表明 TeX 现在可能没有错误。

我想用这张图来说明错误跟踪软件的重要性。它可以从某个地方下载吗？

我正在做 TAOCP 第 1 卷第 3 版的练习，但无法理解以下练习答案中使用的语法。

第 1 章练习 8

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

让您的输入由字符串 a ^m b ^{n 表示}（m a's 后跟 n b's）

回答：

令 A = {a,b,c}，N=5。该算法将以字符串 a ^{gcd(m,n)终止}

我难以理解的部分只是如何解释这张表。此外，当 Knuth 说这将以字符串 a ^gcd(m,n)结束时 ——为什么 gcd(m,n) 的上标？

谢谢你的帮助！

编辑了更多问题：

什么是 T _j - 注意 T = Theta

什么是 s _j - 注意 s = phi

您如何解释列 b _j和 a _j？

为什么 Knuth 将解决方案中的新符号转换为他在文本中没有解释的示例？只是令人沮丧。谢谢！！！

在第 5 页的底部是短语“将k更改为k ⊕ (1 ^{j +1} ) ₂ ”。即使在二进制中，1 的任何幂都不是 1 吗？我想这一定是笔误。我向 Knuth 博士发送了一封电子邮件报告此事，但我预计几个月后不会收到回复。与此同时，我试图弄清楚这应该是什么。

在 32 位整数数学中，加法和乘法的基本数学运算是隐式计算的，模 2^32，这意味着您的结果将是加法或乘法的最低位。

如果你想用不同的模数计算结果，你当然可以使用不同语言的任意数量的 BigInt 类。对于 a,b,c < 2^32 的值，您可以计算 64 位长整数的中间值，并使用内置的 % 运算符来减少到正确的答案

但是有人告诉我，当 C 的形式为 (2^N)-1 或 (2^N)+1，不使用 64 位数学或一个 BigInt 库，并且非常有效，比任意模计算更有效，并且还可以正确计算如果包含中间乘法，通常会溢出 32 位 int 的情况。

不幸的是，尽管听说这种特殊情况有快速评估方法，但我实际上并没有找到该方法的描述。“那不是在 Knuth 吗？” “这不是维基百科的某个地方吗？” 是我听到的喃喃自语。

这显然是随机数生成器中的一种常用技术，因为 2147483647 是一个等于 2^31 -1 的素数，所以它对 a*b mod 2147483647 进行乘法运算。

所以我会问专家。这个我找不到任何讨论的聪明的特殊情况乘法与mod方法是什么？

有人可以向我解释 MIX 中的除法（来自 Knuth 的 TAOCP）是如何逐字节工作的吗？

存储位置 1000 包含|-|0|0|0|2|0|.

执行操作时

寄存器变成

rA现在我理解了和上的符号rX，但是填充的字节的顺序是什么rAX以及完成了哪些划分？

如果 DIV 1000 导致每个位除以 2，那么我希望

其中rA包含除法结果和rX余数（从右侧填充）。

我可能在这里遗漏了一些东西，Knuth 似乎认为我应该能够自己弄清楚（因此关于它的 10 级问题，我也没有得到），但是有人可以在这里帮助我吗？

我需要找到所有可以由字符串中的字母组成的英语单词

我可以通过

如何从 Ruby 中的句子中生成超过 4500 个英语单词？

[编辑]

最好将问题分成几部分：

1. 只制作一个包含 10 个或更少字母的单词数组
2. 较长的单词可以单独查找

Donald Knuth在他的页面上有大量程序可供阅读。但它们大多采用“奇怪”的 CWEB 格式......

使它们在 Windows 中具有适当可读性的最佳方法是什么？

我正在为我正在处理的 C++ 项目实现Knuth shuffle。我试图从我的洗牌中获得最公正的结果（而且我不是（伪）随机数生成方面的专家）。我只是想确保这是最公正的洗牌实现。

draw_t是字节类型（typedef'd to unsigned char）。items是列表中的项目数。我已经包含了random::get( draw_t max )下面的代码。

我正在使用的随机函数已被修改以消除模偏差。RAND_MAX分配给random::_internal_max。

我想生成an 的排列，array a但不想使用实用程序函数，例如java.util.Collections().
排列应该是随机的，并且每个排列都应该可能发生 - 但不需要均匀分布的概率。

以下代码实现了这一点 - 但性能不佳：

问题：
是否有可能减少用于生成排列的随机数的总数？