Поиск номеров Хэмминга - не код или расстояние

Question

В настоящее время я изучаю C++.

Я ищу hamming 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--; 
} 

Так что я хотел бы знать, как я могу найти ответ быстрее. Этот алгоритм не кажется очень хорошим.

Заранее спасибо.

Answer 1

Ваш код хорош, если вы хотите проверить, является ли один конкретный номер числом помех. Когда вы хотите создать список номеров для помех, это неэффективно.

Вы можете использовать подход снизу вверх: Начните с 1, а затем рекурсивно размножайтесь с 2, 3 и 5, чтобы получить все номера помех до определенного предела. Вы должны позаботиться о дубликатах, потому что вы можете добраться до 6 через 2 · 3 и 3 · 2. Набор может позаботиться об этом.

В приведенном ниже коде будут генерироваться все номера помех, которые вписываются в 32-битный беззнаковый int. Он заполняет набор, «распространяя» все номера хамминга. Затем он создает отсортированный вектор из набора, который вы можете использовать, чтобы найти номер Хэмминга в определенном индексе:

#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 не были переполнены, эти условия могли быть записаны в состоянии части цикла.

Примеры кода в ссылке, опубликованной Koshinae, используют аналогичные стратегии, но я удивлен, как долго некоторые из них.