6507 - Fibo Gcd

Cerința

Se dau două numere naturale pozitive, n și m. Să se determine cel mai mare divizor comun (GCD) al celor două numere Fibonacci F(n) si F(m).

Date de intrare

Programul citește de la tastatură două numere naturale pozitive n și m.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse.". În următorul rând se va afișa pe ecran cel mai mare divizor comun GCD(F(n),F(m)), reprezentând cel mai mare divizor comun al lui F(n) si F(m).

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.".

Restricții și precizări

• 1 ⩽ n, m ⩽ 1000000

Exemplu 1

Intrare

10

15

Ieșire

Datele de intrare corespund restricțiilor impuse.

5

Rezolvare

<syntaxhighlight lang="python" line> def citeste_numere():

   try:
       numar_1 = int(input("Introduceți primul număr (n): "))
       numar_2 = int(input("Introduceți al doilea număr (m): "))
       return numar_1, numar_2
   except ValueError:
       return None, None

def valideaza_date(numar_1, numar_2):

   if 1 <= numar_1 <= 10 ** 9 and 1 <= numar_2 <= 10 ** 9:
       return True
   return False

def calculeaza_gcd(numar_1, numar_2):

   while numar_2:
       numar_1, numar_2 = numar_2, numar_1 % numar_2
   return numar_1

def calculeaza_fibonacci(k):

   if k == 0:
       return 0
   elif k == 1:
       return 1

   fib_0, fib_1 = 0, 1
   for _ in range(2, k + 1):
       fib_0, fib_1 = fib_1, fib_0 + fib_1
   return fib_1

def fibonacci_gcd(numar_1, numar_2):

   gcd_val = calculeaza_gcd(numar_1, numar_2)
   return calculeaza_fibonacci(gcd_val)

def main():

   numar_1, numar_2 = citeste_numere()

   if numar_1 is None or numar_2 is None:
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return

   if valideaza_date(numar_1, numar_2):
       print("Datele de intrare corespund restricțiilor impuse.")
       rezultat = fibonacci_gcd(numar_1, numar_2)
       print(rezultat)
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

if __name__ == "__main__":

   main()

</syntaxhighlight>