Formularea. Sunt date două numere naturale. Găsiți cel mai mare divizor comun.
Notă: cel mai mare divizor comun (abreviat ca GCD) a două numere naturale m și n este cel mai mare dintre divizorii lor comuni. Denumire: GCD (m. N).
Nota 2: divizorul comun al celor două numere pozitive este un număr natural, la care este un număr natural, care este un divizor al acestor două numere.
De exemplu, găsim GCD (12, 8):
Vom scrie toți divizorii numărului 12: 1, 2, 3, 4, 6, 12;
Noi scriem toți divizorii numărului 8: 1, 2, 4, 8;
Vom scrie toți divizorii comuni ai numerelor 12 și 8: 1, 2, 4. Dintre aceștia, cel mai mare număr este 4. Acesta este codul GCD al numerelor 12 și 8.
Soluția. Desigur, când decidem, nu vom scrie separatori și nu vom alege cel potrivit. În principiu, ar putea fi rezolvată ca o sarcină 15. Pornirea unui ciclu cu cel mai mic număr de două numere (deoarece acesta poate fi și un GCD, de exemplu, GCD (12, 4) = 4). Dar folosim așa-numitul algoritm Euclid de a găsi GCD, care este derivat prin metode matematice. În cel mai simplu caz, pentru numerele date m și n, se arată astfel:
1) Dacă este inegal, mergeți la pasul 2, altfel imprimați algoritmul;
3) Mergeți la pasul 1
După cum puteți vedea, la pasul 2, cel mai mare dintre cele două numere actuale este înlocuit cu diferența dintre cele mai mari și cele mai mici.
Să dăm un exemplu pentru numerele 12 și 8:
a. Deoarece 12> 8, înlocuim 1 2 cu 12 - 8 = 4;
b. Din moment ce 8> 4, înlocuim 8 cu 8 - 4 = 4;
Fără a face nici un raționament asupra algoritmului și nu ne dovedește corectitudinea, traducem descrierea sa într-o formă mai apropiată de Pascal:
Algoritmul în limbaj natural:
2) Pornirea unui ciclu cu precondiția m <>n. În ciclu:
1. Dacă m> n. apoi atribuiți variabila m la m-n. în caz contrar, atribuiți n variabilei n;
Trimiteți-le prietenilor: