Problema número 200

Árboles de Fibonacci

Tiempo máximo: 3,000 sMemoria máxima: 4096 KiB

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
====