324
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
Exemplu
Date de intrare
718 54 24 42 108 60 30
Date de ieșire
6
#include <bits/stdc++.h> using namespace std; int n , v[1005]; int Cmmdc2(int a, int b) { if(b == 0) return a; else return Cmmdc2(b , a % b); } int Cmmdc(int st, int dr) { if(st == dr) return v[st]; else { int mij = (st + dr) / 2; int x = Cmmdc(st ,mij); int y = Cmmdc(mij + 1 , dr); return Cmmdc2(x , y); } } int main(){ cin >> n; for(int i = 0 ; i < n ; i ++) cin >> v[i]; cout << Cmmdc(0 , n - 1); return 0; }
Comentarii