gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:23:37 25 4
gpt4 key购买 nike

我目前正在学习 C++。

我在找Hamming numbers (numbers 其质因数小于或等于 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--;
}

所以我想知道如何才能更快地找到答案。这个算法好像不是很好。

提前致谢。

最佳答案

如果您想检查一个特定数字是否是汉明数,您的代码很好。当您想构建一个汉明数列表时,它是低效的。

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

下面的代码将生成适合 32 位无符号整数的所有汉明数。它通过“扩展”到所有汉明数来填充一个集合。然后它从该集合构造一个排序 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使用类似的策略,但令我惊讶的是其中一些策略如此冗长。

关于c++ - 查找汉明数 - 不是代码或距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29286845/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com