4262 - FiboRec

Cerința

Scrieți funcția recursivă cu antetul
def FiboRec(x, y)
care primind ca parametri două numere întregi x și y, returnează 1 dacă x și y și sunt doi termeni consecutivi ai șirului Fibonacci, sau returnează 0 în caz contrar.

Restricții și precizări

• Primii zece termeni ai șirului Fibonacci sunt: 1,1,2,3,5,8,13,21,34,55.
• Dacă x și y sunt termeni consecutivi ai șirului Fibonacci, atunci trebuie ca x ≤ y.
• Se recomandă utilizarea recursivității în rezolvarea problemei.

Exemplu

FiboRec(1, 1) = 1, FiboRec(3, 5) = 1, FiboRec(7, 8) = 0, FiboRec(8, 5) = 0, FiboRec(5, 8) = 1.

Explicație

Această funcție recursivă primește ca argumente două numere întregi pozitive x și y, iar scopul ei este de a verifica dacă y se poate obține prin adunarea lui x cu un număr de termeni consecutivi din șirul lui Fibonacci.

Șirul lui Fibonacci este definit astfel: primul termen este 1, al doilea termen este 1, iar fiecare termen următor este suma celor două precedente. Deci, primii termeni ai șirului sunt: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Funcția utilizează recursivitatea pentru a verifica dacă y poate fi obținut prin adunarea lui x cu un număr de termeni consecutivi din șirul lui Fibonacci. Dacă x și y sunt egale, atunci y poate fi obținut prin adunarea lui x cu zero termeni, deci funcția returnează 1.

Dacă x este mai mare decât y sau y este mai mic decât 1, atunci nu se poate obține y prin adunarea lui x cu un număr de termeni consecutivi din șirul lui Fibonacci, așa că funcția returnează 0.

În caz contrar, funcția calculează diferența dintre y și x și o folosește ca prim argument într-un nou apel al funcției FiboRec, iar al doilea argument devine x. Astfel, dacă diferența dintre y și x se găsește în șirul lui Fibonacci, atunci funcția va returna 1.

Rezolvare

<syntaxhighlight lang="python"> def validate_FiboRec(x, y):

   if isinstance(x, int) and isinstance(y, int) and x <= y and y > 0:
       return True
   else:
       return False

def FiboRec(x, y):

   if x == y:
       return 1
   elif x > y or y < 1:
       return 0
   else:
       return FiboRec(y - x, x)

def main():

   x = input("Introduceti valoarea lui x: ")
   y = input("Introduceti valoarea lui y: ")
   try:
       x = int(x)
       y = int(y)
       if validate_FiboRec(x, y):
           result = FiboRec(x, y)
           if result == 1:
               print(f"Numerele {x} si {y} sunt consecutive in sirul Fibonacci.")
           else:
               print(f"Numerele {x} si {y} nu sunt consecutive in sirul Fibonacci.")
       else:
           print("Valorile introduse nu sunt valide.")
   except ValueError:
       print("Valorile introduse nu sunt numere intregi.")

</syntaxhighlight>