|
|
| Line 1: |
Line 1: |
| == 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
| |
| <br>
| |
|
| |
| == 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>
| |
