4

64ビット長整数として表すことができるすべての完全な累乗を出力するにはどうすればよいですか：4、8、9、16、25、27、...。完全な累乗は、整数aのabとして記述できる数値です。 b≥2。これは宿題の問題ではありません。アルゴリズム設計書の就職の面接の質問のセクションで見つけました。ヒント、この章は優先キューに基づいていました。

私が持っているアイデアのほとんどは本質的に二次式であり、64ビットに適合しなくなるまで力を見つけ続けますが、それはインタビュアーが探すものではありません。また、ここでPQがどのように役立つのか理解できません。

4

3 に答える 3

4

パワーごとに1つのエントリを持つ小さな優先キューを使用することは、数値を一覧表示するための合理的な方法です。次のPythonコードを参照してください。

import Queue             # in Python 3 say:  queue
pmax, vmax = 10, 150
Q=Queue.PriorityQueue(pmax)
p = 2
for e in range(2,pmax):
    p *= 2
    Q.put((p,2,e))

print 1,1,2
while not Q.empty():
    (v, b, e) = Q.get()
    if v < vmax:
        print v, b, e
        b += 1
        Q.put((b**e, b, e))

上記のコードのようにpmax、vmaxを使用すると、次の出力が生成されます。提案された問題については、pmaxandvmaxを64andに置き換え2**64ます。

1 1 2
4 2 2
8 2 3
9 3 2
16 2 4
16 4 2
25 5 2
27 3 3
32 2 5
36 6 2
49 7 2
64 2 6
64 4 3
64 8 2
81 3 4
81 9 2
100 10 2
121 11 2
125 5 3
128 2 7
144 12 2

このメソッドの複雑さはO（vmax ^ 0.5 * log（pmax））です。これは、完全な正方形の数が完全な立方体、4乗などの数よりも支配的であり、各正方形に対してO（log（pmax））作業を実行して操作getをputキューに入れるためです。より高いパワーの場合、計算時にO（log（pmax））の作業を行いますb**e。

の場合vmax,pmax =64, 2**64、約2 *（2 ^ 32 + 2 ^ 21 + 2 ^ 16 + 2 ^ 12 + ...）のキュー操作、つまり約2^33のキュー操作があります。

追加のメモ：このメモは、cf16のコメント、「1つのコメントのみ、「完全な立方体の数、4乗などの数よりも完全な正方形の数が支配的であるとは思わない」に対応しています。それらはすべて無限です。しかし、そうです、有限集合を考えれば」。物事の全体的な数学的スキームにおいて、カーディナリティは同じであることは事実です。つまり、が整数のすべての'乗P(j)のセットである場合、すべての整数のカーディナリティ。任意の2セットのパワーの要素は、互いに1対1で対応させることができます。jP(j) == P(k)j,k > 0

それにもかかわらず、昇順で完全な累乗を計算する場合、有限であるかどうかに関係なく、計算される数に関係なく、正方形を提供する作業が他の累乗の作業を支配します。任意のxについて、 xの領域の完全なk乗の密度は、 kが増加するにつれて指数関数的に減少します。xが増加すると、 xの領域の完全なk乗の密度は（ x 1 / k）/ xに比例します。したがって、 xが増加すると、3乗、4乗などは、二乗に比べてほとんどなくなります。

具体的な例として、1e8と1e9の間の累乗の中で、（2; 3; 4; 5; 6）の累乗の数は約（21622; 535; 77; 24; 10）です。1e8と1e9の間には、正方形よりも高い累乗のインスタンスの30倍以上の正方形があります。2つの数の間の完全な平方の数と、より高い完全な累乗の数の比率は次のとおりです。10¹⁰–10¹⁵、r≈301; 10¹⁵–10²⁰、r≈2K; 10²⁰–10²⁵、r≈15K; 10²⁵–10³⁰、r≈100K。要するに、xが増加するにつれて、累乗が昇順で提供される場合、正方形がますます支配的になります。

于 2012-10-19T06:38:47.970 に答える
2

優先度付きキューは、たとえば、出力の重複を避けたい場合、または特にソートされた値を一覧表示したい場合に役立ちます。

多くの場合、優先キューは並べ替えに置き換えることができ、その逆も可能です。したがって、 a bのすべての組み合わせを生成してから、結果を並べ替えて、隣接する重複を削除することができます。このアプリケーションでは、姉妹の回答の1つが示すように、このアプローチはわずかですが、劇的にメモリ効率が悪いとは言えません。

重複を削除することができれば、優先キューは並べ替えよりも優れている可能性があります。または、結果全体をメモリに保存して処理することを避けたい場合。他の姉妹の答えは後者の例ですが、わずかな変更で両方を簡単に行うことができます。

ここでは、最大16 GBのRAMを使用するアレイと、最悪の場合数キロバイトを使用する64未満のアイテムを含むキューとの違いが生じます。このようなメモリ消費量の大きな違いは、RAMアクセス時間とキャッシュアクセス時間の違いにもつながるため、基になるデータ構造がそれ自体を維持することでオーバーヘッドが発生し、ナイーブアルゴリズムと比較してより多くの命令が必要な場合でも、メモリリーンアルゴリズムははるかに高速になる可能性があります並べ替えを使用します。

入力のサイズは固定されているため、考えた方法が本質的に2次式である可能性は技術的にありません。ネストされたループが2つあると、そのような各ループの上限が入力サイズに比例し、多くの場合それでも比例しないと言えるまで、アルゴリズムは2次式になりません。本当に重要なのは、最も内側のロジックが実際に何回実行されるかです。

この場合、実行可能な定数と実行不可能な定数の間で競合が発生します。

于 2012-10-19T07:05:01.827 に答える
1

優先キューが非常に理にかなっていると私が理解できる唯一の方法は、番号が利用可能になったときに、厳密に昇順で、もちろん番号を2回印刷せずに印刷することです。したがって、素数ジェネレーター（エラトステネスのふるいまたはよりスマートな手法を使用してシーケンス2、3、5、7、11、...を生成する）から始めます。まず、2 ^ 2=4という事実を表すトリプルをキューに入れます。次に、キューから最小のアイテム（べき乗の結果が最小のトリプル）を削除し、それを印刷し、指数を1つ増やして、キューに戻すプロセスを繰り返します（優先順位は新しい結果によって決定されます）。べき乗）。このプロセスを、必要に応じて（p ^ 2が出力される前に）新しい素数を生成するプロセスとインターリーブします。

可能な最大の指数ベースは2^32（2 ^ 32）^ 2 = 2 ^ 64であるため、キュー上の要素の数は2 ^ 32未満の素数の数を超えてはなりません。これは、明らかに203,280,221です。、これは扱いやすい数だと思います。

于 2012-10-19T05:37:19.777 に答える