-3

我正在阅读 Robert Sedwick 的算法。

这里是书

页码：214。

下面的文字参考了数字的二进制表示。

在这里，Robert Sedwick 提到以下程序的灵感来自与二进制数的对应关系。绘制标尺的非递归程序如下所述

void rule(int l, int r, int h)
  { 
    for (int t = 1, j = 1; t <= h; j += j, t++)
      for (int i = 0; l+j+i <= r; i += j+j)
        mark(l+j+i, t);
  }

在图 5.10 中，作者提到要以非递归方式绘制尺子，我们交替使用长度为 1 的绘图标记和跳过位置，然后交替使用长度为 2 的绘图标记和跳过剩余位置，依此类推。

我在上面有以下问题。

  1. 我的问题是作者如何提到该程序是受二进制数对应的启发？
  2. 图 5.10 中作者跳位是什么意思？这里指的是什么职位？
  3. Fig5.10 中第一图中的标记是什么？

请用规则（0,8,3）解释。

4

2 回答 2

1

对于#1，如果你用二进制写下一系列数字，并屏蔽除低 x 位之外的所有内容，你会得到一个重复模式（例如 x=4）：

 0 = 0000
 1 = 0001
 2 = 0010
 3 = 0011
 4 = 0100
 5 = 0101
...
14 = 1110
15 = 1111
16 = 0000
17 = 0001
...

如果您查找以 1 字符串结尾的数字，您会看到一个有趣的模式。将上面逆时针旋转90度以节省空间：

010101010101010101010101010101010101010101010101
001100110011001100110011001100110011001100110011 ....
000011110000111100001111000011110000111100001111
000000001111111100000000111111110000000011111111

（仅）用 ! 替换 1 的结尾字符串：

0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!0!
001!001!001!001!001!001!001!001!001!001!001!001! ....
0000111!0000111!0000111!0000111!0000111!0000111!
000000001111111!000000001111111!000000001111111!

用空格替换其他所有内容，您会得到一个重复的标尺图案。

 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
   !   !   !   !   !   !   !   !   !   !   !   ! ....
       !       !       !       !       !       !
               !               !               !

如果您考虑一下，您会看到 1 的字符串的长度（对应于标记的长度）如何对应于它的出现频率以及它如何导致上述模式。

于 2012-09-10T19:15:14.970 回答
0

我觉得这里遗漏了什么是这篇文章的作者，而不是读者。书中发布的代码缺少注释 - 特别是 @param 标记以准确指示三个参数的含义。发布的解释似乎也缺少一些东西。

这是我对 #2 的猜测：当您查看尺子时，0.5 英寸的标记比 0.25 或 0.75 英寸的标记更大。所以首先我们可以放置半英寸标记，然后当我们放置 1/4" 标记时，我们会“跳过位置”，因为不需要绘制一半的 1/4" 标记。例如，当我们填写 1" 和 3" 之间的标记时，按 1/4" 计数，我们有：

1.25 [跳过] 1.75 [跳过] 2.25 [跳过],,...

换句话说，当放置 1/4" 标记时，我们实际上是按 0.5" 而不是四分之一来计算的。在书中发布的代码中，这可能就是您j+j在内部循环中看到的原因。这表明 j 是当前标记值（先是 1/4，然后是 1/2，然后是 1/8）。由于一切都是用整数完成的，也许 j=1 对应于 1/16"，然后 2j、4j、8j 是标记值。

于 2012-09-10T10:58:03.733 回答