Examen Laboratori 2017 X91871

La seqüència de nombres de Fibonacci es defineix de la següent manera:

1. $F_0 = 1$.

2. $F_1 = 1$.

3. $F_n = F_{n-1} + F_{n-2}$, per a $n > 1$

Un nombre natural és un nombre de Fibonacci si es pot generar de manera recursiva amb aquesta definició.

Cal fer una funció que rebi un vector V no buit (és a dir, almenys té mida mes gran o igual que $1$) d’enters positius, els quals són tots estrictament més grans que $1$ i que torni TRUE si i només si tots els números que hi ha a V són nombres de Fibonacci.

Fixeu-vos que us demanem una funció que torni TRUE si i només si tots els números del vector són nombres de Fibonacci, i no pas que els números del vector formin una seqüència de Fibonacci.

Per a ajudar-vos a fer el programa, el vector V està ordenat. Això us ha d’ajudar a fer un programa més eficient que no pas si el vector V no estigués ordenat. Ara bé, si voleu, podeu fer el problema sense tenir en compte que v està ordenat.

Per exemple, si V és $[5, 13, 21, 34, 144]$ la funció tornarà TRUE, ja que tots els números que hi ha són nombres de Fibonacci, mentre que si V és $[2, 21, 89, 90, 114]$, la funció tornarà FALSE, ja que $90$ no és cap nombre de Fibonacci.

IMPORTANT! No feu cap assumpció sobre el contingut de V, només que està ordenat i prou i que té, almenys, un element. Segons les assumpcions que feu, podeu fer una solució que funcioni només en els exemples que us donem (públics), però no en tots (públics i privats).

Entrada

1 vector v ordenat d’enters.

Sortida

TRUE si i només si v només conté nombres de Fibonacci.