Algoritmul lui Euclid în C++. CMMDC și CMMMC

Algoritmul lui Euclid în C++. CMMDC și CMMMC

În acest articol voi prezenta conceptele de CMMDC (cel mai mare divizor comun) și CMMMC (cel mai mic multiplu comun), precum și Algoritmul lui Euclid, atât prin scăderi repetate, cât și prin împărțiri repetate. La final, vom discuta despre câteva aplicații la CMMDC și CMMMC.

Cel mai mare divizor comun (CMMDC)

Cel mai mare divizor comun a două numere naturale aa și bb este efectiv cel mai mare număr natural care îl divide atât pe aa cât și pe bb Acesta se notează cmmdc(a,b)\cmmdc(a, b) gcd(a,b)\gcd(a, b) (de la greatest common divisor) sau pur și simplu (a,b)(a, b)

De exemplu, (20,24)=4(20, 24) = 4 (6,3)=3(6, 3) = 3 (14,5)=1(14, 5) = 1 și (0,18)=18(0, 18) = 18 Există un singur caz în care valoarea (a,b)(a, b) nu e definită, și anume atunci când a=b=0a = b = 0 Asta pentru că 00 este divizibil cu toate numerele naturale nenule. Nu putem spune că (a,b)=(a, b) = \infty

Să luăm un exemplu mai mare: a=229320a = 229\,320 și b=996072b = 996\,072 Dacă descompunem în factori primi numerele aa bb și (a,b)(a, b) obținem:

a=229320=23325172131b=996072=233173112(a,b)=1176=233172\begin{align*} a = 229\,320 &= \textcolor{dodgerblue}{2}^{\textcolor{orangered}{3}} \cdot \textcolor{dodgerblue}{3}^2 \cdot 5^1 \cdot \textcolor{dodgerblue}{7}^{\textcolor{orangered}{2}} \cdot 13^1\\ b = 996\,072 &= \textcolor{dodgerblue}{2}^3 \cdot \textcolor{dodgerblue}{3}^{\textcolor{orangered}{1}} \cdot \textcolor{dodgerblue}{7}^3 \cdot 11^2\\ (a, b) = 1\,176 &= \textcolor{dodgerblue}{2}^{\textcolor{orangered}{3}} \cdot \textcolor{dodgerblue}{3}^{\textcolor{orangered}{1}} \cdot \textcolor{dodgerblue}{7}^{\textcolor{orangered}{2}} \end{align*}

De aici observăm că putem defini CMMDC-ul a două numere drept produsul dintre factorii lor comuni luați la cea mai mică putere. Este cât se poate de logic: Dacă am scădea puterea unui factor din descompunerea lui (a,b)(a, b) am obține un CMMDC mai mic, iar dacă am mări-o, cel puțin unul dintre cele două numere nu va mai fi divizibil cu noul CMMDC.

Cel mai mic multiplu comun (CMMMC)

Cel mai mic multiplu comun a două numere naturale nenule este cel mai mic număr natural nenul care este divizibil atât cu aa cât și cu bb Acesta se notează cmmmc(a,b)\cmmmc(a, b) lcm(a,b)\lcm(a, b) (de la least common multiple) sau [a,b][a, b] De exemplu, [20,24]=120[20, 24] = 120 [3,5]=15[3, 5] = 15 [12,4]=12[12, 4] = 12 și [1,7]=1[1, 7] = 1

Din nou, vom lua un exemplu mai complex ca să analizăm descompunerile în factori primi ale numerelor aa bb și [a,b][a, b] Fie a=840a = 840 și b=126b = 126

a=840=23315171b=126=213271[a,b]=2520=23325171\begin{align*} a = 840 &= 2^{\textcolor{orangered}{3}} \cdot 3^1 \cdot 5^{\textcolor{orangered}{1}} \cdot 7^{\textcolor{orangered}{1}}\\ b = 126 &= 2^1 \cdot 3^{\textcolor{orangered}{2}} \cdot 7^1\\ [a, b] = 2\,520 &= 2^{\textcolor{orangered}{3}} \cdot 3^{\textcolor{orangered}{2}} \cdot 5^{\textcolor{orangered}{1}} \cdot 7^{\textcolor{orangered}{1}} \end{align*}

