Как найти и проверить совершенные числа в 1С: исправляем ошибки и оптимизируем алгоритм

← На главную

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

Напомним определение: совершенное число — это целое положительное число, которое равно сумме всех своих положительных делителей, отличных от самого числа. Самый простой пример — число 6. Его делители: 1, 2 и 3. Их сумма: 1 + 2 + 3 = 6.

Разбор ошибок исходного кода

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

Вспомним исходный вариант программы:


&НаКлиенте
Процедура СовершенныеЧислаОткрытие()
    НачальноеЧисло = 2;
    ПределПоиска = 500;
    
    Пока НачальноеЧисло < ПределПоиска Цикл
        СуммаДелителей = 0;
        Делитель = 1;
        
        Пока Делитель <= НачальноеЧисло/2 Цикл
            Если НачальноеЧисло % Делитель = 0 Тогда
            СуммаДелителей = СуммаДелителей + Делитель;
        КонецЕсли;
        Делитель = Делитель +1;
        КонецЦикла;
        
        Если СуммаДелителей = НачальноеЧисло Тогда
            СовершенныеЧисла = НачальноеЧисло;
        КонецЕсли;
        НачальноеЧисло = НачальноеЧисло + 1;
    КонецЦикла;
    
КонецПроцедуры

Давайте разберем по шагам ключевые проблемы этого кода:

Отсутствие вывода информации. Обратите внимание на строку СовершенныеЧисла = НачальноеЧисло;. Здесь переменная просто перезаписывается на каждой итерации внешнего цикла. На момент завершения работы процедуры в ней останется только последнее найденное число из диапазона до 500 (это число 496). Предыдущие найденные числа (6 и 28) будут безвозвратно утеряны. Более того, результат вообще никак не выводится на форму или в окно сообщений пользователю.
Жесткая привязка к диапазону поиска. Переменная ПределПоиска установлена в значение 500. В условии задачи сказано: «Вычислить программно и вывести первые 3 совершенных числа». В данном случае диапазон подобран удачно (первые три числа — это 6, 28 и 496). Но что, если бы нам потребовалось найти первые 4 числа? Четвертое совершенное число — 8128. Наш алгоритм бы его просто проигнорировал, так как цикл завершится на 500. Программа должна останавливаться не по достижению лимита чисел, а по счетчику успешно найденных результатов.
Отсутствие модульности структуры. Вторая часть задачи требует определить, является ли введенное пользователем число совершенным. В текущей реализации нам пришлось бы скопировать весь блок вычисления делителей и вставить его во вторую процедуру. Дублирование кода — это грубейшая ошибка проектирования. Логику проверки числа необходимо выделить в отдельную функцию, которую мы сможем вызывать из любых мест программы.
Крайне низкая производительность. Внутренний цикл проверки делителей работает до значения НачальноеЧисло / 2. Для небольших чисел это незаметно, но если пользователь захочет проверить число 8 128 или тем более 33 550 336 (пятое совершенное число), система зависнет на долгое время, выполняя десятки миллионов лишних итераций.

Шаг 1. Разработка универсальной и быстрой функции проверки

Для исправления архитектурных недостатков последуем совету из Сообщения 4 и создадим отдельную функцию ЭтоСовершенноеЧисло. Но перед написанием кода обсудим важную математическую оптимизацию.

Если число $N$ делится на число $d$, то оно автоматически делится и на число $N/d$. Это значит, что все делители числа (кроме квадратного корня из числа, если оно является полным квадратом) разбиваются на пары. Следовательно, нам нет необходимости перебирать все числа до $N/2$. Достаточно дойти только до квадратного корня из проверяемого числа $\sqrt{N}$.

Рассмотрим пример с числом 28. Его квадратный корень равен приблизительно 5.29. Нам достаточно проверить в качестве делителей числа от 2 до 5:

Проверяем 2: 28 делится на 2 без остатка. Значит, мы нашли сразу два делителя: 2 и парный ему 28 / 2 = 14.
Проверяем 3: 28 не делится на 3.
Проверяем 4: 28 делится на 4. Мы нашли делители 4 и парный ему 28 / 4 = 7.
Проверяем 5: 28 не делится на 5.

Добавляем к сумме обязательную единицу (так как любое число делится на 1) и получаем: 1 + 2 + 14 + 4 + 7 = 28. Мы совершили всего 4 итерации цикла вместо 14! На больших числах этот подход дает колоссальный выигрыш в скорости.

Реализуем этот оптимизированный алгоритм на языке 1С:


