Аддитивная цепочка
maximsidorovАлгоритмы аддитивных цепочек на языке Julia
В данном примере рассматривается реализация алгоритма поиска минимальной длины аддитивной цепочки для заданных чисел на языке программирования Julia.
Введение
Алгоритм аддитивных цепочек решает задачу нахождения наименьшего количества шагов, необходимых для получения целевого числа, начиная с единицы, где каждый следующий член цепочки равен сумме двух предыдущих членов этой же цепочки.
Это классическая задача в теории чисел и имеет приложения в оптимизации возведения в степень, вычислениях в криптографии, а также в анализе сложности некоторых алгоритмов.
Теоретическая часть
Аддитивная цепочка длины для представляет собой последовательность , такие как . Каждый элемент является суммой двух предыдущих членов, не обязательно различимых.
Цепь Брауэра для — это цепь сложения, где . Каждый элемент использует предыдущий элемент в качестве слагаемого.
В этом примере нас интересуют цепочки минимальной длины .
Задача
Для каждого вывести следующее:
-
,
-
количество цепей Брауэра длины .
Функция trypermutation
Функция trypermutation рекурсивно строит все возможные последовательности таких сумм, пытаясь достичь цели за минимальное число шагов. Это делается перебором всех допустимых вариантов сложений (перестановок).
Основная часть
Функция проверки текущего состояния последовательности — checksequence
"""
Проверяет условия завершения рекурсии или продолжает её.
pos -- текущее количество шагов (глубина рекурсии),
seq -- текущая цепочка значений,
n -- целевое значение,
minlen -- максимальная разрешённая глубина (минимально найденная длина до этого момента).
Возвращает кортеж из:
(minimal_length_found, number_of_ways_with_that_length)
"""
function checksequence(pos, seq, n, minlen)
# Если мы уже превысили известный минимум – дальше не стоит проверять
pos > minlen || seq[1] > n ? (minlen, 0) :
# Если первое значение стало больше N – цепочка не годится
seq[1] == n ? (pos, 1) : # Мы достигли цели! Возвращаем кол-во шагов и одну найденную цепочку
# Если ещё не достигли максимума, но можно продолжать перебирать:
pos < minlen ? trypermutation(0, pos, seq, n, minlen) : (minlen, 0) # Иначе всё равно перешагнули
end
Рекурсивная функция попытки всех допустимых перестановок — trypermutation
"""
trypermutation(i, pos, seq, n, minlen)
i -- индекс последнего элемента, который может быть слагаемым,
pos -- сколько элементов есть в текущей цепочке (длина цепочки),
seq -- сама цепочка чисел,
n -- целевое (искомое) число,
minlen -- текущая лучшая найденная длина цепочки.
Возвращает пару (лучшая_длина, число способов получить эту длину).
"""
function trypermutation(i, pos, seq, n, minlen)
if i > pos
return minlen, 0 # Ничего нового не нашлось – просто возвращаем минимум
end
new_seq = deepcopy(seq) # Создаём копию цепочки
pushfirst!(new_seq, seq[1] + seq[i+1]) # Добавляем новое число в начало (слева): a[j] = a[1]+a[i+1]
res1 = checksequence(pos + 1, new_seq, n, minlen) # Проверяем полученную цепочку дальше
res2 = trypermutation(i + 1, pos, seq, n, res1[1]) # Пробуем другой вариант i -> i+1
# Выбираем наилучший результат:
if res2[1] < res1[1]
return res2
elseif res2[1] == res1[1]
return res2[1], res1[2] + res2[2] # Если равно — складываем количества путей
else
error("Результат с большим i меньше результата меньшей i – логически ошибочно!")
end
end
Главная программа: вывод результатов для набора чисел
Набор тестовых чисел: для каждого из них будет найдена минимальная длина аддитивной цепочки.
for num in [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
(minlen, nchains) = trypermutation(0, 0, [1], num, 12) # Стартовая цепочка — [1]; максимальная допустимая длина — 12
println("N = ", num)
println("Минимальная длина цепочек: L(n) = ", minlen)
println("Количество цепочек такой длины (число Брауэра): ", nchains)
end
Как работает главный цикл?
Для каждого числа из списка выполняется следующее:
- Запускается рекурсивный перебор
trypermutation, начинающий со стартовой цепочки[1]. - Рекурсия генерирует все возможные последовательности, добавляя новый член как сумму любых двух существующих.
- Функция
checksequenceотслеживает достижение нужного значения (== n) и фиксирует, если новая цепочка короче текущей. - По окончании перебора выводятся два числа для каждого входного:
L(n)— минимальная длина аддитивной цепочки;- Число минимальных цепочек Брауэра (с разным порядком сложений, но той же длины).
Заключение
Мы рассмотрели реализацию алгоритма построения минимальных аддитивных цепочек методом полного перебора с использованием рекурсии в среде Julia. Для набора чисел были найдены минимальные длины соответствующих цепочек и подсчитано число таких цепочек (т.н. цепочек Брауэра). Эта техника полезна, например, для эффективных алгоритмов быстрого возведения в степень и анализа трудоемкости операций в криптографических системах.
Пример разработан с использованием материалов Rosetta Code