查找汉明数字 - 不是代码或距离 [英] Finding Hamming Numbers - not code or distance

问题描述

我正在寻找汉明数字（主要因数小于或等于5的数字）。
当我输入一个数字时，程序应该输出 n

$ b

以下数字是输入和输出： > 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--; 
 
 
 
 $ b $ p 
 $ b所以我想知道如何能更快地找到答案。 
这个算法似乎并不是很好。
 
 
感谢您的帮助。 
 
解决方案
如果你想检查一个特定的数字是否是一个汉明数字，你的代码是好的。你可以使用自下而上的方法：从1开始，然后用2递归地乘以2， 3和5，以使所有汉明数达到一定限度。你必须照顾重复，因为你可以通过2·3和3·2的方式达到6。下面的代码将生成所有的汉明数字，这些数字适合32位无符号整型数组。它通过扩散到所有汉明数字来填充一个集合。然后它从这个集合构造出一个已排序的向量，你可以使用它来在某个索引处找到一个汉明数字： 
 
 
  #include <&的iostream GT; 
 #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）; （n  
如果（n ;如果（n ; 
 
 
 
 int main（）
 {
 std :: set< uint>海明; 
 
 spread（hamming，1）; 
 
 std :: vector< uint> （hamming.begin（），hamming.end（））; （size_t i = 0; i< ordered.size（）; i ++）{
 std :: cout<<我 ''<<命令[i]<< \\\
; 
} 
 
 return 0; 
 
 $ / code> 
即使您最终创建了更多的汉明数字比你需要。
 
 
 
如果你确定你不建立一个数字两次，你甚至不需要一个集合。每个汉明数字都可以写成 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>海明; （uint k = 1 ;; k * = 2）{
 for（uint l = k ;; l * = 3）{
 for（uint m = 1）
 
 ;; m * = 5）{
 hamming.push_back（m）; $ m $ b如果（m> umax / 5）中止; 
} 
 if（l> umax / 3）break; 
} 
 if（k> umax / 2）break; 
} 
 
 std :: sort（hamming.begin（），hamming.end（））; （size_t i = 0; i< hamming.size（）; i ++）{
 std :: cout<<我 ''<< hamming [i]<< \\\
; 
} 
 
 return 0; 
 
  
奇怪的 break 语法的循环是必需的，因为我们必须检查溢出之前的大小。如果 umax * 5 可以保证不溢出，这些条件可以写入循环的条件部分。
 
 
 
链接Koshinae中的代码示例使用了类似的策略，但我很惊讶其中有些是多么漫长。
 
I'm currently learning C++.

I am looking for hamming numbers (numbers whose prime divisors are less or equal to 5).

When I input a number n, the program should output the n-th hamming number.

Following numbers are input, and output:
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 ...
Finding hamming numbers looks easy, but increasing the input number increases runtime cost exponentially.
If I input over 1000, it almost costs over 1 second,
and over 1200, it almost costs over 5 seconds.

This is the code I wrote:
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--;
}
So I would like to know how I can find the answer faster.
This algorithm doesn't seem to be very good.

Thanks in advance.
解决方案
Your code is good if you want to check whether one particular number is a hamming number. When you want to build a list of hamming numbers, it is inefficient.

You can use a bottom-up approach: Start with 1 and then recursively multiply that with 2, 3, and 5 to get all hamming numbers up to a certain limit. You have to take care of duplicates, because you can get to 6 by way of 2·3 and 3·2. A set can take care of that.

The code below will generate all hamming numbers that fit into a 32-bit unsigned int. It fills a set by "spreading" to all hamming numbers. Then it constructs a sorted vector from the set, which you can use to find a hamming number at a certain index:
#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;
}
This code is faster than your linear method even if you end up creating more hamming numbers than you need.

You don't even need a set if you make sure that you don't construct a number twice. Every hamming number can be written as h = 2^n2 + 3^n3 + 5^n5, so if you find a means to iterate through these uniquely, you're done:
#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;
}
The strange break syntax for the loops is required, because we have to check the size before the overflow. If umax*5 were guananteed not to overflow, these conditions could be written in the condition part of the loop.

The code examples in the link Koshinae posted use similar strategies, but I'm surprised how lengthy some of them are.

                        
这篇关于查找汉明数字 - 不是代码或距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！