3

汉明问题是一个著名的问题，它基本上生成所有仅质因数为 {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？

4

1 回答 1

1

一个充分条件是，f_i从整数到整数的所有函数都必须是单调递增的，并且n < f_i(n)对于所有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)。

那么为什么会这样呢？

首先很明显，该算法的任何输出都在集合中。

反过来，假设所有三个条件都满足。然后我们必须通过归纳证明，如果你属于这个序列，我们在到达那里之前就开始寻找你，然后当我们超过你时必须产生它。（我们通过你的事实是，序列是一个递增的整数集。）证明有点混乱，但很简单。

于 2017-06-27T00:38:14.540 回答