В спортивном программировании и теории чисел существует интересная категория объектов — самоописательные числа (или автобиографические числа). Число называется самоописательным, если его n-я цифра (начиная с нулевой позиции) точно указывает, сколько раз цифра «n» встречается в этом числе.
Например, рассмотрим число 21200:
Разберем, как эффективно найти все такие числа в десятичной системе счисления, используя встроенный язык 1С, и проанализируем различные подходы к оптимизации алгоритма.
Прежде чем приступать к написанию кода, проанализируем математические ограничения. Простой перебор всех чисел до 10 миллиардов займет неприемлемое время. Для ускорения поиска воспользуемся двумя ключевыми свойствами:
Эти свойства позволяют нам отсекать огромные ветки перебора в рекурсивных функциях. Если текущая сумма цифр уже превысила допустимый предел, продолжать расчет нет смысла.
Рассмотрим наиболее эффективный метод, предложенный в обсуждении — рекурсивный поиск с использованием массива, который отслеживает «баланс» использования цифр. Мы будем «набирать» число по цифре, одновременно проверяя, сколько раз каждая цифра была использована и сколько раз она *должна* быть использована согласно текущему значению разряда.
Основная логика заключается в функции Рекурсия, которая принимает текущую позицию, оставшуюся сумму и массив состояний. Посмотрим на реализацию:
Функция Рекурсия(Поз, Длина, МассивБаланса, ТекущееЧисло, ОставшаясяСумма)
// Если дошли до конца числа
Если Поз = Длина Тогда
// Проверяем инвариант взвешенной суммы
Если ОставшаясяСумма <> 0 Тогда
Возврат 0;
Конецесли;
// Проверяем, чтобы все цифры в балансе сошлись в ноль
Для Каждого ЗначениеБаланса Из МассивБаланса Цикл
Если ЗначениеБаланса <> 0 Тогда
Возврат 0;
Конецесли;
КонецЦикла;
Сообщить("Найдено число: " + ТекущееЧисло);
Возврат 1;
Конецесли;
// Перебор возможных цифр для текущей позиции
// Первая цифра не может быть нулем (для чисел длиной > 1)
Для Д = ?(Поз = 0, 1, 0) По Мин(ОставшаясяСумма, Длина - 1) Цикл
// Обновляем баланс:
// Увеличиваем счетчик цифр на текущей позиции
МассивБаланса[Поз] = МассивБаланса[Поз] + Д;
// Уменьшаем баланс для цифры, которую мы фактически поставили
МассивБаланса[Д] = МассивБаланса[Д] - 1;
// Рекурсивный вызов с уменьшением оставшейся взвешенной суммы
Рекурсия(Поз + 1, Длина, МассивБаланса, ТекущееЧисло + Строка(Д), ОставшаясяСумма - Д * Поз);
// Откат состояния (Backtracking)
МассивБаланса[Д] = МассивБаланса[Д] + 1;
МассивБаланса[Поз] = МассивБаланса[Поз] - Д;
КонецЦикла;
КонецФункции
Проанализируем работу этого алгоритма. В МассивБаланса мы храним разницу между тем, сколько раз цифра *должна* встретиться (согласно значению в разряде), и тем, сколько раз она *уже* встретилась в процессе формирования числа. Идеальный результат — когда к концу формирования числа все элементы массива равны нулю.
В ходе дискуссии было отмечено, что для больших оснований систем счисления (длиной 7 и более) самоописательные числа всегда следуют определенному шаблону. Это позволяет вообще избежать глубокой рекурсии для поиска длинных чисел.
Шаблон для основания b >= 7:
b - 4211Рассмотрим пример для 10-разрядного числа (десятичная система):
Получаем число: 6210001000. Проверим: 6 нулей, 2 единицы, 1 двойка, 0 троек, 0 четверок, 0 пятерок, 1 шестерка, остальные нули. Условие выполняется!
Еще один вариант решения, предложенный участниками, основывается на аналитическом сужении области поиска. Выяснено, что в самоописательных числах цифры больше 3 могут стоять только в самом первом разряде (счетчик нулей). Это позволяет сократить перебор до нескольких циклов.
&НаКлиенте
Процедура НайтиЧислаПеребором()
МассивРезультатов = Новый Массив;
// Перебираем только первые три разряда, остальное заполняем логически
Для Разряд0 = 1 По 9 Цикл
Для Разряд1 = 0 По 2 Цикл
Для Разряд2 = 0 По 2 Цикл
ЧислоСтрокой = ФормироватьПостфикс(Разряд0, Разряд1, Разряд2);
Если ЭтоСамоописательное(ЧислоСтрокой) Тогда
МассивРезультатов.Добавить(ЧислоСтрокой);
КонецЕсли;
КонецЦикла;
КонецЦикла;
КонецЦикла;
КонецПроцедуры
Функция ФормироватьПостфикс в данном случае будет дописывать нули и ставить единицу в разряд, соответствующий значению Разряд0. Такой метод работает на порядок быстрее общего перебора, так как количество комбинаций сокращается до нескольких десятков.
Мы проанализировали несколько способов решения задачи в среде 1С. Самым гибким является рекурсивный метод с контролем баланса, так как он работает для любой длины числа. Однако аналитический метод (использование шаблона b-4, 2, 1...) является самым быстрым, так как выдает результат мгновенно по формуле.
Важные моменты для запоминания:
Мин(ОставшаясяСумма, Длина - 1) для ограничения циклов — это база эффективного бэктрекинга.Массив, а в Строку переводить только результат для вывода пользователю.Эти подходы применимы не только в математических головоломках, но и в реальных бизнес-задачах, связанных с комбинаторикой, например, при распределении товаров по ячейкам или планировании сложных графиков производства.