F005A. Paraules de Fibonacci P50726

Les paraules de Fibonacci F₁, F₂, F₃, … es defineixen de la manera següent:

• F₁ = “a”.
• F₂ = “b”.
• Per a tota n ≥ 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₁ = “a”, F₂ = “b”, F₃ = “ab”, F₄ = “bab”, F₅ = “abbab”, F₆ = “bababbab” i F₇ = “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.