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

Тема в разделе "Свободное общение", создана пользователем V-Isa, 19 фев 2004.

Статус темы:
Закрыта.
  1. V-Isa

    V-Isa Гость

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

    admin Well-Known Member

    Регистрация:
    8 авг 2003
    Сообщения:
    2.811
    Симпатии:
    0
    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
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей