标签: knuth

我必须使用元素之间的最小数量的比较来模拟在python中对5个元素的列表进行排序的执行计划.除此之外,复杂性无关紧要.

结果是一个对列表,表示在另一个时间对列表进行排序所需的比较.

我知道有一种算法可以在7次比较中实现这一点(元素之间,总是,不是复杂性),但我找不到可读(对我而言)的版本.

如何对7个比较中的5个元素进行排序,并为排序构建"执行计划"？

PD:不是作业.

我希望能够学习 MIX/MMIX，但我不知道用来编写它的工具链。我过去曾使用 uVision 来处理 ARM 汇编器相关的事情，对于 MIX/MMIX 是否存在这样的等效项？

有人可以向我解释MIX中的划分(来自Knuth的TAOCP)是如何在字节到字节的基础上工作的？

rA = |-| . . . .0| 

rX = |+|1235|0|3|1|

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

执行操作时

DIV 1000

寄存器变成了

rA = |+|0|617|?|?|

rX = |-|0|0|0|?|1|

现在我明白上的标志rA和rX,但以什么顺序的字节rAX填充和部门完成？

如果DIV 1000导致每一位除以2,那么我会期待

rAX = |+|617|0|1|0|-|0|1|0|1|1| 

其中rA包含除法结果和rX余数(从右侧填充).

我可能在这里遗漏了一些东西,而Knuth似乎认为我应该能够自己解决这个问题(因此关于它的10级问题,我也没有得到),但有人可以帮助我吗？

我很抱歉,如果我的问题听起来很愚蠢,因为我的数据结构理解不是很好.

我一直在阅读Knuth的Dancing Links算法,并且非常了解它基本上是如何工作的.提到跳舞链接的数据结构可视化看起来像一个包含列和行的表,每个单元格连接到它们的上,下,左和右单元格.我还读到在这个算法中使用循环双链表.

我想知道的是,如何将双链表放入带有列和行的表中？

据我所知,大多数双链表只有2个指针(向上和向下),这是否意味着我必须制作我自己的自定义链表,它有4个指针(向上,向下,向左和向右)？或者还有其他方法吗？

提前致谢.

我一直在阅读 Donald Knuth 的《编程艺术》第一卷，其中使用 MIX 作为汇编语言。在Knuth讲MIX中算术运算的部分，我不明白减法、乘法和除法运算是如何进行的。

例如，课本上有这样的内容：

寄存器 A 具有以下字代码：-| 1234 | 0 | 0 | 9且存储器单元（例如 M）具有以下字代码：-| 2000 | 150 | 0。

书上说执行 AM 的结果是：+| 766 | 149|?。

在 MIX 中，内存被分成单词。每个字具有以下内容： 第一个字段表示符号（+ 或 -）
接下来的两个字节保存地址。
下一个字节表示索引，而第五个字节用于字段规范。
最后一个字节用于操作码。
书上说执行 AM 的结果是：+| 766 | 149|?。

谁能帮我这个？

我想了解 Knuth\xe2\x80\x93Morris\xe2\x80\x93Pratt 算法的工作原理。我在普林斯顿大学观看了本教程https://www.youtube.com/watch?v=iZ93Unvxwtw。在此视频中，他们使用一个表格，其中字母表长度 = 行数，模式长度 = 列数。将该表视为 DFA，用于检测文本中的模式。我认为这种方法很有趣，但维基百科说 Knuth\xe2\x80\x93Morris\xe2\x80\x93Pratt 算法使用一个前缀表，其中只有一行前缀的长度。两者都有效，并且两者的速度都是 O(n+m)（n 是文本的长度，m 是模式的长度）。但DFA版本需要更多空间。但问题是哪个是真正的 Knuth\xe2\x80\x93Morris\xe2\x80\x93Pratt 算法，哪个是微分？

我无法弄清楚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).

有人可以提供一个使用 Knuth 序列的 Java 中 shellsort 的简单工作示例吗？我在互联网上查看了几个地方，但找不到适合我的解释。我在概念层面上理解 shellsort - 因为它是一种插入排序，它是在一个间隙上完成的，这个间隙随着时间的推移而缩小，直到达到 1 的间隙 - 这本质上是一种插入排序。然而，Knuth 序列是 (k * 3 - 1)/2 并且前几个间隙的列表通常表示为 [1, 4, 13, 40, 121.. 等等]。

我的问题是这将如何实施？起始间隙实际上是 1，还是这个序列在它大于被排序列表的大小之前生成的值？如果差距从 1 开始，如果我正确理解 shell 排序，目的就会失败。有人可以解释一下吗？我觉得我错过了一些对理解这件事至关重要的东西。

提前致谢。

在计算机科学中，精确覆盖问题是确定是否存在精确覆盖的决策问题。精确覆盖问题是 NP-完全问题[1]，是 Karp 的 21 个 NP-完全问题之一。[2] 精确覆盖问题是一种约束满足问题。

我一直在阅读精确覆盖问题的示例，例如 n-queens、sudoku 等，但似乎无法理解问题是如何精确的。

我正在尝试用 Java 实现 Knuth 的 Dancing Links 算法。

根据 Knuth 的说法，如果x是一个节点，我可以通过 C 中的以下操作完全取消链接节点：

L[R[x]]<-L[x]
R[L[x]]<-R[x]

并通过以下方式恢复取消链接：

L[R[x]]<-x
R[L[x]]<-x

我的主要方法中做错了什么？

Java中如何实现取消链接和恢复？

这是我的主要方法：

      ///////////////

      DoublyLinkedList newList = new DoublyLinkedList();

      for (int i = 0; i < 81; i++) {
        HashSet<Integer> set = new HashSet<Integer>();
        set.add(i);
        newList.addFirst(set);
      }

      newList.displayList();

      // start at 69
      newList.getAt(12).displayNode();

      //HOW TO IMPLEMENT UNLINK?
      //newList.getAt(12).previous() = newList.getAt(12).next().previous().previous();
      //newList.getAt(12).next() = newList.getAt(12).previous().next().next();

      newList.displayList();

      //HOW TO IMPLEMENT REVERT UNLINK?
      //newList.getAt(12) = newList.getAt(12).next().previous();
      //newList.getAt(12) = newList.getAt(12).previous().next();

      System.out.println();

      ///////////////

这是 DoubleLinkedList 类： …