汉明问题是一个著名的问题,基本上生成所有只有{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
,g
等可计算且具有可证明无界范围但没有其他假设,则通过应用这些函数从{1}
生成的集合是递归可枚举的,但通常不是递归的。在非递归情况下,由于停机问题是不可判定的,因此没有算法可能起作用。实际上,没有通用算法可以确定 2 是否在该集合中。 - John Coleman