3

我有一个以交错顺序绘制线条的程序（分形）。最初，给定H要绘制的线条，它确定帧数，然后每 th 帧N绘制一次N，然后每N+1'th 帧绘制一次，等等。

例如，如果H = 10和N = 3，它会按顺序绘制它们：

0, 3, 6, 9,
1, 4, 7,
2, 5, 8.

但是我不喜欢带子逐渐变厚的方式，在很长一段时间内留下大面积未绘制的区域。因此，该方法被增强为递归地在每组中绘制中点线，而不是立即绘制后续线，例如：

0, (32)          # S (step size) = 32
8, (24)          # S = 16
4, (12)          # S = 8
2, 6, (10)       # S = 4
1, 3, 5, 7, 9.   # S = 2

（括号中的数字超出范围，未绘制。）算法非常简单：

Set S to a power of 2 greater than N*2, set F = 0.
While S > 1:
    Draw frame F.
    Set F = F + S.
    If F >= H, then set S = S / 2; set F = S / 2.

当奇数帧在最后一个步长上绘制时，它们以简单的顺序绘制，就像初始（烦人的）方法一样。每四帧也是如此，等等。这还不错，因为已经绘制了一些中间帧。

但是相同的排列可以递归地应用于每个步长的元素。在上面的示例中，最后一行将更改为：

1,      # the 0th element, S' = 16
9,      # 4th, S' = 8
5,      # 2nd, S' = 4
3, 7.   # 1st and 3rd, S' = 2

前面几行元素太少，递归无法生效。但如果N足够大，某些行可能需要多级递归。任何具有 3 个或更多对应元素的步长都可以递归排列。

问题 1.这种元素排列是否有一个通用名称N，我可以用它来查找其他材料？我也对可能存在的任何类似示例感兴趣。如果我是第一个想要这样做的人，我会感到惊讶。

问题 2.我可以使用一些技术来计算它吗？我在 C 领域工作，但现阶段我对算法级别更感兴趣；我很高兴阅读其他语言的代码（在合理范围内）。

我还没有解决它的实施问题。我希望我会先预先计算排列（与上面的前一种方法的算法相反）。但我也很感兴趣，是否有一种简单的方法可以让下一帧绘制而无需预先计算，其复杂性与前一种方法相似。

4

1 回答 1

3

听起来好像您正在尝试构建一维低差异序列。您的排列可以通过反转索引的二进制表示来计算。

def rev(num_bits, i):
    j = 0
    for k in xrange(num_bits):
        j = (j << 1) | (i & 1)
        i >>= 1
    return j

示例用法：

>>> [rev(4,i) for i in xrange(16)]
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

适用于一般 n 的变体：

def rev(n, i):
    j = 0
    while n >= 2:
        m = i & 1
        if m:
            j += (n + 1) >> 1
        n = (n + 1 - m) >> 1
        i >>= 1
    return j

>>> [rev(10,i) for i in xrange(10)]
[0, 5, 3, 8, 2, 7, 4, 9, 1, 6]
于 2011-11-18T02:01:00.793 回答