&НаКлиенте
Функция ЭтоСовершенноеЧисло(Знач ПроверяемоеЧисло)
    // Первое совершенное число в математике — это 6. 
    // Все числа меньше 6 заведомо не могут быть совершенными.
    Если ПроверяемоеЧисло <= 5 Тогда
        Возврат Ложь;
    КонецЕсли;
    
    // Любое число делится на 1, поэтому инициализируем сумму единицей
    СуммаДелителей = 1; 
    Делитель = 2;
    
    // Основной цикл оптимизированного поиска делителей до квадратного корня
    Пока Делитель * Делитель <= ПроверяемоеЧисло Цикл
        Если ПроверяемоеЧисло % Делитель = 0 Тогда
            СуммаДелителей = СуммаДелителей + Делитель;
            
            // Вычисляем парный делитель
            ПарныйДелитель = ПроверяемоеЧисло / Делитель;
            
            // Избегаем повторного добавления делителя, если число — полный квадрат
            Если ПарныйДелитель <> Делитель Тогда
                СуммаДелителей = СуммаДелителей + ПарныйДелитель;
            КонецЕсли;
        КонецЕсли;
        
        Делитель = Делитель + 1;
    КонецЦикла;
    
    // Число совершенно, если сумма его делителей равна самому числу
    Возврат (СуммаДелителей = ПроверяемоеЧисло);
КонецФункции

Шаг 2. Решение первой задачи (Поиск первых 3 чисел)

Теперь, когда у нас есть готовая универсальная функция проверки, мы можем легко и элегантно решить первую задачу. Нам нужно организовать цикл, который будет проверять числа по порядку, начиная с 2, и складывать найденные совершенные числа в массив. Как только количество элементов в массиве достигнет 3, цикл должен завершиться.

Напишем процедуру для обхода чисел:


&НаКлиенте
Процедура НайтиПервыеТриСовершенныхЧисла()
    НайденныеЧисла = Новый Массив;
    ТекущееЧисло = 2;
    
    // Цикл выполняется до тех пор, пока мы не соберем 3 совершенных числа
    Пока НайденныеЧисла.Количество() < 3 Цикл
        Если ЭтоСовершенноеЧисло(ТекущееЧисло) Тогда
            НайденныеЧисла.Добавить(ТекущееЧисло);
        КонецЕсли;
        
        ТекущееЧисло = ТекущееЧисло + 1;
    КонецЦикла;
    
    // Формируем красивую строку для вывода результата пользователю
    РезультатСтрокой = "Первые три совершенных числа успешно найдены: " + Символы.ПС;
    Для Каждого Число Из НайденныеЧисла Цикл
        РезультатСтрокой = РезультатСтрокой + "• " + Строка(Число) + Символы.ПС;
    КонецДля;
    
    ПоказатьПредупреждение(, РезультатСтрокой);
КонецПроцедуры

Благодаря использованию динамического условия окончания цикла НайденныеЧисла.Количество() < 3, программа гарантированно найдет ровно три числа и завершит работу. Если завтра вам понадобится найти первые 4 числа, вам достаточно будет изменить лишь одну цифру в условии цикла.

Шаг 3. Решение второй задачи (Проверка числа пользователя)

Для реализации второй части задачи нам понадобится форма. Предположим, вы создали обработку и добавили на управляемую форму два реквизита:

ЧислоДляПроверки (тип: Число, длина 15, точность 0) — поле ввода для пользователя.
Кнопку «Проверить», связанную с клиентской процедурой ПроверитьЧислоПользователя.

Напишем обработчик нажатия на кнопку. В нем мы обязательно предусмотрим валидацию входных данных, чтобы защитить программу от некорректного ввода (отрицательные числа, нули или пустые значения):


&НаКлиенте
Процедура ПроверитьЧислоПользователя(Команда)
    // Проверяем заполнение реквизита на форме
    Если НЕ ЗначениеЗаполнено(ЧислоДляПроверки) Или ЧислоДляПроверки <= 0 Тогда
        ПоказатьПредупреждение(, "Пожалуйста, введите корректное положительное целое число!");
        Возврат;
    КонецЕсли;
    
    // Вызываем нашу оптимизированную функцию
    Если ЭтоСовершенноеЧисло(ЧислоДляПроверки) Тогда
        ТекстСообщения = "Да! Число " + Строка(ЧислоДляПроверки) + " является совершенным.";
    Иначе
        ТекстСообщения = "Нет, число " + Строка(ЧислоДляПроверки) + " не является совершенным.";
    КонецЕсли;
    
    ПоказатьПредупреждение(, ТекстСообщения);
КонецПроцедуры

Продвинутый уровень: Генерация совершенных чисел через формулу Евклида-Эйлера

Проанализируем ситуацию: наш оптимизированный перебор работает прекрасно для первых четырех чисел (6, 28, 496, 8128). Но если вы попробуете найти пятое совершенное число (33 550 336) методом прямого перебора, это займет неприемлемо много времени даже с учетом оптимизации квадратного корня. Нам нужен принципиально иной подход.

Здесь на помощь приходит великая математика. Еще древнегреческий математик Евклид доказал, что если число $2^p - 1$ является простым, то число, вычисленное по формуле:

$$N = 2^{p-1} \times (2^p - 1)$$

будет четным совершенным числом. Спустя столетия Леонард Эйлер доказал обратное: все четные совершенные числа имеют именно такой вид. Числа вида $2^p - 1$ называются простыми числами Мерсенна.

Давайте посмотрим, как работает эта формула при разных значениях простого параметра $p$:

