Рекурсивный алгоритм представления Цекендорфа

Приветики-омлетики

Спасибо добрым участникам Хабра, за то, что пригласили писать посты и получать на них фидбек.

Сегодня я бы хотел освятить тему представления чисел с помощью ряда Фибоначи и разумеется написать простенькое REST API c использованием Mongo DB алгоритм с помощью языка Ruby, который бы по заданому числу N возвращал его представление.

Часть 1 : представление Цекендорфа

Как гласит статья из Википедии :

Теорема Цекендорфа гласит, что всякое натуральное число можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи так, чтобы в этом представлении не оказалось двух соседних чисел из последовательности Фибоначчи.

100 = 89 + 8 + 3.

Я думаю, понимая что такое числа Фибоначи, не составит труда понять в чём заключенна данная теорема.

Цели которые должны быть достигнуты :

• скорость работы

• максимальная простота кода

Как язык програмирования я буду использовать Ruby, почему? Потому что Ruby – это

Лучший друг программиста.

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

Выписав все числа Фибоначи которые меньше заданого, на листочек (школа), я обнаружил, что выгодней всего для такой суммы брать самое последнее число, но при условии что оно меньше чем наше искомое число.

Пример:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.

Берём число 34, соседнее с ним число (21) можно сразу пропустить, ибо их сумма будет заведомо больше нашего входного числа N, ибо числа Фибоначи мы ищем пока они не превысят входное, ведь зачем нам числа больше входного :-).

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

И тогда появилась идея: а что если отнимать от N последнее число в ряду Фибоначи, и искать новый ряд где эта разница будет лимитом, и рекурсивно продолжать это действия пока разница не станет <= 0.

Пример:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
ans = [34]

N = 51 – 34 = 17
F = 1 , 1 , 2 , 3 , 5 , 8 , 13.
ans = [34 , 13]

N = 17 – 13 = 4
F = 1 , 1 , 2 , 3.
ans = [34 , 13 , 3]

N = 4 – 3 = 1
F = 1
ans = [34 , 13 , 3, 1]

Сразу попробую записать в код :

def le_fib(limit, fib)
  theoretical = fib[fib.count - 1] + fib[fib.count - 2]
  return fib.last if theoretical > limit

  fib << theoretical
  le_fib(limit, fib)
end

def main(target,result)
  temporary = le_fib(target, [1,1])
  result << temporary
  return result if target - temporary <= 0

  main(target - temporary, result)
end
pp main(gets.to_i,[])

Функция le_fib – рекурсивно ищет ряд Фибоначи с пределом, на то, что бы следующее число не было больше чем входное число target. Здесь важно, что нас не интересует ряд Фибоначи целиком, нам важно лишь его окончание.

Функция main – рекурсивно ищет масcив, числа которого есть числами Фибоначе, и которые бы в сумме давали нам входное число.

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

Статья про интерес, всегда в рукаве нужно иметь пару задач с числами Фибоначе, иначе какой из тебя программист 🙂