Árboles de Fibonacci
Cualquier informático que se precie conoce los números de Fibonacci y ha implementado al menos una vez la función recursiva que los calcula. La definición de la función es:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n − 2) + fib(n − 1)
Hoy no implementaremos una vez más esa función, aunque sí trabajaremos con un concepto similar a los números de Fibonacci: los árboles de Fibonacci.
Entendemos por árbol de Fibonacci de tamaño n a aquel cuya raíz contiene el número de Fibonacci fib(n), cuyo hijo izquierdo representa el árbol de Fibonacci de tamaño n − 2 y el derecho el de n − 1. Evidentemente, los árboles de Fibonacci de tamaños 0 y 1 tienen únicamente un nodo raíz con el valor 0 y 1 respectivamente.
¿Podrías dibujar este tipo de árboles?
Entrada
La entrada estará compuesta por múltiples casos de prueba, cada uno en una línea. Cada caso de prueba consistirá en un número mayor o igual que cero que indicará el tamaño del árbol de Fibonacci que hay que dibujar. Un número negativo marcará el final de la entrada y no generará salida.
Salida
Para cada caso de prueba se dibujará el árbol de Fibonacci del tamaño solicitado. Después de cada árbol se escribirá una línea con cuatro símbolos de igual (====) para separar un caso de prueba de otro.
El dibujo del árbol se realizará de la siguiente forma:
- Si el árbol es vacío, escribirá [vacio] y después un retorno de carro.
- Si el árbol es un árbol hoja, escribirá el contenido de la raíz y un retorno de carro.
- Si el árbol tiene algún hijo, escribirá el contenido del nodo raíz, y recursivamente en las siguientes líneas el hijo izquierdo y después el hijo derecho. Los hijos izquierdo y derecho aparecerán tabulados, dejando tres espacios.
Entrada de ejemplo
0 1 2 3 -1
Salida de ejemplo
0
====
1
====
1
0
1
====
2
1
1
0
1
====