问题标签 [knuth]

Donald Knuth 的计算机编程艺术第 1 卷第一章中的练习与使用 Euclid 的 gcd 算法对剩余步骤取平均值有关。我的代码完美地返回了 GCD，并且已经过测试。我无法让它返回剩余步骤，并且我的第二个测试标记为失败测试并在代码中带有注释无法获得正确的剩余步骤，并且只会为 gcdTestObject 上的 gcdRemainerSteps 返回 1。

我为测试直到程序中的计数而编写的第二段代码运行良好，它完美地通过了所有测试。

这会按预期返回 100 的计数器，并且测试是绿色的。

我一直在阅读 Donald Knuth 第二版的计算机编程艺术第 3 卷中的排序和搜索算法。我在第 95 页遇到了 Knuth 称之为“列表插入”（传统插入排序的一种修改）的算法。

在该页面上，Knuth 得出结论，“直接插入的正确数据结构是单向链接线性列表。”并且“链接分配（第 2.2.3 节）非常适合插入，因为只需要几个链接要改变。” 但是，第 97 页的 MIXAL 程序（程序 L）似乎没有利用传统的链表结构（一系列由地址链接的节点）。相反，键和链接似乎一起存储在一个类似结构的结构中，这些结构存储在一个名为INPUT.

我决定尝试在 C 中实现这个算法。我提供了 Knuth 对算法的描述，以及他在 MIXAL 汇编语言中的实现作为参考。我决定让键成为data数组中的元素本身，并将链接放在一个类似并行的数组中，称为links. 我说“类并行数组”是因为数组的大小links比数组的大小data大一。我这样做是为了可以data通过将其存储为数组中的第一个元素来轻松确定数组最小元素的索引links。由于 中的这个额外索引links，数组的索引 0 - (n - 1)data对应于数组的索引 1 - n links。links数组中的每个元素对应于data排序列表中下一个元素的数组。

我的问题是，根据他的描述，这个算法应该如何实现，还是我遗漏了什么？

在The Art of Computer Programming Volume 1, third edition一书中，我很难理解以下 MIX 汇编语言指令的含义：ENT1 *，它出现在本书的第 189 页。

(p.189) 例如，如果我们想让MAXNbe的调用序列

那么子程序可以写成如下：

到目前为止我发现的是以下行

将存储常量的内存地址n存储到存储指令的内存位置的 [0:2] 字段中ENT1 *。

因此，我在这里猜测以下行

应该将存储指令的内存位置的 [0:2] 字段的值加载ENT1 *到 register I1。

*但是，如教科书所述，星号（）的含义是：

(p.146) 星号（读作“self”）指的是它出现的行的位置。

那么，不应该 ENT1 *只将存储指令的内存位置的地址ENT1 *存储到寄存器I1吗？

我为 Mastermind 实现了 Donald Knuth 1977 算法https://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf

我能够重现他的结果——在最坏的情况下 5 次猜测获胜，平均为 4.476。

然后我尝试了一些不同的东西。我反复运行 Knuth 的算法，并在每次开始前随机打乱整个组合列表。在最坏的情况下（如 Knuth），我能够采用 5 次猜测获胜的策略，但平均有 4.451 次猜测获胜。比高德纳好。

是否有任何先前的工作试图平均优于 Knuth 算法，同时保持最坏的情况？到目前为止，我在网上找不到任何迹象。

谢谢！

阿隆

我正在查看 Don Knuth 教授的一些代码，这些代码用 CWEB 编写并转换为 C。一个具体的例子是 dlx1.w，可从Knuth 的网站获得

在某一阶段，结构 nd[cc] 的 .len 值会递减，并且以一种笨拙的方式完成：

（这是一个 Knuth 特有的问题，所以也许您已经知道“o”是一个用于递增“mems”的预处理器宏，它是通过访问 64 位字来衡量的运行总工作量。） “t”中剩余的值绝对不会用于其他任何事情。（这里的例子在 dlx1.w 的第 665 行，或者 dlx1.c 的 ctangle 之后的第 193 行。）

我的问题是：为什么 Knuth 会这样写，而不是

他确实在其他地方使用过（dlx1.w 的第 551 行）：

（并且“oo”是一个类似的宏，用于将“mems”递增两次——但这里有一些微妙之处，因为 .len 和 .aux 存储在同一个 64 位字中。将值分配给 S.len 和 S。 aux，通常只会计算一次 mems 的增量。）

