問題タブ [hamming-numbers]

重複の可能性：
素数2、3、および5のみを使用してシーケンスを生成し、n番目の項を表示する（C ++）

私はこれについてずっとブレインストーミングをしてきましたが、これを理解することはできません。次の問題を解決する必要があります。

次のシーケンスを生成し、シーケンスのn番目の項を表示します

2,3,4,5,6,8,9,10,12,15など....シーケンスには素数2、3、5のみがあります

while、for、ifなどの基本的なC++を使用する必要があります。特別なことは何もありません。配列についてよく知らないという理由だけで配列を使用することはできません。また、ソリューションのコードを理解したいと思います。

私は完全な解決策を求めているのではありませんが、これを乗り越えるためのガイダンスを求めています...お願いします。

私の問題は、シーケンス内の数が2、3、および5以外の他の素数で割り切れるかどうかを確認する方法がわからないことです。

また、次のように番号を確認しているとしましょう。

素数7で割ることができる14などの数を生成するという事実だけでは機能しません。したがって、そのシーケンスが2、3、およびで割り切れるだけであることを確認する方法を理解する必要があります。 5 .....私は問題の解決策を含む多くの資料をオンラインで見つけましたが、それらの解決策はあまりにも進んでおり、私はそれらを使用できません（それらのほとんどは他の言語で書かれています... C ++）。もっと簡単な方法があると思います。

私はPython3の機能容量で遊んでおり、ハミング数を計算するための古典的なアルゴリズムを実装しようとしました。これが素因数として2、3、または5しかない数です。最初のハミング数は2、3、4、5、6、8、10、12、15、16、18、20などです。

私の実装は次のとおりです。

マージが機能しないように見えるという問題。その前に、私はエラトステネスのふるいを同じ方法で実装しました、そしてそれは完全にうまくいきました：

これは私のマージ操作と同じテクニックを使用しています。ですから違いはわかりません。あなたはなにか考えはありますか？

（これらはすべて他の方法で実装できることを知っていますが、クラス宣言や特別なビルド済みPython関数を使用せずに、Pythonのジェネレーターと再帰を含む純粋な関数型機能を正確に理解することを目標としています。）

UPD：Will Nessの場合、LISP（実際にはRacket）でのこのアルゴリズムの実装は次のとおりです。

素因数が2、3、5、ハミング数だけの数のリストを定義する必要があります。（つまり、2 ^ i * 3 ^ j * 5 ^ kの形式の番号。シーケンスは1、2、3、4、5、6、8、9、10、12、15、…で始まります）

factors関数を使用して、またはそれ以外の方法でそれを行うことができます。factors以下は、その引数の要素を返す必要があります。正しく実装できたと思います。

リスト内包表記を使用して2^i * 3 ^ j * 5 ^ kのリストを作成しようとしましたが、ガードの記述に行き詰まりました。

ハミング数の無限ストリーム (つまり、すべて正の整数 ) を生成するためのよく知られた解決策がありnますn = 2^i * 3^j * 5^k。これを F# で 2 つの異なる方法で実装しました。最初の方法は を使用しseq<int>ます。ソリューションはエレガントですが、パフォーマンスはひどいものです。2 番目の方法は、末尾が でラップされるカスタム タイプを使用しLazy<LazyList<int>>ます。ソリューションは不格好ですが、パフォーマンスは驚くべきものです。

を使用したパフォーマンスseq<int>が非常に悪い理由と、それを修正する方法があるかどうかを誰かが説明できますか? ありがとう。

を使用した方法 1 seq<int>。

を使用した方法 2 Lazy<LazyList<int>>。

問題 - 2、3、5 でしか割り切れない最初の N 個の数を見つける複雑さは?

私の努力

コード -

複雑さの計算-

ループ 2 の複雑さ- O( ln(i) )、これは、数値が 2 で割り切れるたびに発生し、最終的に 1 に達します。

ループ 1 の複雑さ- O(T)、ここで T は、最初の N 個の数値を取得するために反復する回数です。

したがって、複雑さは ln(i) の合計です。ここで、i = 2 から T です。

factorial(N) は (N)^(3N/2) に正比例することを意味します

上式により、

質問-

1. T を N で表すことはできますか?
2. はいの場合は、それを変換するのを手伝ってください。

免責事項：それについて多くの質問がありますが、一定のメモリを必要とするものは見つかりませんでした。

ハミング数とは、2^i*3^j*5^ki、j、k を自然数とする数です。

O(N)時間とO(1)(定数)メモリでN番目のハミング数を生成する可能性はありますか? 生成とは、正確には生成器を意味します。つまり、結果を出力することしかできず、以前に生成された数値を読み取ることはできません (その場合、メモリは一定ではありません)。ただし、一定数のそれらを保存できます。

たとえば、優先キューに基づいて、定数メモリを使用した最適なアルゴリズムのみが O(N log N) よりも優れていないことがわかります。しかし、O(N) 時間でアルゴリズムを構築することは不可能であるという数学的な証明はありますか?

これは 10 億番目の醜い/ハミング数ですか?

62565096724471903888424537973014890491686968126921250076541212862080934425144389 76692222667734743108165348546009548371249535465997230641841310549077830079108427 08520497989078343041081429889246063472775181069303596625038985214292236784430583 66046734494015674435358781857279355148950650629382822451696203426871312216858487 7816068576714140173718

これを確認できる共有するコードを誰かが持っていますか? ありがとう！

ハミング問題は、基本的に素因数が {2,3,5} のみの整数をすべて生成する有名な問題です。（そして、私が思う素因数の任意のセットに拡張できます）

n 番目のハミング数を見つけるには、Dijkstra による巧妙な O(N) 構築アルゴリズムがあり、その疑似コードは次のとおりです。

この解決策のポイントは、H がハミング数である場合、2H、3H、5H もハミング数であるということです。

ハミング問題に少し似ていると感じましたが、素因数のセットを使用して数を構築していません。代わりに、問題のステートメントをリフェーズすると、次のようになります。

1 は結果セットにあります。H が結果セットにある場合、2H+1 と 3H+1 も結果セットに含まれます。結果セットの n 番目の数値を見つける

次に、この問題に対して同じ構築アルゴリズムが機能するかどうか疑問に思いますが、機能することがわかりました! （そして、なぜそれが機能するのかさえわかりません）

それで、私は疑問に思います：

この構築アルゴリズムは、これらの関数が結果 >= を与える場合、「x結果にある場合はすべて結果にもある」などのルールが与えられた場合、数値を生成する問題に対して機能しますか?f(x), g(x), p(x), q(x)...x