9

我一直在从事一项看似简单但让我发疯的任务。因此，如果您喜欢编程挑战……请继续阅读。

我希望能够采用一个数字范围，例如 [1:20] 并使用类似于二进制 serach 算法的机制打印值。因此，首先打印最低值（在本例中为 1），然后是中间值（例如在本例中为 10），然后将范围分成四等份并打印 1/4 和 3/4 处的值（在本例中为 5和 15) 然后分成八等份，直到打印出范围内的所有值。

这个应用程序（这里实际上没有必要理解）是用于内存页面访问机制，当首先在中间范围访问页面时，该机制的行为会更有效。

对于这个问题，采用任何数字范围并以上述方式打印值就足够了。

对此有什么想法吗？一个伪代码解决方案就可以了。我会对此进行尝试，但到目前为止我所尝试的一切都没有减少它。谢谢。

更新：根据要求，示例 [1:20] 的所需输出将是这样的：1、10、5、15、3、7、12、17、2、4、6、8、11、13、 16、18、9、19、20

根据所使用的算法，该输出可以以许多类似的方式呈现。但是，这个想法是首先显示半值，然后是四分之一，然后是八分之一，然后是 16 分等，而忽略先前呈现的值。

4

4 回答 4

10

这是一些产生与您的示例类似的输出的 Python 代码：

def f(low, high):
    ranges = collections.deque([(low, high)])
    while ranges:
        low, high = ranges.popleft()
        mid = (low + high) // 2
        yield mid
        if low < mid:
            ranges.append((low, mid))
        if mid + 1 < high:
            ranges.append((mid + 1, high))

例子：

>>> list(f(0, 20))
[10, 5, 15, 2, 8, 13, 18, 1, 4, 7, 9, 12, 14, 17, 19, 0, 3, 6, 11, 16]

该low, high范围不包括端点，这是 Python 中的约定，因此结果包含从 0 到 19 的数字。

该代码使用 FIFO 来存储仍需要处理的子范围。FIFO 以全范围初始化。在每次迭代中，弹出下一个范围并产生中点。然后，如果当前范围的下子范围和上子范围非空，则将它们附加到 FIFO。

编辑：这是 C99 中完全不同的实现：

#include <stdio.h>

int main()
{
    const unsigned n = 20;
    for (unsigned i = 1; n >> (i - 1); ++i) {
        unsigned last = n;    // guaranteed to be different from all x values
        unsigned count = 1;
        for (unsigned j = 1; j < (1 << i); ++j) {
            const unsigned x = (n * j) >> i;
            if (last == x) {
                ++count;
            } else {
                if (count == 1 && !(j & 1)) {
                    printf("%u\n", last);
                }
                count = 1;
                last = x;
            }
        }
        if (count == 1)
            printf("%u\n", last);
    }
    return 0;
}

这通过使用一些技巧来确定一个整数是否已经在较早的迭代中出现，从而避免了 FIFO 的必要性。

您也可以轻松地在 C 中实现原始解决方案。由于您知道 FIFO 的最大大小（我猜它类似于 (n+1)/2，但您需要仔细检查），您可以使用环形缓冲区保存排队的范围。

编辑 2：这是 C99 中的另一个解决方案。它被优化为只进行一半的循环迭代，并且只使用位运算和加法，没有乘法或除法。它也更简洁，并且它不包含0在结果中，因此您可以按照最初的意图在开始时进行此操作。

for (int i = 1; n >> (i - 1); ++i) {
    const int m = 1 << i;
    for (int x = n; x < (n << i); x += n << 1) {
        const int k = x & (m - 1);
        if (m - n <= k && k < n)
            printf("%u\n", x >> i);
    }
}

（这是我从一开始就打算编写的代码，但我花了一些时间来理解它。）

于 2012-08-08T18:41:19.933 回答
0

Hmmm... you're basically looking for some kind of space-filling curve of sorts. I'm almost certain that you can do that with clever bit-twiddling. You might like to take a look at the way indices are computed for the Morton Z-order or Ahnentafel indexing that's used in some cache-oblivious stencil algorithms. I had a look at this some years ago, and the indexing was similar to what you're describing and done with bit-twiddling.

于 2012-08-08T18:57:47.927 回答
0

二进制堆作为数组已经具有这种结构。您可能希望以这种形式存储数组并按顺序打印。对于节点i，孩子是2i + 1，2i + 2。

于 2012-08-08T18:51:41.067 回答
0

1/2 很容易，对吧？

那么为什么不递归地做呢，使得 1/4 是 1/2 的 1/2，而 1/8 是 1/4 的 1/2？

于 2012-08-08T20:27:00.447 回答