30.12.2020 20:12
nanallew 17 1500 Источник

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

Сегодня я бы хотел осветить тему представления чисел с помощью ряда Фибоначчи и разумеется написать простенькое 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ив, числа которого есть числами Фибоначчи, и которые бы в сумме давали нам входное число.

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

Пример работы для 20 случайных чисел до 1000

Оценка времени работы в зависимости от величины ряда (входного числа)

Как видим время работы даже на числах до 10^9 очень позитивное.

А общий объем кода в 17 строк говорит о том что обе задачи выполнены успешно.

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