Sistemul de numerație Fibonacci

Sistemul de numeraţie zecimal se bazează pe cifrele {0,1,…,9} şi numerele 1,10,100,1000,… Cu ajutorul cifrelor şi numerelor respective putem reprezenta orice număr de formă: N = 538 = 5*100 + 3*10 + 8*1. Sistemul de numeraţie Fibonacci se bazează pe cifrele {0,1} şi pe firul lui Fibonacci:

$f_0=1$

$f_1=1$

$f_i=f_{i-1}+f_{i-2}$

$i \geq 2$

. În mod similar, orice număr M = c[n-1]…c[0] alcătuit din cifrele 0 și 1 poate fi reprezent în mod unic sub formă

$M = c[n-1]*f_{n-1}+c[n-2]*f_{n-2}+ \ldots + c[0]*f_0$

. De exemplu, M = 10101001 în baza Fibonacci reprezintă F = 1*21 + 0*13 + 1*8 + 0*5 + 1*3 + 0*2 + 0*1 + 1*1 = 33 în baza 10.

Să se elaboreze un program care:

transformă un număr natural din sistemul zecimal în sistemul Fibonacci.
transformă un număr din sistemul Fibonacci în sistemul zecimal.