Спасибо добрым участникам Хабра за приглашение писать посты и получать о них отзывы.
Сегодня мне хотелось бы осветить тему представления чисел с помощью ряда Фибоначчи и, конечно же, написать простой REST API с использованием алгоритма Mongo DB на языке Рубин , что для данного числа Н возвращал свое представление.
Часть 1: Презентация Зекендорфа
Как говорится статья из Википедии:Теорема Зекендорфа утверждает, что каждое натуральное число можно однозначно представить в виде суммы.Думаю, разобравшись в том, что такое числа Фибоначчи, не составит труда понять, о чем говорит эта теорема.один или больше разные числа Фибоначчи так, чтобы это представление не содержало двух соседних чисел из последовательности Фибоначчи.
100 = 89 + 8 + 3.
Цели, которые необходимо достичь:
- рабочая скорость
- максимальная простота кода
Лучший друг программиста.Сначала теоретически нужно найти шаблон, по которому будет написан алгоритм.
Записав на листок бумаги (школьный) все числа Фибоначчи, меньшие заданного числа, я обнаружил, что за такую сумму выгоднее всего взять самое последнее число, но при условии, что оно меньше желаемого.
число.
Пример : Н=51 Ж = 1, 1, 2, 3, 5, 8, 13, 21, 34. Берем число 34, число рядом с ним (21) можно сразу пропустить, так как их сумма заведомо будет больше нашего входного числа Н , потому что мы ищем числа Фибоначчи до тех пор, пока они не превысят входное, ведь зачем нам числа больше входного.
Но как лучше всего посчитать сумму? Простым перебором первого условия мы точно не добьемся: скорость работы.
Используя сложный алгоритм, откажемся от второго: максимальная простота кода.
И тут появилась идея: что, если мы заберем это у Н последнее число в ряду Фибоначчи, и искать новый ряд, где эта разница будет пределом, и рекурсивно продолжать это действие до тех пор, пока разница не станет <= 0. Пример : Н=51 Ж = 1, 1, 2, 3, 5, 8, 13, 21, 34. ответ = [34] Н = 51 - 34 = 17 Ф = 1, 1, 2, 3, 5, 8, 13. ответ = [34, 13] Н = 17 - 13 = 4 Ф = 1, 1, 2, 3. ответ = [34, 13, 3] Н = 4 - 3 = 1 Ф=1 ответ = [34, 13, 3, 1] Попробую сразу написать это в коде:
Функция le_fib - рекурсивно ищет ряд Фибоначчи с таким пределом, чтобы следующее число не было больше входного числа цель .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,[])
Здесь важно, что нас интересует не весь ряд Фибоначчи, нас интересует только его окончание.
Функция основной — рекурсивно ищет массив, числа которого являются числами Фибоначчи, и который в сумме даст нам входное число.
Но, чтобы убедиться в корректной работе алгоритма, следует сказать, что теоретически никакие два числа рядом не могут быть одинаковыми, поскольку последовательность убывает, и на каждой последующей итерации число с предыдущего этапа нам недоступно, потому что он явно больше.
Пример работы для 20 случайных чисел до 1000 
Оценка времени работы в зависимости от размера серии (количества входа) 
Как видим, время работы даже на числах до 10^9 очень положительное.
А общий объем кода в 17 строк говорит о том, что обе задачи выполнены успешно.
Статья про интерес, всегда нужно иметь в рукаве парочку задачек с числами Фибоначчи, иначе какой же ты программист? Теги: #математика #Алгоритмы #алгоритм #математическая задача
-
Ресурс Двигателя После Гибели Ракеты
19 Oct, 24 -
Зимний Дайджест Новостей Игровой Индустрии
19 Oct, 24
