汉明问题是一个著名的问题，它基本上生成所有质因数仅为{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？
一个充分条件是从整数到整数的所有f_i函数必须是单调递增的，并且对所有i和n都具有n < f_i(n)。
证明您需要规则的整数部分之类的东西的示例是(n+0.5, (n + floor(n+1))/2)函数对。 这将导致序列1, 3/2, 7/4, 15/8, ...，您将永远无法2.
函数(2^n, 20 - 5n + n^2)按顺序1, 2, 4, 16, 14, ...出现，显然不是有序的。 因此，需要不减少。
函数(n-3)给出了序列(1， -2， -5， ...)并显示了n < f_i(n)的重要性。
那么为什么会这样呢？
首先，很明显，该算法输出的任何内容都在集合中。
反过来，假设所有三个条件都满足。 然后，我们必须通过归纳法证明，如果你属于这个序列，我们在到达那里之前就开始寻找你，然后在我们经过你时必须产生它。 (我们传递你的事实是，序列是一组递增的整数。 证明有点混乱，但很简单。