问题标签 [taocp]

我刚开始阅读 TAOCP 第 1 卷，但我无法理解其风格。

Knuth 提到了一种计算方法是四元组（Q，I，Omega，f）——但我无法理解这些方法中的每一个是什么。我理解他的第一个例子，但不明白他的第二个例子

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

在本章的最后，有一个算法讨论了字符串集。

（我已经用一些更容易输入的变量替换了希腊变量——抱歉）

令 A 为有限的字母集，令 A* 为 A 上所有字符串的集合。想法是对计算状态进行编码，以便它们由 A* 的字符串表示

（注意 p & w 是字符串）如果和 s 是 A* 中的字符串，我们说 T 出现在 s 中，如果 s 对字符串 p 和 w 具有 pTw 的形式。

我理解制作字符串集的概念，但不理解他在这里想说的所有内容。为什么我需要Q、I、Omega？f 真正向我解释了什么（为什么我需要 f 中的 3 个函数？）？

任何人都可以帮忙阐明一下吗？

我正在做 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 博士发送了一封电子邮件报告此事，但我预计几个月后不会收到回复。与此同时，我试图弄清楚这应该是什么。

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

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

执行操作时

寄存器变成

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

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

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

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

我在工作 tacop 2.2.2 顺序分配时遇到了一些问题，在第 247 页重新打包内存部分。

主题是有 n 个堆栈共享一个公共区域位置 L0 < L < LX，最初我们设置 BASE[j] = TOP[j] = L0 为 1 <= j <= n

目标是在插入或删除关于堆栈 i 的元素时发生溢出时，如何重新打包内存。（通过从尚未填满的桌子上拿走一些来为堆栈 i 腾出空间）。

一个）。如果存在任何这样的 k，则找到 i < k < n 且 TOP[k] < BASE[k+1] 的最小 k。将事情提升一个档次，设置 CONTENTS(L+1) -> CONTENTS(L)，对于 TOP[k] >= L > BASE[i+1] 最后，设置 BASE[j] -> BASE[j] + 1 , TOP[j] -> TOP[j] + 1, 对于 i < j < k

这是我的问题：

他们如何找到尚未填充的堆栈？堆栈 k? 为什么选择最小的k？

TAOCP vol 1 中的“练习笔记”部分有一个问题，类似于：

“证明 13^3 = 2197。概括你的答案。（这是作者试图避免的一种可怕的问题）。”

问题：

1. 您将如何实际证明这一点？（直接乘法是一种方法，另一种方法是使用 (a+b)^3 的公式）。解决方案是否需要使用某种方法来进行某种概括？

2. 这里的概括是什么？

3. 为什么这是一个可怕的问题？

4. 您还知道哪些其他类似的可怕问题？

感谢任何答案。

PS如果上面的问题陈述使它看起来像一个家庭作业问题，我深表歉意，但事实并非如此。要求大家不要将此标记为家庭作业问题，以便更多人给出答案。

我尝试实现Donald E. Knuth 的算法 O（定向森林）：“计算机编程的艺术 - 第 4 卷，Fascile 4，生成所有树”（第 24 页）。

我的 Python 解决方案是：

我的实施给了我：

[0, 1, 2, 3], [0, 1, 2, 2], [0, 1, 2, 1], [0, 1, 2, 0], [0, 1, 1, 1], [0, 1, 1, 0],

[0, 1, 0, 3] ,

[0, 1, 0, 0], [0, 0, 0, 0]。

我已经在寻找一个错误太久了。希望有人能指出我修复代码的正确方向。我对算法的理解正确吗？对我的 python 风格的任何改进也值得赞赏。谢谢你的帮助。

我想知道 Donald Knuth 是否涵盖了他伟大著作中的不相交集？如果有，是哪一章？

最好的祝福，

我从事软件开发的职业是获得英语学位，而不是计算机科学或其他科学/工程背景。我在自学的基础上已经走了很长一段路，但是在这样做了 10 多年之后，我想回去填补空白，尤其是在数学方面。

让自己接受 Comp-Sci 教育的显而易见的地方是学习计算机编程艺术。然而，由于我没有学过那么多数学，而且我在大学的最后一堂数学课是在 1995 年，所以我需要一些复习和增强才能阅读 TAOCP 中的数学符号。

我的想法是去可汗学院学习必要的主题，作为阅读 TAOCP 的先决条件。但是，在第 22 条军规中，我试图弄清楚我实际上需要通过哪些主题作为准备。

所以，我想知道的是，如果某人基本上只有高中数学（我有更多的数学知识，但我认为对于仅以高中为背景的人来说这是一个有效的问题），什么数学“课程”是否需要像可汗学院这样的地方才能开始 TAOCP 准备阅读和理解所包含的数学？

嗨，我的第一个问题……我开始阅读“计算机编程的艺术”。我知道这很难。首先，我决定使用书籍的语言——我从 MIX 开始。我做了一些练习，我认为我可以使用书中的程序进行管理。但是问题到处都是我写的，MIX老了，学MMIX等等。好的，但是为什么-这是我的问题？我正在学习 1 moth MIX，我开始理解书中的问题，现在停止工作并再次开始学习新的 ASM，为什么？话说，MIX老了，但是书里所有的代码都是MIX，如果我花时间学习MMIX，我得重新写问题，我想这对我来说会很困难。MIX是不是太老了，我真的必须学习新版本吗？有更多TAOCP经验的人可以给我一个建议：继续看书——MIX中的示例、问题等，或者停止学习MMIX。和，