問題タブ [hamming-numbers]

素因数が2、3、または5しかない数は、醜い数と呼ばれます。

例：

1は2^0と見なすことができます。

私はn^番目の醜い数を見つけることに取り組んでいます。これらの数値は、n大きくなるにつれて非常にまばらに分布することに注意してください。

与えられた数が醜いかどうかを計算する簡単なプログラムを書きました。のためn > 500に-それは超遅くなりました。私はメモ化を使用してみました-観察：、、ugly_number * 2はugly_number * 3すべてugly_number * 5醜いです。それでも遅いです。logのいくつかのプロパティを使用してみましたが、乗算から加算までこの問題が軽減されるためですが、まだあまり運がありません。これを皆さんと共有することを考えました。面白いアイデアはありますか？

エラトステネスのふるいに似た概念を使用する（アノンに感謝）

in^番目の醜い数です。

これでもかなり遅いです。私は1500^番目の醜い番号を見つけようとしています。

私の友人が就職の面接を受けています。インタビューの質問の 1 つを考えさせられました。

i と j の 2 つの負でない整数があります。次の方程式が与えられると、出力がソートされるように i と j を反復処理する (最適な) 解を見つけます。

したがって、最初の数ラウンドは次のようになります。

いくらやってもパターンが見えない。あなたの考え？

式では

2 ^× *3年^* 5^年

x、yおよびは、z負でない整数値 (>=0) を取ることができます。

したがって、関数は一連の数値を生成します1,2,3,4,5,6,8,9,10,12,15,16....

• 私はブルートフォースソリューションを持っています。
• 基本的には、1 から始まるループを反復し、各反復で、現在の数値係数が 2、3、または 5 のセットのみからのものかどうかを確認します。

私が持ちたいのは、エレガントなアルゴリズムです。

これはインタビューの質問です。

重複の可能性:
n 番目の醜い数
式 (2^x)*(3^y)*(5^z) の K 番目に小さい数を見つける

この問題を迅速かつエレガントな方法で解決する方法を考えています。

2^x * 3^y * 5^z; の形式で記述できるすべての数値nを「醜い」と定義します。ここで、x、y、z は自然数です。1500 番目の醜い数を見つけます。

たとえば、最初の「醜い」数字は次のとおりです。

この方法で、ブルートフォースを使用してこの問題を解決しようとしました。

しかし、それにはかなりの時間がかかるため、より迅速でより良い解決策を見つけたいと考えています。

醜い数の素因数は知っていますが、これらの数を正しい順序で生成する方法が思いつきません。

すべての数字をチェックすることなく、これらの数字を生成する方法が必要だと思います。問題は、素因数の指数が非常にランダムに分布しているように見えることです。

この表を見てください：

ご覧のとおり、x、y、z の値は規則に従っていないようです。

あなたの誰かがこの問題の解決策を見つけることができますか?

問題をさまざまな部分に分割しようと考えています。問題は指数のランダム性によって決定されるため、2s、3s、5s の累乗を個別に生成してから、2^x*3^y、2^x*5^z などの形式の数値を生成することができます。最終的にそれらをまとめましたが、これで問題が解決するかどうかはわかりません。

規則的な数は、60 の累乗を均等に分割する数です。例として、60 ² = 3600 = 48 × 75 であるため、48 と 75 は両方とも 60 のべき乗の約数です。したがって、これらも規則的な数です。

これは、次の 2 の累乗への切り上げの拡張です。

大きな素因数を含む可能性のある整数値Nがあり、小さな素因数 (2、3、および 5) のみで構成される数値に切り上げたい

例:

• f(18) == 18 == 21 * 32
• f(19) == 20 == 22 * 51
• f(257) == 270 == 21 * 33 * 51

この要件を満たす最小の数を見つける効率的な方法は何でしょうか?

関連する値は大きい可能性があるため、1 から始まるすべての通常の数値を列挙したり、すべての可能な値の配列を維持したりすることは避けたいと思います。

私は素数のセットを持っており、それらの素因数のみを昇順で使用して整数を生成する必要があります。

たとえば、セットがp = {2、5}の場合、整数は1、2、4、5、8、10、16、20、25、…</p>になります。

この問題を解決するための効率的なアルゴリズムはありますか？

Haskell でハミング数を生成しようとしています。問題は、出力リストに重複した # が表示され、その理由が正確にわからないことです。重複削除機能を作成するだけですか、それとも単純なものが不足していますか?

また、関数 hamming では、入力リストのサイズが正確に 3 であることを確認したいのですが、リストのサイズを見つけて比較を行うにはどうすればよいですか?

これは、私のコースの1つでの宿題に関するプログラミングの質問です。私は2、3年プログラムを作成しておらず、そもそもそれほど素晴らしかったです。現在、速度を上げるためにチュートリアルを行っていますが、しばらく時間がかかります。あなたたちがこの問題で私を助けることができれば、私は本当にそれをいただければ幸いです。

制約：

このシーケンスの各項は、次の形式の正の整数2^i*3^j*5^kですi, j, and k。 i + j + k >= 1.

配列は使用できません。この問題を解決するためのアルゴリズムには、リストの作成とマージを繰り返す必要があります。具体的には5 lists; a final list, temp list, and three term lists。

「最終的なリストは、現在の一時リストとマージされることによって大きくなります。一時リストは、3つの用語リストのマージによって置き換えられます。新しい用語リストは、新しい一時リストに2, 3, and 5 respectively「」を掛けることによって生成されます。

目的のシーケンスは次のようになります。2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, . . .

（これはエキサイティングです！）私は知っています、主題はよく知られています。ハミング数の無制限の増加シーケンスを、重複や省略なしに効率的に生成するための最新技術（Haskellおよび他の言語）は、長い間次のとおりです（AFAIK-そしてところで、元のEdsgerDijkstraのコードと同等です）それも）：

私が尋ねている質問は、重要な手段でそれをより効率的にする方法を見つけることができるかということです。それはまだ最先端の技術ですか、それとも実際にこれを改善して2倍速く実行し、より良い経験的な成長順序で起動することは可能ですか？

答えが「はい」の場合は、コードを表示し、上記と比較した場合の速度と経験的な成長順序について話し合ってください（~ n^1.05 .. n^1.10最初の数十万の数が生成されます）。また、存在する場合、この効率的なアルゴリズムを拡張して、任意の素数のセットで滑らかな数のシーケンスを生成できますか？

素数2、3、5を使用してシーケンスを生成し、シーケンスのn番目の数値を表示するという問題に取り組んでいます。したがって、プログラムに1000番目の数値を表示するように要求すると、それが表示されるはずです。

基本的な決定とループだけで、配列などを使用することはできません。

私はそれに取り組み始めて壁にぶつかりました...これが私が得たものです：

残念ながら、そのコードは必要なことを実行しません。素数7を含む14などの数値が表示されます。数値は、指定された3つの素数（2、3、5）でのみ除算できます。

私が理解しようとしているいくつかの情報を見つけましたが、それを実装する方法が今のところわかりません...多分たくさんのfor（）ループを使用していますか？したがって、2 ^ n * 3 ^ m * 5 ^ kの概念を使用する必要があるようです。ここで、n + m +k>0です。

最初に2^1 * 3 ^ 0 * 5 ^ 0で完全に割り切れるかどうかを確認し、次に2 ^ 0 * 3 ^ 1 * 5 ^ 0、次に2 ^であるかどうかを確認するテストで、数値を実行する必要があると思います。 0 * 3 ^ 0 * 5^1など...どこから始めればよいかわからない。