3

私は Project Euler の問題 220をいじっていますが、ウィキペディアのトピックに関するDragon Curveの記事について少し混乱しています。曲線全体を描画することなく n 番目のターンの方向を計算するトピックについては、次のように述べています。

まず、n を k * 2^m の形式で表現します。ここで、k は奇数です。n 番目のターンの方向は、k mod 4、つまり k を 4 で割ったときの余りによって決定されます。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
  • n がk2^m として表現できるかどうかを判断する賢い方法はありますか?
  • n がこのように表現できないとはどういう意味ですか?

(この問題は、長さ 2^50 のドラゴン曲線上の点の位置を計算するため、実際に曲線を描くことは問題外です。)

4

2 に答える 2

3

m は、数値の最下位にある 0 ビットの数です。最も単純なアルゴリズムは、数が偶数である限り 2 で割ることですが、二分探索を使用して高速化することもできます。

すべての整数はこの方法で表現できます。

于 2008-12-29T19:42:21.380 に答える
1

任意の整数は、k * 2 ^ mとして表すことができます。ここで、kは奇数です。理由を確認するには、任意の数値を2進数で記述します。右（最下位ビット）から始めて、すべてゼロの文字列があります。空の文字列である可能性があります。ゼロの数はmです。残りのビットはkを構成します。kの最下位ビットは1であるため（ゼロの場合は、ゼロの文字列を拡張するだけなので）、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 に答える