ハミング問題は、基本的に素因数が {2,3,5} のみの整数をすべて生成する有名な問題です。（そして、私が思う素因数の任意のセットに拡張できます）
n 番目のハミング数を見つけるには、Dijkstra による巧妙な O(N) 構築アルゴリズムがあり、その疑似コードは次のとおりです。
List<int> H
int i=0,j=0,k=0, n=10 // find the 10-th hamming number
H.add(1)
for(i=0 to 10)
int next = min(2*H[i], 3*H[j], 5*H[k])
H.add(next)
if(next == 2*H[i]) ++i
if(next == 3*H[j]) ++j
if(next == 5*H[k]) ++k
output(H[10])
この解決策のポイントは、H がハミング数である場合、2H、3H、5H もハミング数であるということです。
ハミング問題に少し似ていると感じましたが、素因数のセットを使用して数を構築していません。代わりに、問題のステートメントをリフェーズすると、次のようになります。
1 は結果セットにあります。H が結果セットにある場合、2H+1 と 3H+1 も結果セットに含まれます。結果セットの n 番目の数値を見つける
次に、この問題に対して同じ構築アルゴリズムが機能するかどうか疑問に思いますが、機能することがわかりました! （そして、なぜそれが機能するのかさえわかりません）
Def f(x) 2x+1
Def g(x) 3x+1
List<int> H
int i=0,j=0,n=10 // find the 10-th hamming number
H.add(1)
for(i=0 to 10)
int next = min(f(H[i]), g(H[j]))
H.add(next)
if(next == f(H[i])) ++i
if(next == g(H[j])) ++j
output(H[10])
それで、私は疑問に思います：
この構築アルゴリズムは、これらの関数が結果 >= を与える場合、「x結果にある場合はすべて結果にもある」などのルールが与えられた場合、数値を生成する問題に対して機能しますか?f(x), g(x), p(x), q(x)...x