3

我正在玩 Project Euler 的Problem 220，我对 Wikipedia 关于该主题的文章Dragon Curve有点困惑。关于无需绘制整条曲线即可计算第 n 个转弯方向的主题，它说：

首先，以 k * 2^m 的形式表示 n，其中 k 是奇数。第n 圈的方向由k mod 4 决定，即k 除以4 的余数。如果k mod 4 为1，则第n 圈为R；如果k mod 4 为1，则第n 圈为R。如果 k mod 4 为 3，则第 n 轮为 L。

例如，要确定转弯 76376 的方向：

76376 = 9547 x 8.
9547 = 2386x4 + 3
so 9547 mod 4 = 3
so turn 76376 is L
  • 除了检查 2 的连续幂的可分性之外，是否有一种聪明的方法可以确定 n 是否可以表示为 k2^m？
  • 如果 n 不能以这种方式表达，这意味着什么？

（问题涉及计算长度为 2^50 的龙曲线上的点的位置，因此实际绘制曲线是不可能的。）

4

2 回答 2

3

m 是数字最低有效端的零位数。最简单的算法是只要数字是偶数就除以 2，但您也可以使用二进制搜索来加快速度。

所有整数都可以用这种方式表示。

于 2008-12-29T19:42:21.380 回答
1

任何整数都可以表示为 k * 2^m，其中 k 是奇数。要了解原因，请以二进制形式写入任意数字。从右边（最低有效位）开始，将有一个全为零的字符串。它可能是一个空字符串。零的数量是 m。其余位组成 k。k 的最低有效位是一个（因为如果它是一个零，你只需扩展你的零字符串），所以 k 是奇数。

要找到 k 和 m，您可能会编写一个简单的循环（在本例中为 Python）：

def k_and_m(n):
    k, m = n, 0
    while (k % 2) == 0:
        k >>= 1
        m += 1
    return k, m
于 2008-12-29T20:05:45.683 回答