В этой статье мы углубимся в концепцию самоделящихся чисел и рассмотрим несколько методов их эффективного вычисления. Самоделящиеся числа — это целые числа, которые делятся на каждую содержащуюся в них цифру. Например, число 128 является самоделящимся числом, поскольку оно делится на 1, 2 и 8. Наша цель — найти все самоделящиеся числа в заданном диапазоне [слева, справа]. Мы обсудим различные подходы и предоставим примеры кода для реализации этих методов.

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

#include <vector>
vector<int> selfDividingNumbers(int left, int right) {
    vector<int> result;
    for (int num = left; num <= right; num++) {
        int n = num;
        bool isSelfDividing = true;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                isSelfDividing = false;
                break;
            }
            n /= 10;
        }
        if (isSelfDividing) {
            result.push_back(num);
        }
    }
    return result;
}

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

#include <vector>
vector<int> selfDividingNumbers(int left, int right) {
    vector<int> result;
    for (int num = left; num <= right; num++) {
        int n = num;
        bool isSelfDividing = true;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                isSelfDividing = false;
                break;
            }
            n /= 10;
        }
        if (isSelfDividing) {
            result.push_back(num);
        }
    }
    return result;
}

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

def selfDividingNumbers(left, right):
    def isSelfDividing(num):
        if num < 10:
            return True
        digit = num % 10
        if digit == 0 or num % digit != 0:
            return False
        return isSelfDividing(num // 10)
    result = []
    for num in range(left, right + 1):
        if isSelfDividing(num):
            result.append(num)
    return result

В этой статье мы рассмотрели различные методы вычисления самоделящихся чисел в заданном диапазоне. Мы начали с итерационного подхода методом грубой силы, а затем представили оптимизированную версию, которая сокращает количество ненужных итераций. Кроме того, мы обсудили рекурсивный подход с использованием Python. В зависимости от ассортимента и требований вы можете выбрать наиболее подходящий для вашей реализации способ.

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