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

[V-Isa]

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

 

[admin]

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

 

[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