Уродливые числа — это положительные целые числа, простые делители которых ограничены значениями 2, 3 и 5. В этой статье блога мы обсудим несколько методов поиска уродливых чисел в C++. Мы рассмотрим различные алгоритмы и предоставим примеры кода для каждого подхода. Давайте погрузимся!

Метод 1: грубая сила
Самый простой способ найти уродливые числа — использовать грубую силу. Мы можем перебирать каждое положительное целое число, начиная с 1, и проверять, не является ли оно уродливым числом, на основе его простых множителей. Вот пример фрагмента кода:

#include <iostream>
bool isUgly(int num) {
    while (num % 2 == 0)
        num /= 2;
    while (num % 3 == 0)
        num /= 3;
    while (num % 5 == 0)
        num /= 5;
    return num == 1;
}
int findNthUglyNumber(int n) {
    int count = 0;
    int num = 1;
    while (count < n) {
        if (isUgly(num))
            count++;
        num++;
    }
    return num - 1;
}
int main() {
    int n = 10;
    int nthUglyNumber = findNthUglyNumber(n);
    std::cout << "The " << n << "th ugly number is: " << nthUglyNumber << std::endl;
    return 0;
}

Метод 2: динамическое программирование
Динамическое программирование можно использовать для эффективного поиска некрасивых чисел, избегая избыточных вычислений. Мы сохраняем три указателя, соответствующие числам, кратным 2, 3 и 5, и выбираем среди них наименьшее число в качестве следующего уродливого числа. Вот пример фрагмента кода:

#include <iostream>
#include <vector>
#include <algorithm>
int findNthUglyNumber(int n) {
    std::vector<int> uglyNumbers(n);
    uglyNumbers[0] = 1;
    int i2 = 0, i3 = 0, i5 = 0;
    for (int i = 1; i < n; i++) {
        int nextUglyNum = std::min({2 * uglyNumbers[i2], 3 * uglyNumbers[i3], 5 * uglyNumbers[i5]});
        uglyNumbers[i] = nextUglyNum;
        if (nextUglyNum == 2 * uglyNumbers[i2])
            i2++;
        if (nextUglyNum == 3 * uglyNumbers[i3])
            i3++;
        if (nextUglyNum == 5 * uglyNumbers[i5])
            i5++;
    }
    return uglyNumbers[n - 1];
}
int main() {
    int n = 10;
    int nthUglyNumber = findNthUglyNumber(n);
    std::cout << "The " << n << "th ugly number is: " << nthUglyNumber << std::endl;
    return 0;
}

Метод 3: приоритетная очередь
Используя приоритетную очередь, мы можем поддерживать отсортированную последовательность уродливых чисел. Мы начинаем с числа 1 и умножаем его на 2, 3 и 5, чтобы получить следующие уродливые числа. Вот пример фрагмента кода: