Суми от числа на Фибоначи
За всяко цяло положително число n съществува
крайна редица от числа на Фибоначи, чиято сума е n. Задачата е да
се напише програма, която дава дължината на най-късата редица от числа
на Фибоначи, чиято сума е зададено число n.
Да припомним, че числата на Фибоначи { fi
} се дефинират така: f1= f2=
1 и fi = fi -1+ fi
-2 за i = 3, 4, ... .
Например 6 = 1 + 5 = 3 + 3 = 2 + 2 + 2, като най-късата
редица има дължина 2.
Вход.
Всеки ред от входа съдържа по едно цяло положително
число n (1 < n < 1 000 001). Края на входа се маркира
с числото 0.
Изход.
Всеки ред от изхода съдържа по едно цяло число.
Пример.
13
19
102
1200
0
Решение на примера.
1
3
2
5