我唯一的理论是递减由两个内存访问组成：首先是查找，然后是分配。（对吗？）这种写法是对这两个步骤的提醒。这对 Knuth 来说会异常冗长，但也许这是本能的备忘录而不是说教。

对于它的价值，我在CWEB 文档中进行了搜索，但没有找到答案。我的问题可能更多地与 Knuth 的标准做法有关，我正在一点一点地学习。我会对将这些实践作为一个整体进行布局（并且可能受到批评）的任何资源感兴趣——但现在，让我们专注于 Knuth 以这种方式编写它的原因。

在 MIX 计算机中，一个字由五个字节和一个符号组成。符号在记忆中是如何表示的？它是另一个字节，所以每个字真的是六个字节吗？

谢谢。

我在这里找到了一个声明，即数独的算法 X具有 O(N^3) 时间复杂度，其中 N 是棋盘大小。

这可能是合乎逻辑的，因为对于数独，要计算的二进制矩阵有 N^3 行。但这使得数独问题可以在多项式时间内解决，而数独被称为 NP 问题，这意味着（据我所知）

• 不可能总是在多项式时间内求解

• 可以在多项式时间内验证解决方案

那么算法 X 的数独时间复杂度是多少，是否有可能在多项式时间内解决数独问题？

谢谢！

我已经实现了Knuth 的“Dancing Links”算法来探索广义精确覆盖问题（即，使用辅助列）。对于精确覆盖（即所有列都是主列），代码按预期工作，因此对于简单的稀疏矩阵：

我的代码返回以下一组行作为解决方案：

而且我还用许多其他确切的封面示例对此进行了测试，并进行了检查。但是，关于辅助列的细节有点模糊。根据我从各种Knuth /非 Knuth资源中收集到的信息，它表明您需要做的是：

唯一的区别是我们通过只为主要列制作列标题的循环列表来初始化数据结构。每个辅助列的标题应具有简单地指向自身的 L 和 R 字段。该算法的其余部分与以前完全相同，因此我们仍将其称为算法 DLX。

在对矩阵/节点/标题的表示方式进行了这些更改，然后将第一列设置为辅助列（即，只有第 2 列和第 3 列是主要列）之后，我最终得到了以下几组行作为解决方案：

虽然所有这些都是有效的解决方案，并且有些与精确的精确覆盖解决方案重叠，但似乎缺少其他解决方案（即，来自精确覆盖解决方案集中的一些解决方案）：

也许这是我的一个误解，但我是否在概念上遗漏了一些东西，或者 Knuth 的解释不完整？

如果你能证明你的算法产生了完整的解决方案，这甚至会很有帮助，这将帮助我确认我的算法是不完整的！

不幸的是，即使是Knuth 关于舞蹈链接的“计算机编程艺术”似乎也没有提供太多帮助。

我似乎记得曾经阅读过 tAOCP 分册之一 Knuth 关于计算整数商和余数的讨论。我的记忆是，他声称没有另一个就不可能计算一个，并且他认为结果都应该提供给程序员。问题是大多数编程语言都强制程序员计算 q = a/b 然后 r = a%b 之类的东西，但实际上 CPUB 做了两次相同的计算，这是一种浪费。

我刚刚在 MMIX Volume Fascicle 1 在第 1.3.1 节中对 DIV 的描述中进行了搜索，但我没有找到我似乎记得的讨论。

有人可以告诉我他们是否记得类似的讨论，我可以在哪里找到它？

我希望在 R中实现类似于Knuth 的算法 X的东西。

问题：我有anxk 矩阵A，n>=k，实值条目代表成本。一般来说，n 和 k 都会非常小（n<10，k<5）。我想找到行到列的映射，以最小化矩阵的总成本，受限于不能使用单行两次的约束。

我认为这有点像算法 X，因为一个合理的方法似乎是：

1. 在 A 中选择一列并找到其中的最小值。
2. 删除该行和该列。现在你只剩下Asub了。
3. 转到第 1 步并使用 Asub 和新列选择重复，直到 ncol(Asub)=1。

但是我不知道如何在 R 中创建一个递归数据结构来存储单元级成本的结果树。到目前为止，这是我所拥有的，它只使它下降了一个分支，因此找不到最佳解决方案。

我确定我在如何处理 R 函数中的递归方面缺少一些基本知识。如果这个算法实际上不是最合适的，我也很高兴听到解决这个问题的其他方法。