F005A. Paraules de Fibonacci P50726

Les paraules de Fibonacci $F_1, F_2, F_3, \dots$ es defineixen de la manera següent:

• $F_1 =$ “a”.

• $F_2 =$ “b”.

• Per a tota $n \ge 3$, $F_n$ és el resultat de concatenar $F_{n-2}$ amb $F_{n-1}$.

Les set primeres paraules de la seqüència de Fibonacci són: $F_1 =$ “a”, $F_2 =$ “b”, $F_3 =$ “ab”, $F_4 =$ “bab”, $F_5 =$ “abbab”, $F_6 =$ “bababbab” i $F_7 =$ “abbabbababbab”.

Feu un programa que, donada una sèrie de paraules, digui si són de Fibonnaci o no. Per a les que ho siguin, cal indicar la seva posició en la seqüència.

Entrada

L’entrada és una seqüència de paraules compostes només per les lletres a i b. Cap paraula tindrà més de 1000 lletres.

Sortida

Per a cada paraula, cal indicar la seva posició en la seqüència, o dir que no és de Fibonacci, seguint el format de l’exemple.

Pista

Fixeu-vos que la longitud de les paraules de Fibonacci creix molt de pressa. Per tant, hi ha molt poques paraules de Fibonacci de mida 1000 o menys (de fet, n’hi ha exactament 16). Calculeu-les totes a l’inici del programa.

Observacions

• Recordeu que un string s amb n caràcters c es pot declarar així: string s(n, c);

• Recordeu també que les operacions dels strings com ara s += ’a’; o bé s1 += s2; o bé s = s1 + s2; estan prohibides.