De aici, putem observa că CMMMC-ul a două numere este egal cu produsul dintre factorii lor comuni și necomuni luați la cea mai mare putere.

Algoritmul lui Euclid prin scăderi repetate

Algoritmul lui Euclid este o metodă foarte simplă și eficientă de a calcula CMMDC-ul a două numere. Există două variante ale Algoritmului lui Euclid: una prin scăderi repetate și cealaltă prin împărțiri repetate. Prima nu este nici pe departe la fel de eficientă precum a doua, dar voi începe cu ea pentru că ne ajută să înțelegem mai ușor varianta prin împărțiri.

Algoritmul lui Euclid prin scăderi repetate presupune să scădem la fiecare pas numărul mai mic din numărul mai mare, până când unul dintre ele devine 00 La final, valoarea numărului care a rămas nenul va fi egală cu (a,b)(a, b)

while (a && b)
if (a > b)
a -= b;
else
b -= a;
cout << a + b << '\n';

(Afișăm a+ba + b pentru că această valoare este egală cu numărul care nu a devenit 00

Se observă că algoritmul acesta modifică valorile inițiale ale variabilelor aa și bb Deci, dacă avem nevoie de ele mai târziu, putem să le facem copii la început, și să folosim copiile în cadrul algoritmului. Sau, mai simplu, definim o funcție gcd, care primește ca parametri numerele aa și bb și returnează (a,b)(a, b)

// ...
int gcd(int a, int b) {
while (a && b)
if (a > b)
a -= b;
else
b -= a;
return a + b;
}
// ...
int main() {
int a, b; cin >> a >> b;
cout << gcd(a, b) << '\n';
return 0;
}

Explicație

Să vedem de ce algoritmul furnizează întotdeaua rezultatul corect. Practic, el se bazează pe următoarea relație de recurență:

gcd(a,b)={gcd(ab,b)pentru a>bapentru b=0\gcd(a, b) = \begin{cases} \gcd(a - b, b) & \text{pentru } a \gt b\\ a & \text{pentru } b = 0 \end{cases}

Al doilea caz este trivial, iar primul se justifică astfel:

Notăm c=abc = a - b Fie dd un divizor oarecare al lui bb

  • Dacă dad \mid a atunci, știind că dbd \mid b rezultă că dabd \mid a - b adică dcd \mid c
  • Dacă dcd \mid c atunci, știind că dbd \mid b rezultă că dc+bd \mid c + b adică dad \mid a

Mai pe scurt, db(dadc)d \mid b \to (d \mid a \leftrightarrow d \mid c) Cu alte cuvinte, perechile (b,a)(b, a) și (b,c)(b, c) au aceeași mulțime de divizori comuni. Așadar, cel mai mare divizor comun al fiecărei perechi trebuie și el să fie același. Adică, gcd(a,b)=gcd(b,c)\gcd(a, b) = \gcd(b, c)

Exemplu CMMDC

Exemple

Iată o animație care ilustrează modul în care funcționează Algoritmul lui Euclid prin scăderi repetate pe trei perechi de numere: (5,18)(5, 18) (20,24)(20, 24) și (60,35)(60, 35)

Complexitate

După cum am spus mai sus, această variantă a algoritmului nu este eficientă. De exemplu, dacă a=109a = 10^9 și b=1b = 1 se vor efectua un miliard de operații, ceea ce este enorm. Putem spune deci că Algoritmul lui Euclid prin scăderi repetate are complexitatea O(a+b)O(a + b)

Algoritmul lui Euclid prin împărțiri repetate

Să ne uităm cum evoluează perechea de numere (a,b)=(18,5)(a, b) = (18, 5) în cazul algoritmului precedent:

(18,5)(13,5)(8,5)(3,5)(18, 5) \to (13, 5) \to (8, 5) \to (3, 5)

L-am scăzut pe bb din aa până când aa a devenit mai mic decât bb Practic, am simulat procesul de împărțire a lui aa la bb prin scăderi repetate. Astfel, la final aa a devenit amodba \modd b adică restul împărțirii lui aa la bb Așadar, putem optimiza algoritmul inițial împărțind la fiecare pas numărul mai mare la cel mai mic, și reținând în acesta restul împărțirii. În cazul de mai sus economisim doi pași, însă în cazul (a,b)=(109,1)(a, b) = (10^9, 1) economisim un miliard de pași.

while (a && b)
if (a > b)
a %= b;
else
b %= a;
cout << a + b << '\n';

Iată și o implementare ceva mai elegantă:

while (b) {
int r = a % b;
a = b;
b = r;
}
cout << a << '\n';

La fiecare pas, îl copiem pe bb în aa și pe rr (restul împărțirii) în bb menținând astfel invariantul a>ba \gt b Numai la primul pas este posibil ca acesta să nu fie îndeplinit. Dacă inițial a=ba = b algoritmul se termină într-un pas, iar dacă a<ba \lt b numerele se inversează după primul pas, aa devenind mai mare decât bb

Complexitate

Să luăm din nou exemplul acela mare de la începutul articolului. Avem:

(229320,996072)(996072,229320)(229320,78792)(78792,71736)(71736,7056)(7056,1176)(1176,0)\begin{align*} (229\,320, 996\,072) & \to (996\,072, 229\,320) \to (229\,320, 78\,792) \to (78\,792, 71\,736)\\ & \to (71\,736, 7\,056) \to (7\,056, 1\,176) \to (1\,176, 0) \end{align*}

Numărul de pași efectuați este foarte mic în comparație cu numerele inițiale, ceea ce ne face să intuim că algoritmul are o complexitate de ordinul O(log(a+b))O(\log(a + b)) Se întâmplă ca intuiția să fie corectă, iar mai jos aveți demonstrația. E doar pentru cei interesați; în niciun caz nu aveți nevoie de ea la școală. Pentru clasa a noua, e suficient să știți că Algoritmul lui Euclid este… extrem de rapid.

Vom analiza trei iterații consecutive ale algoritmului. Perechea (a,b)(a, b) devine (b,c)(b, c) unde c=amodbc = a \modd b iar (b,c)(b, c) devine (c,d)(c, d) unde d=bmodcd = b \modd c Considerăm că a>ba \gt b de unde și b>cb \gt c și c>dc \gt d

(a,b)(b,c)(c,d)(a, b) \to (b, c) \to (c, d)

Știm că d=bmodcd = b \modd c adică b=qc+db = qc + d pentru un qq natural. Dar b>c>db \gt c \gt d așa că q1q \ge 1 Prin urmare,

bc+db \ge c + d

Dar a>ba \gt b deci mai avem că

a>c+da \gt c + d

Adunând cele două relații, obținem că

a+b>2(c+d)a + b \gt 2(c + d)

Așadar, la fiecare două iterații, suma valorilor aa și bb devine de cel puțin două ori mai mică. Asta înseamnă că numărul maxim de iterați din while este aproximativ 2[log2(a+b)]2[\log_2(a + b)] În concluzie, complexitatea algoritmului este de ordinul O(log(a+b))O(\log(a + b)) În caz că vă întrebați, cel mai nefavorabil caz este cel în care numerele date sunt termeni consecutivi din Șirul lui Fibonacci, dar nu mai intru în detalii.

Formula pentru CMMMC

CMMMC-ul poate fi calculat foarte ușor folosind următoarea formulă:

(a,b)[a,b]=ab(a, b) \cdot [a, b] = a \cdot b

De aici îl scoatem pe [a,b][a, b] drept ab/(a,b)a \cdot b \mathbin{/} (a, b) Înmulțirea și împărțirea se efectuează în timp constant, motiv pentru care complexitatea calculării CMMMC-ului este egală cu cea a calculării CMMDC-ului, adică O(log(a+b))O(\log(a + b))

int lcm(int a, int b) {
return a * b / gcd(a, b);
}

Să demonstrăm formula. Reamintesc că CMMDC-ul este produsul factorilor comuni la cea mai mică putere, iar CMMMC-ul este produsul factorilor comuni și necomuni la cea mai mare putere. Ei bine, putem reformula prima definiție. Putem considera că CMMDC-ul este produsul factorilor comuni și necomuni la cea mai mică putere, dacă prin asta înțelegem că un factor care nu apare în ambele numere se va lua la puterea 00 Deci, dacă un factor pp apare la puterea xx în aa și la yy în bb știm că în (a,b)(a, b) va apărea la puterea min(x,y)\min(x, y) iar în [a,b][a, b] la max(x,y)\max(x, y) Când înmulțim (a,b)(a, b) cu [a,b][a, b] exponentul lui pp va deveni min(x,y)+max(x,y)\min(x, y) + \max(x, y) care este tot una cu x+yx + y Așadar, (a,b)[a,b]=ab(a, b) \cdot [a, b] = a \cdot b

CMMDC și CMMMC pentru mai multe numere

Cum calculăm CMMDC-ul și CMMMC-ul pentru mai mult de două numere? În cazul CMMDC-ului e simplu. Luăm primele două numere, le calculăm CMMDC-ul, apoi calculăm CMMDC-ul dintre acest CMMDC și numărul următor și așa mai departe.

gcd(a,b,c)=gcd(gcd(a,b),c)\gcd(a, b, c) = \gcd(\gcd(a, b), c)

În cazul CMMMC-ului putem fi tentați să generalizăm formula cu produsul, însă ea nu funcționează pentru mai mult de două numere. Dacă ați înțeles demonstrația de mai sus, ar trebui să fie clar de ce. Ne rămâne să procedăm la fel, adică să luăm câte două numere și să le calculăm CMMMC-ul.

lcm(a,b,c)=lcm(lcm(a,b),c)\lcm(a, b, c) = \lcm(\lcm(a, b), c)

Aplicații

În continuare, voi prezenta cinci probleme legate de CMMDC și CMMMC.

Problema 1.

Se dau două numere naturale nenule aa și bb Să se determine dacă cele două numere sunt prime între ele. Două numere se numesc prime între ele, coprime sau relativ prime dacă singurul lor divizor comun este 11

Testăm pur și simplu dacă gcd(a,b)=1\gcd(a, b) = 1 By the way, două numere consecutive sunt întotdeauna prime între ele. Ca să aibă un divizor comun pp trebuie ca diferența lor să fie divizibilă cu pp Cum diferența dintre aa și bb este 11 singura valoare posibilă a lui pp este 11

bool relativePrimes(int a, int b) {
return gcd(a, b) == 1;
}

Problema 2.

Se dau două fracții a/ba / b și c/dc / d Știind că aa bb cc și dd sunt numere naturale, iar bb și dd sunt nenule, să se afișeze suma celor două fracții sub forma unei fracții ireductibile e/fe / f

ab+cd=ad+cbbd\frac{a}{b} + \frac{c}{d} = \frac{ad + cb}{bd}

O fracție x/yx / y este ireductibilă dacă gcd(x,y)=1\gcd(x, y) = 1 Deci, ca să aducem o fracție x/yx / y la forma sa ireductibilă, trebuie să o simplificăm prin gcd(x,y)\gcd(x, y)

int e = a * d + c * b;
int f = c * d;
int g = gcd(e, f);
cout << e / g << " / " << f / g << '\n';

În caz că numerele date sunt mari, ar trebui să evităm pe cât posibil calculele ale căror rezultat ar putea depăși valoarea maximă a tipului int. În acest sens, putem aduce din start fracțiile date la forma lor ireductibilă. În plus, când le aducem la un numitor comun, ar fi bine să alegem ca acesta să fie lcm(b,d)\lcm(b, d)

int gcdAB = gcd(a, b); a /= gcdAB; b /= gcdAB;
int gcdCD = gcd(c, d); c /= gcdCD; d /= gcdCD;
int lcmBD = lcm(b, d);
a *= lcmBD / b;
c *= lcmBD / d;
int e = a + c;
int f = lcmBD;
int gcdEF = gcd(e, f);
e /= gcdEF;
f /= gcdEF;
cout << e << " / " << f << '\n';

Problema 3.

O instalație de Crăciun consistă din n1n \ge 1 becuri de diferite culori. Știind că inițial toate becurile sunt aprinse și că fiecare bec ii (cu 1in1 \le i \le n se aprinde din tit_i în tit_i secunde, să se determine după cât timp toate becurile vor fi aprinse simultan din nou.

Răspunsul trebuie să fie divizibil cu fiecare dintre timpii dați. Cum ne interesează prima dată când toate becurile vor fi aprinse din nou, vom calcula lcm(t1,t2,,tn)\lcm(t_1, t_2, \ldots, t_n)

int ans = 1;
for (int i = 1; i <= n; i++)
ans = lcm(ans, t[i]);
cout << ans << '\n';

Problema 4.

Se consideră un dreptunghi de dimensiuni a×ba \times b Să se determine numărul minim de pătrate congruente în care poate fi împărțit dreptunghiul dat, precum și lungimea laturii acestora.

De exemplu:

CMMDC. Problema 4.

Se observă că lungimea laturii ll alese trebuie să fie divizibilă atât cu aa cât și cu bb Cum noi vrem ca a/la / l și b/lb / l să fie cât mai mici posibil, ll trebuie să fie cât mai mare. Deci, ll nu poate fi decât gcd(a,b)\gcd(a, b) Numărul pătratelor va fi ab/l2ab / l^2

int l = gcd(a, b);
cout << a * b / l / l << ' ' << l << '\n';

Problema 5.

Se dau două puncte în plan AA și BB ambele de coordonate întregi. Să se determine numărul punctelor laticeale de pe segmentul [AB][AB] Prin punct laticeal înțelegem punct de coordonate întregi.

De exemplu:

CMMDC. Problema 5.

Dacă înșiruim punctele laticeale de pe segmentul [AB][AB] în funcție de cât de apropiate sunt de punctul AA vom observa că fiecare două puncte consecutive determină câte un dreptunghi. Cum dreptunghiurile determinate sunt congruente, lățimea lor trebuie să dividă lățimea dreptunghiului mare (determinat de AA și BB iar lungimea lor trebuie să dividă lungimea dreptunghiului mare. Asta înseamnă că numărul dreptunghiurilor mici trebuie să dividă gcd(a,b)\gcd(a, b) unde a=xAxBa = |x_A - x_B| iar b=yAyBb = |y_A - y_B|

Totuși, numărul nu are de ce să fie mai mic decât gcd(a,b)\gcd(a, b) pentru că dimensiunile dreptunghiurilor n-ar mai fi prime între ele, așa că fiecare dreptunghi ar putea fi împărțit în două sau mai multe dreptunghiuri cu colțuri în puncte laticeale. Deci, numărul de dreptunghiuri este gcd(a,b)\gcd(a, b) ceea ce înseamnă că numărul punctelor căutate este gcd(a,b)+1\gcd(a, b) + 1

int latticePoints(int xA, int yA, int xB, int yB) {
return gcd(abs(xA - xB), abs(yA - yB)) + 1;
}

Sfârșit! Urmează în curând un articol despre descompunerea unui număr în factori primi și aplicațiile acesteia. Dacă aveți vreo întrebare despre CMMDC, CMMMC sau Algoritmul lui Euclid, nu ezitați să o adresați mai jos, într-un comentariu :smile:

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii