Comments 20
Например бинарное представление — это булева логика, и вычисления в ЭВМ.А тут как?
Когда-то такое представление рассматривали как код, выявляющий ошибки — в представлении числа не может быть двух еденичек подряд. А потом придумали код Хэмминга, код Соломона-Рида, и эту чепуху выбросили.
ps Если уж автор добрался до статьи в вики, он бы мог её прочитать.
Для любого заданного натурального числа его цекендорфово представление находится при помощи жадного алгоритма
Какой перебор, какая рекурсия, какой фибонаЧе?..
Не всё в этой жизни автор знает…
Спасибо за отличное разъяснение, самому было интересно!
Ну рекурсия же выглядит занимательно, разве нет ?)
C. Heuberger, Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms
wwwu.aau.at/cheuberg/publications/pdf/minredfibo.pdf
Рекурсия выглядит уныло, если достаточно простой итерации.
n, F = 100, [1, 2]
while F[-1] < n do
F << F[-2] + F[-1]
end
F.reverse.each do |f|
if f <= n
n -= f
print f
print '+' if n > 0
end
end
Ты прав
Самый-самый классический кейс про рекурсию — DFS, обход дерева в глубину. Фишка в том, что приходтся возвращаться к развилкам, к тем данным, какие ты надыбал, впервые подойдя к развилке, и уходить из этой развилки с этими стартовыми данными в другую ветвь.
Это всегда хорошо работает, но не всегда нужно. Представь, что твоё дерево — бамбук. Развилок нет вообще, прёшь вверх до упора, упёрся — спрыгнул. Нет смысла запоминать ситуации на развилках, ведь развилок нет. Вот это-то и значит, что рекурсия тебе избыточна, достаточно итерации.
В данном случае отсутствие развилок — это природа жадного алгоритма. Ты откусываешь от n максимально возможное число фибоначчи, на другие не смотришь.
С Новым годом.
А тут сложение, где перенос, хоть и происходит сразу в две стороны, но дальше не распространяется.
В вашем же рекурсивном алгоритме вся рекурсия — хвостовая. Соответственно, она эквивалентна циклам. Ваше решение, фактически — это 2 вложенных цикла. le_fib строит числа фиббоначи до максимального, не больше заданного (одним циклом, с меньих к большим). Main откусывает максимальное число фиббоначи в цикле от заданного.
Если переписать с циклами, то станет понятно, что ваше решение квадратичное и делает много лишнего! Вместо того, чтобы строить числа фиббоначи с нуля на каждой итерации main, их можно построить только один раз, и дальше пройтись по этому массиву один раз с конца, вычитая текущее число, если оно помещается в target.
Будет даже короче вашего кода и быстрее в 20 раз для 10^9. Код уже выше привел longclaps.
def le_fib(limit, fib):
theoretical = fib[-1] + fib[-2]
if theoretical > limit:
return fib[-1]
fib.append(theoretical)
return le_fib(limit, fib)
def main(target,result):
temporary = le_fib(target, [1,1])
result.append(temporary)
if target — temporary <= 0:
return result
return main(target — temporary, result)
i=int(input('Enter i: '))
print(main(i,[]))
def le_fib(limit, fib):
theoretical = fib[-1] + fib[-2]
if theoretical > limit:
return fib[-1]
fib.append(theoretical)
return le_fib(limit, fib)
def main(target,result):
temporary = le_fib(target, [1,1])
result.append(temporary)
if target - temporary <= 0:
return result
return main(target - temporary, result)
i=int(input('Enter i: '))
print(main(i,[]))
Рекурсивный алгоритм представления Цекендорфа