1023 - Cmmdc 3

Cerinţa

Se dă un sir cu n elemente, numere naturale nenule. Folosind metoda Divide et Impera, determinaţi cel mai mare divizor comun al elementelor acestui șir.

Date de intrare

Programul citește de la tastatură numărul n, iar cele n elemente ale șirului.

Date de ieşire

Programul afișează pe ecran numărul X, reprezentând cel mai mare divizor comun al elementelor.

Restricţii şi precizări

• 1 ≤ n ≤ 1000
• elementele șirului vor avea cel mult 9 cifre
• se recomandă folosirea metodei Divide et Impera

Exemplul 1

Date de intrare

7
18 54 24 42 108 60 30

Date de ieșire

6

Exemplul 2

Date de intrare

1001
123

Numerele introduse nu respectă restricțiile.<syntaxhighlight lang="python3" line="1"> def verifica_restrictii(n, arr):

   if 1 <= n <= 1000 and all(1 <= num <= 10**9 for num in arr):
       return True
   return False

def cmmd(x, y):

   while y:
       x, y = y, x % y
   return x

def cmmd_divide_et_impera(arr, start, end):

   if start == end:
       return arr[start]
   else:
       mid = (start + end) // 2
       left_cmmd = cmmd_divide_et_impera(arr, start, mid)
       right_cmmd = cmmd_divide_et_impera(arr, mid + 1, end)
       return cmmd(left_cmmd, right_cmmd)

def main():

   n = int(input("Introduceți numărul n: "))
   arr = list(map(int, input("Introduceți cele n elemente separate prin spațiu: ").split()))

   if verifica_restrictii(n, arr):
       rezultat = cmmd_divide_et_impera(arr, 0, n - 1)
       print("Cel mai mare divizor comun:", rezultat)
   else:
       print("Numerele introduse nu respectă restricțiile.")

if __name__ == "__main__":

   main()

</syntaxhighlight>