Codificación de Fibonacci

La codificación de Fibonacci http://bit.ly/1Lllqjv de un número n es una cadena d = d(0)d(1)…d(k-1)d(k) de ceros y unos tal que

donde F(i) es el i-ésimo término de la sucesión de Fibonacci

Por ejemplo, la codificación de Fibonacci de 4 es «1011» ya que los dos últimos elementos son iguales a 1 y

La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla

Definir la función

tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,

Comprobar con QuickCheck las siguientes propiedades:

  • Todo entero positivo se puede descomponer en suma de números de la sucesión de Fibonacci.
  • Las codificaciones de Fibonacci tienen como mínimo 2 elementos.
  • En las codificaciones de Fibonacci, la cadena «11» sólo aparece una vez y la única vez que aparece es al final.

Soluciones

El código se encuentra en GitHub.

Escribe tu solución