Полномочия половины этой суммы до одного

Question

Назовите каждое субанитарное соотношение с его знаменателем мощностью 2 a perplex.

Номер 1 может быть написан многими способами как сумма недоумений.

Назовите каждую сумму недоумений дзета. Два зета отличаются друг от друга тогда и только тогда, когда одна из дзета имеет как минимум одно недоумение, которое у другого нет. На изображении, показанном выше, последние два зета считаются одинаковыми.

Найти все числа способов 1 можно записать в виде дзеты с N недоумениями. Поскольку это число может быть большим, вычислите его по модулю 100003.

Пожалуйста, не публикуйте код, а скорее алгоритм. Будьте как можно точнее.

Эта проблема была дана на конкурсе, и официальное решение, написанное на румынском языке, было загружено в https://www.dropbox.com/s/ulvp9of5b3bfgm0/1112_descr_P2_fractii2.docx?dl=0 в виде файла docx. (вы можете использовать перевод google) Я не понимаю, что хотел сказать автор решения.

Answer 1

Ну, это напоминает мне алгоритмы BFS (первый поиск по ширине), где вы излучаете из одной точки, чтобы найти несколько решений с различными перестановками.

Здесь вы можете использовать рекурсию и задавать базовый регистр, как если бы в 1 столбец вызова рекурсивной функции были достигнуты N недоразумений.

Таким образом, вы можете сказать:

function(int N <-- perplexes, ArrayList<Double> currentNumbers, double dividedNum) 
if N == 0, then you're done - enter the currentNumbers array into a hashtable 
clone the currentNumbers ArrayList as cloneNumbers 
remove dividedNum from cloneNumbers and add 2 dividedNum/2 
iterate through index of cloneNumbers 
    for every number x in cloneNumbers, call function(N--, cloneNumbers, x) 

Это грубый, очень неэффективно, но короткий путь, чтобы сделать это. Очевидно, есть много способов, с помощью которых вы можете сократить алгоритм (уменьшите количество дубликатов, попадающих в хэш-таблицу, предотвратите клонирование как можно больше и т. Д.), Но поскольку это показывает абсолютную перестановку каждого числа, а затем вводит эту последовательность в hashtable, хэш-таблица будет использовать сравнение equals(), чтобы увидеть, что последовательность уже существует (например, ваши последние 2 zetas) и отклонить дубликат. Таким образом, вы останетесь с ответом, который вы хотите.

Эффективность текущего алгоритма: O (| E |^(N)), где | E | - это абсолютное число чисел, которое вы можете иметь внутри массива в конце всех вставок, а N - количество вставок (или, как вы сказали, количество недоумений). Очевидно, что это не самая оптимальная скорость, но она определенно работает.

Надеюсь, это поможет!