寻找汉明数 - 不是代码或距离

Question

我目前正在学习C++。

我正在寻找Hamming numbers（其质因子小于或等于5的数值）。

当我输入一个数字n时，程序应该输出第n个Hamming数。

以下是输入和输出的数字：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 ...

找到汉明数看起来很容易，但增加输入数字会使运行时间成本呈指数增长。

如果我输入超过1000，它几乎需要超过1秒的时间， 而超过1200，它几乎需要超过5秒的时间。

这是我写的代码：

while (th > 1)
{
    h++;
    x = h;

    while (x % 2 == 0)
        x /= 2;
    while (x % 3 == 0)
        x /= 3;
    while (x % 5 == 0)
        x /= 5;

    if (x == 1)
        th--;
}

我想知道如何更快地找到答案。这个算法似乎不太好。

提前感谢。

- Jae-young Song

---

请查看以下内容：http://rosettacode.org/wiki/Hamming_numbers - Koshinae

此外，这里还有：http://en.wikipedia.org/wiki/Regular_number - Koshinae

你只需要做一次除法就能得到一个已经计算过的数字。记忆化。 - stark

@stark备忘录化指数空间不可取。 - Will Ness

Answer 1

如果您想检查一个特定的数字是否是哈明数，那么您的代码很好用。但当您想建立一个哈明数列表时，它就效率低下了。

您可以使用自底向上的方法：从1开始，然后递归地将其乘以2、3和5，以获取所有小于某个限制的哈明数。您必须注意重复项，因为您可以通过2·3和3·2到达6。一个集合可以解决这个问题。

下面的代码将生成适合32位无符号整数的所有哈明数。它通过“扩散”到所有哈明数来填充一个集合。然后它从集合构造一个排序向量，您可以使用它来找到某个索引处的哈明数：

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

typedef unsigned int uint;

const uint umax = 0xffffffff;

void spread(std::set<uint> &hamming, uint n)
{
    if (hamming.find(n) == hamming.end()) {
        hamming.insert(n);

        if (n < umax / 2) spread(hamming, n * 2);
        if (n < umax / 3) spread(hamming, n * 3);
        if (n < umax / 5) spread(hamming, n * 5);
    }
}

int main()
{
    std::set<uint> hamming;

    spread(hamming, 1);

    std::vector<uint> ordered(hamming.begin(), hamming.end());

    for (size_t i = 0; i < ordered.size(); i++) {
        std::cout << i << ' ' << ordered[i] << '\n';
    }

    return 0;
}

这段代码比你的线性方法更快，即使你最终创建了比所需还多的汉明数也是如此。

如果您确保不重复构造数字，则甚至不需要使用 set（集合）。每个汉明数都可以写成 h = 2^n2 + 3^n3 + 5^n5 的形式，因此，只要找到一种独特的迭代方式，您就完成了：

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

typedef unsigned int uint;

int main()
{
    const uint umax = 0xffffffff;
    std::vector<uint> hamming;

    for (uint k = 1;; k *= 2) {
        for (uint l = k;; l *= 3) {
            for (uint m = l;; m *= 5) {
                hamming.push_back(m);
                if (m > umax / 5) break;
            }
            if (l > umax / 3) break;
        }
        if (k > umax / 2) break;
    }

    std::sort(hamming.begin(), hamming.end());

    for (size_t i = 0; i < hamming.size(); i++) {
        std::cout << i << ' ' << hamming[i] << '\n';
    }

    return 0;
}

循环中奇怪的 `break` 语法是必需的，因为我们必须在溢出之前检查大小。如果 `umax*5` 不会溢出，这些条件可以写在循环的条件部分。 罗塞塔代码链接 Koshinae 发布 的代码示例使用类似的策略，但我惊讶于其中一些代码的冗长程度。

- M Oehm

Answer 2

在这个链接中，你可以找到两种不同的解决方案来寻找第n个Hamming数。第二种方法是优化过的，可以在几秒钟内得出结果。

/* Function to get the nth ugly number*/
unsigned getNthUglyNo(unsigned n) 
{ 
    unsigned ugly[n]; // To store ugly numbers 
    unsigned i2 = 0, i3 = 0, i5 = 0; 
    unsigned next_multiple_of_2 = 2; 
    unsigned next_multiple_of_3 = 3; 
    unsigned next_multiple_of_5 = 5; 
    unsigned next_ugly_no = 1; 

    ugly[0] = 1; 
    for (int i=1; i<n; i++) 
    { 
        next_ugly_no = min(next_multiple_of_2, 
                           min(next_multiple_of_3, 
                               next_multiple_of_5)); 
        ugly[i] = next_ugly_no; 
        if (next_ugly_no == next_multiple_of_2) 
        { 
            i2 = i2+1; 
            next_multiple_of_2 = ugly[i2]*2; 
        } 
        if (next_ugly_no == next_multiple_of_3) 
        { 
            i3 = i3+1; 
            next_multiple_of_3 = ugly[i3]*3; 
        } 
        if (next_ugly_no == next_multiple_of_5) 
        { 
           i5 = i5+1; 
           next_multiple_of_5 = ugly[i5]*5; 
        } 
    } /*End of for loop (i=1; i<n; i++) */

return next_ugly_no; 
} 

- Pooria_T