F005A. Paraules de Fibonacci P50726


Statement
 

pdf   zip

html

Les paraules de Fibonacci F1, F2, F3, … es defineixen de la manera següent:

  • F1 = “a”.
  • F2 = “b”.
  • Per a tota n ≥ 3, Fn és el resultat de concatenar Fn−2 amb Fn−1.

Les set primeres paraules de la seqüència de Fibonacci són: F1 = “a”, F2 = “b”, F3 = “ab”, F4 = “bab”, F5 = “abbab”, F6 = “bababbab” i F7 = “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.
Public test cases
  • Input

    a
    b
    ba
    aaa
    bb
    bababbab
    

    Output

    a es la paraula numero 1
    b es la paraula numero 2
    ba no es de Fibonacci
    aaa no es de Fibonacci
    bb no es de Fibonacci
    bababbab es la paraula numero 6
    
  • Information
    Author
    Professorat de P1
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Python