Pila Fibonacci. X44798


Statement
 

pdf   zip   tar

html

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:

Fn = Fn−1 + Fn−2

amb F1 = F2 = 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.

Public test cases

  • Input

    1
1
2
3
5
8
13
21
34
55
-1

    Output

    |55|
|34|
|21|
|13|
|8|
|5|
|3|
|2|
|1|
|1|
 =

sí

  • Input

    1
1
2
3
5
8
12
21
34
55
-1

    Output

    |55|
|34|
|21|
|12|
|8|
|5|
|3|
|2|
|1|
|1|
 =

no
    • Information
    Author
    PRO1-Vilanova
    Language
    Catalan
    Official solutions
    Make
    User solutions
    Make