• Открыта запись на вторую часть курса по анонимности и безопасности в сети интернет "Paranoid II" от команды codeby. Анонимные роутеры, Подъём, настройка и администрирование Tor-ноды, Работа с железом ПК, Удаление аппаратных закладок, Минимизация рисков, Авторские разработки и многое другое. Подробнее ...

  • Напоминаем, что 1 декабря стартует курс "Тестирование Веб-Приложений на проникновение с нуля" от команды codeby. Общая теория, подготовка рабочего окружения, пассивный фаззинг и фингерпринт, активный фаззинг, уязвимости, пост-эксплуатация, инструментальные средства, Social Engeneering и многое другое. Подробнее ...

Алгоритм расчета количества "счастливых" чисел

  • Автор темы V-Isa
  • Дата начала
Статус
Закрыто для дальнейших ответов.
V

V-Isa

Необходим алгоритм определения количества "счастливых" чисел в заданном диапазоне. Обычный перебор не подходит, так как разрадность числа может быть очень большой. Счастливым называется число, сумма цифр которого слева равна сумме цифр справа.
Например, 123006 - счастливое, 12306 - нет.
 
A

admin

V-Isa
А если через массив делать? Тогда должно помочь. Но быстрдействие его весьма сомнительно.
 
G

Guest

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

Опять же, мы можем перебирать не все 2N-разрядные числа, а только счастливые 2N-разрядные. На векторе это делать гораздо проще, чем на двоичном представлении.

Алгоритм такой:
Для 2N-разрядного числа есть
* N свободных переменных d[1]..d[N], каждая из которых меняется от 0 до 9
их сумма S лежит в пределах 0..9N
* переменная d[N+1] может меняться от max(0, S-9N) до min(9, S)
оставшиеся d[N+2]..d[2N] в сумме должны дать S1=S-d[N+1]
* соответственно, d[N+2] меняется от max(0, S1-9(N-1)) до min(9, S1)
и так далее, пока
* последняя переменная, d[2N] вообще принимает одно-единственное значение.

Алгоритм можно построить на рекурсии глубиной 2N-1, - т.е. на 2N-1 вложенных циклах;
а можно - на двух циклах: внешний, вдоль множества всех чисел, а внутренний - вдоль разрядов числа.

Больше того, можно написать функцию next(vector_of_digits) которая из текущего вектора строит следующий.
Кстати, для удобства можно вместе с самим числом хранить ещё и вектор частичных сумм, S,S1,...SN
 
Статус
Закрыто для дальнейших ответов.
Мы в соцсетях:  ТелеграмВконтактеДзенФейсбукТвиттерЮтуб