c++ - 查找汉明码-而不是代码或距离

我目前正在学习C++。

我正在寻找Hamming numbers(主要除数小于或等于5的numbers)。

当我输入数字n时，程序应输出第n个汉明数字。

输入和输出以下数字:

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--;
}

因此，我想知道如何更快地找到答案。
这个算法似乎不是很好。

提前致谢。

最佳答案

如果您要检查一个特定数字是否为汉明数字，则您的代码很好。当您要构建汉明数字列表时，效率很低。

您可以使用自下而上的方法:从1开始，然后将其与2、3和5递归相乘，以使所有汉明数均达到一定的极限。您必须注意重复项，因为可以通过2·3和3·2达到6。一套可以解决这个问题。

下面的代码将生成适合32位unsigned int的所有汉明数。它通过“扩展”到所有汉明数来填充一个集合。然后，它从集合中构造一个排序的 vector ，您可以使用该 vector 在特定索引处查找汉明数:

#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;
}

即使最终创建的海明数超出了您的需要，此代码也比线性方法要快。

如果您确保不构造两次数字，则甚至不需要集合。每个汉明码都可以写成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保证不溢出，则可以在循环的条件部分中写入这些条件。

the Rosetta Code link Koshinae posted中的代码示例使用类似的策略，但是我很惊讶其中的某些代码很冗长。