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

Question

我目前正在学习C++。

我正在寻找汉明数（质因数小于或等于 5 的 数字）。

当我输入数字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--;
}

所以我想知道如何才能更快地找到答案。这个算法看起来不太好。

提前致谢。

Answer 1

如果您想检查一个特定数字是否是汉明数，那么您的代码很好。当你想建立一个汉明数列表时，效率很低。

\n\n

您可以使用自下而上的方法：从 1 开始，然后递归地将其与 2、3 和 5 相乘，以使所有汉明数达到某个限制。您必须处理重复项，因为您可以通过 2\xc2\xb73 和 3\xc2\xb72 得到 6。一套可以解决这个问题。

\n\n

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

\n\n

#include <iostream>\n#include <algorithm>\n#include <set>\n#include <vector>\n\ntypedef unsigned int uint;\n\nconst uint umax = 0xffffffff;\n\nvoid spread(std::set<uint> &hamming, uint n)\n{\n    if (hamming.find(n) == hamming.end()) {\n        hamming.insert(n);\n\n        if (n < umax / 2) spread(hamming, n * 2);\n        if (n < umax / 3) spread(hamming, n * 3);\n        if (n < umax / 5) spread(hamming, n * 5);\n    }\n}\n\nint main()\n{\n    std::set<uint> hamming;\n\n    spread(hamming, 1);\n\n    std::vector<uint> ordered(hamming.begin(), hamming.end());\n\n    for (size_t i = 0; i < ordered.size(); i++) {\n        std::cout << i << \' \' << ordered[i] << \'\\n\';\n    }\n\n    return 0;\n}\n

\n\n

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

\n\n

如果您确保不会两次构造数字，您甚至不需要集合。每个汉明数都可以写成h = 2^n2 + 3^n3 + 5^n5，因此如果您找到一种方法来唯一地迭代这些数，那么您就完成了：

\n\n

#include <iostream>\n#include <algorithm>\n#include <set>\n#include <vector>\n\ntypedef unsigned int uint;\n\nint main()\n{\n    const uint umax = 0xffffffff;\n    std::vector<uint> hamming;\n\n    for (uint k = 1;; k *= 2) {\n        for (uint l = k;; l *= 3) {\n            for (uint m = l;; m *= 5) {\n                hamming.push_back(m);\n                if (m > umax / 5) break;\n            }\n            if (l > umax / 3) break;\n        }\n        if (k > umax / 2) break;\n    }\n\n    std::sort(hamming.begin(), hamming.end());\n\n    for (size_t i = 0; i < hamming.size(); i++) {\n        std::cout << i << \' \' << hamming[i] << \'\\n\';\n    }\n\n    return 0;\n}\n

\n\n

break循环需要奇怪的语法，因为我们必须在溢出之前检查大小。如果umax*5保证不溢出，这些条件可以写在循环的条件部分中。

\n\n

Koshinae发布的Rosetta 代码链接 中的代码示例使用了类似的策略，但令我惊讶的是其中一些示例的长度。

\n