2.25 Поиск суммы чисел Фибоначчи на основе теоремы Цекендорфа
Согласно теореме Цекендорфа, любое произвольное положительное целое можно выразить
как сумму (необязательно последовательных) чисел Фибоначчи.
Напишите функцию
get_non_consecutive_fibonacci_numbers_summing_to_n(n), которая принимает натуральное число
n и возвращает
список непоследовательных чисел Фибоначчи, сумма которых равна
n.
Числа в списке должны следовать в порядке убывания, без повторений, длина списка должна быть минимально возможной.
В табл. 2.25 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 2.25. Некоторые ожидаемые результаты для задачи поиска суммы чисел Фибоначчи |
| n |
Ожидаемый результат |
| 53 |
34 13 5 1 |
| 25 |
21 3 1 |
| 31 |
21 8 2 |
| 3009 |
2584 377 34 13 1 |
Запрещенные операторы:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
53
|
34 13 5 1
|
|
2
|
3009
|
2584 377 34 13 1
|