При $p = 2$: $2^1 \times (2^2 - 1) = 2 \times 3 = 6$ (1-е число)
При $p = 3$: $2^2 \times (2^3 - 1) = 4 \times 7 = 28$ (2-е число)
При $p = 5$: $2^4 \times (2^5 - 1) = 16 \times 31 = 496$ (3-е число)
При $p = 7$: $2^6 \times (2^7 - 1) = 64 \times 127 = 8128$ (4-е число)
При $p = 13$: $2^{12} \times (2^{13} - 1) = 4096 \times 8191 = 33 550 336$ (5-е число)

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

Для быстрой проверки чисел Мерсенна на простоту в математике используется специализированный эффективный тест Люка-Лемера. Напишем функцию, которая генерирует совершенные числа практически мгновенно:


&НаКлиенте
Функция ПолучитьСовершенноеЧислоПоПараметру(Знач р)
    // Вычисляем число Мерсенна: Mp = 2^p - 1
    ЧислоМерсенна = Pow(2, р) - 1;
    
    // Проверяем число Мерсенна на простоту с помощью теста Люка-Лемера
    Если р = 2 Тогда
        Простое = Истина;
    ИначеЕсли НЕ ЭтоПростоеЧисло(р) Тогда
        Простое = Ложь; // p само должно быть простым числом
    Иначе
        // Тест Люка-Лемера для Mp
        s = 4;
        Для и = 1 По р - 2 Цикл
            s = (s * s - 2) % ЧислоМерсенна;
        КонецДля;
        Простое = (s = 0);
    КонецЕсли;
    
    Если Простое Тогда
        // Возвращаем совершенное число: 2^(p-1) * (2^p - 1)
        Возврат Pow(2, р - 1) * ЧислоМерсенна;
    Иначе
        Возврат 0; // Данный параметр p не дает совершенного числа
    КонецЕсли;
EndФункции

&НаКлиенте
Функция ЭтоПростоеЧисло(Знач Число)
    Если Число <= 1 Тогда Возврат Ложь; КонецЕсли;
    Для д = 2 По Цел(Sqrt(Число)) Цикл
        Если Число % д = 0 Тогда Возврат Ложь; КонецЕсли;
    КонецДля;
    Возврат Истина;
КонецФункции

С помощью этой математической модели мы можем за доли секунды получить огромные совершенные числа, просто передавая простые параметры $p$ (например, 2, 3, 5, 7, 13, 17, 19). Попробуйте запустить этот алгоритм в 1С — вы будете удивлены скоростью его работы по сравнению со стандартным поиском делителей!

Оффтоп-загадка с форума: Что за формула в Сообщении 3?

В процессе обсуждения темы на форуме один из участников оставил ироничное сообщение (Сообщение 3) с просьбой написать программу, доказывающую неравенство:

$$rad(ABC)^s < C$$

для конечного числа троек взаимно простых чисел при условии $A+B=C$ и $s > 1$.

Проанализируем ситуацию: это не просто шутка, а отсылка к одной из величайших нерешенных математических проблем современности — abc-гипотезе (также известной как гипотеза Остерле — Массера), сформулированной в 1985 году. Суть гипотезы состоит в том, что для любого реального числа $s > 1$ существует лишь конечное множество троек взаимно простых положительных целых чисел $A$, $B$, $C$, удовлетворяющих условию $A + B = C$, для которых верно указанное неравенство. Здесь функция $rad(x)$ означает радикал числа (произведение всех его уникальных простых делителей).

Ирония автора сообщения заключалась в том, что доказать или опровергнуть данную гипотезу с помощью перебора на компьютере принципиально невозможно — это требует глубочайшего теоретического анализа. Заявленное в 2012 году японским математиком Синити Мотидзуки доказательство этой гипотезы до сих пор вызывает ожесточенные споры в мировом научном сообществе из-за своей чрезвычайной сложности. Попытка решить "на коленке" в 1С задачу тысячелетия — прекрасный пример тонкого программистского юмора!

Подводим итоги

Мы успешно модернизировали программу, исправили все логические ошибки исходного кода и разделили его на логические блоки в соответствии с лучшими практиками разработки на платформе 1С:Предприятие. Посмотрим, чему мы научились:

Разделение логики: всегда выносите повторяющиеся расчеты в отдельные экспортируемые или локальные функции. Функция ЭтоСовершенноеЧисло помогла нам решить две независимые задачи без дублирования кода.
Оптимизация вычислений: замена верхнего предела поиска делителей с половины числа $N/2$ на квадратный корень $\sqrt{N}$ ускоряет вычисления в геометрической прогрессии при росте проверяемого числа.
Математический подход: понимание внутренней природы чисел (в данном случае связи совершенных чисел с простыми числами Мерсенна) позволяет полностью отказаться от "тяжелых" переборов в пользу мгновенных формульных расчетов.

Применяйте изученные приемы оптимизации циклов и структурирования кода в своих повседневных задачах автоматизации бизнеса — это сделает ваши конфигурации быстрыми, а код — легким для чтения и поддержки вашими коллегами.