Pila Fibonacci. X44798

Feu la funció recursiva bool pilaFibonacci(stack<int> P); tal que, donada una pila d’enters positius, amb almenys dos elements, retorni true (false altrament) si la pila té empilada una seqüència de Fibonacci.

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

$$F_n = F_{n-1} + F_{n-2}$$

amb $F_1 = F_2 = 1$.

Tingueu en compte que tindrem en compte l’eficiència de la solució proposada. Per tant, per a fer una solució raonable possiblement hagueu de fer algun tipus d’immersió.

Solucions que consisteixin en copiar repetidament una pila i passar-la a una altra funció auxiliar possiblement no siguin massa eficients.

Entrada

La funció rep una pila d’enters positius amb almenys dos elements.

Sortida

true (false altrament) si la pila té empilada una seqüència de Fibonacci.

Observació

Heu d’enviar la solució comprimida en un fitxer .tar:

tar cvf program.tar pilaFibonacci.cpp

Observeu que per compilar us donem el Makefile, les utilitats d’entrada/sortida de piles a utilitats.hpp, la capçalera del mòdul funcional pilaFibonacci.hpp i el programa principal program.cpp.

Jutge.org també us donarà un semàfor verd si envieu una solució iterativa, però no serà correcte ja que l’enunciat del problema demana que la solució enviada sigui recursiva.