La serie de Fibonacci está definida de la siguiente manera:
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2, para n > 2
Es decir, comienza con 1, 1 y luego los siguientes valores se forman sumando los dos números inmediatamente anteriores. Este proceso resulta en la siguiente serie de enteros:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...
De la mano de la serie de Fibonacci, existe algo llamado representación de Zeckendorf. Básicamente, el teorema de Zeckendorf nos indica que todo número entero positivo puede escribirse como la suma de números no consecutivos de la serie de Fibonacci, exactamente de una manera.
Por ejemplo, la representación del número 100 es la suma 89 + 8 + 3, y si bien es verdad que existen otras formas de representarlo, solo hay una forma de hacerlo con Zeckendeforf. Para cualquier número entero positivo, la representación de Zeckendorf se puede encontrar en varios pasos: En cada uno de ellos, siempre elegimos el número Fibonacci más grande que al sumarse no haga que nuestro total se exceda del número objetivo. En el caso del número 100, primero tomamos el fibonacci 89, luego el 8, y finalmente el 3.
Dado un número entero positivo, escribe un programa que muestre su representación Zeckendorf.
La entrada contiene múltiples casos de prueba hasta fin de archivo.
Cada caso de prueba se describe en solamente una línea con un número entero X (1 = X = 1000000).
Por cada caso de prueba, imprime una línea con los términos de la representación de Zeckendorf de X, de mayor a menor, con un espacio entre cada término.
100 11
89 8 3 8 3