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

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

V-Isa

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

admin

Well-Known Member
08.08.2003
2 754
1
#2
V-Isa
А если через массив делать? Тогда должно помочь. Но быстрдействие его весьма сомнительно.
 

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

Опять же, мы можем перебирать не все 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
 
Статус
Закрыто для дальнейших ответов.