Pirmasis algoritmas – Euklido algoritmas didžiausiam bendrajam dalikliui rasti

Kartą mokinys, išmokęs savo pirmąją geometrijos teoremą,
paklausė Euklido: „Kokia man nauda, kad šitai išmoksiu?“.
Euklidas pakvietė savo vergą ir tarė: „Duok šiam žmogui
drachmą, nes jis turi turėti naudos iš to, ką išmoksta.“
J. Stobijus (Joannes Stobaeus), V a. pr. Kr.
Euklido portretas

Fig. 4 Euklido portretas

Šiame skyrelyje susipažinsime su seniausiu netrivialiu algoritmu, išlikusiu iki šių dienų. Tai algoritmas didžiausiam bendrajam dalikliui rasti. Nėra žinoma, kas šį algoritmą sugalvojo (ir ar tai buvo vienas žmogus). Dar prieš Euklidui (graikų k. Εὐκλείδης, Eukleides) aprašant šį algoritmą, jį savo veikale cituoja Aristotelis. Euklidas algoritmą kruopščiai aprašė garsiajame veikale „Pradmenys“ (apie 300 m. pr. Kr.), todėl algoritmui ir prigijo Euklido vardas.

Didžiausias bendrasis daliklis ir mažiausias bendrasis kartotinis

Prisiminkime didžiausio bendrojo daliklio (DBD) ir mažiausio bendrojo kartotinio (MBK) sąvokas.

Sakome, kad skaičius \mathbf{a} dalija skaičių \mathbf{b}, jei egzistuoja toks sveikasis skaičius k, kad b = ka; žymime a | b.

Pavyzdžiui, 5|30, nes 30 = 6 \cdot 5. Skaičius 1 dalija visus skaičius (1|a, visiems sveikiesiems a), o skaičių 0 dalija visi skaičiai, išskyrus patį 0 (a|0, visiems sveikiesiems a, a\neq0).

Dviejų neneigiamų skaičių a ir b didžiausiu bendruoju dalikliu (DBD) vadinamas didžiausias skaičius, dalijantis a ir b. Pavyzdžiui, DBD(12, 8) = 4, DBD(3, 6) = 3, DBD(7, 9) = 1.

Neneigiamų skaičių a ir b mažiausiu bendruoju kartotiniu (MBK) vadinamas mažiausias teigiamas skaičius, kurį dalija a ir b. Pavyzdžiui, MBK(12, 8) = 24, MBK(3, 6) = 6, MBK(7, 9) = 63.

Natūralus būdas rasti DBD(a, b) – išskaidyti skaičius a ir b pirminiais daugikliais ir išrinkti visus bendruosius šių skaičių pirminius daugiklius. Pavyzdžiui, 12 = \mathbf{2 \cdot 2} \cdot 3, 8 = \mathbf{2 \cdot 2} \cdot 2, bendrieji daugikliai yra \mathbf{2 \cdot 2}, taigi DBD(12, 8) = 4. Šiuo būdu tarsi konstruojame DBD, stengdamiesi jį padaryti kuo didesnį (rinkdami kuo daugiau skaičiaus a pirminių daugiklių), tačiau žiūrėdami, kad DBD dalytų ir skaičių b.

MBK(a, b) taip pat galime rasti išskaidę skaičius a ir b į pirminius daugiklius. Kadangi a|MBK(a, b), tai MBK turi priklausyti visi a pirminiai daugikliai. Tačiau ir b|MBK(a, b), todėl pridedame skaičiaus b pirminius daugiklius, kurių trūksta (būtent, daugiklius, kurie nėra bendrieji skaičiams a ir b). Pavyzdžiui, MBK(12, 8) = 2 \cdot 2 \cdot 3 \cdot 2 = 24.

Šie DBD ir MBK konstravimo būdai paaiškina ir šiuos skaičius siejančią lygybę: DBD(a, b) \cdot MBK(a, b) = a \cdot b.

Euklido algoritmas

An algorithm must be seen to be believed.
Algoritmą reikia pamatyti, kad juo patikėtum.
Donaldas Knutas (Donald Knuth)

Tarkime, reikia rasti skaičių a ir b didžiausiąjį bendrą daliklį. Atliekame tokius veiksmus:

  • jei b = 0, tai DBD(a, b) lygus a, priešingu atveju a_{2} = b, b_{2} = a mod b (lygus liekanai, gautai padalijus ab)

  • jei b_{2} = 0, tai DBD(a, b) lygus a_{2}, priešingu atveju a_{3} = b_{2}, b_{3} = a_{2} mod b_{2}

  • jei b_k = 0, tai DBD(a, b) lygus a_k, priešingu atveju a_{k+1} = b_{k}, b_{k+1} = a_{k} mod b_{k}.

Kadangi dalydami iš skaičiaus n galime gauti liekaną nuo 0 iki n-1, tai b > b_{2} > \cdots > b_{k} > \cdots > b_{n} = 0, ir algoritmas atliks baigtinį skaičių veiksmų (anksčiau ar vėliau b_{i} taps lygus 0, tad algoritmas baigs darbą).

Raskime skaičių a = 12 ir b = 8 DBD naudodamiesi Euklido algoritmu:

  • b > 0, taigi skaičiuojame a_{2} = b = 8, b_{2} = a mod b = 12 mod 8 = 4.

  • b_{2} > 0, taigi skaičiuojame a_{3} = b_{2} = 4, b_{3} = a_{2} mod b_{2} = 8 mod 4 = 0.

  • b_{3} = 0, taigi DBD(a, b) = a_{3} = 4.

Gavome DBD(12, 8) = 4. Užrašysime Euklido algoritmą Paskalio ir C++ kalbomis.

function DBD(a, b : longint) : longint;
  var c : longint;
begin
  while b > 0 do begin
    c := a;
    a := b;
    b := c mod b;
  end;
  DBD := a;
end;

Jei reikia rasti dviejų skaičių DBD, tačiau nežinome, ar jie teigiami, funkciją iškviečiame perduodami skaičių modulius: DBD(abs(a), abs(b)).

Euklido algoritmas yra teisingas, nes remiasi sąryšiu: DBD(a, b) = DBD(b, a mod b). Šio sąryšio teisingumu nesunku įsitikinti pasinaudojus lygybe:

a = (a div b) \cdot b + a mod b.

Du skaičiai turi vieną ir tik vieną didžiausiąjį bendrą daliklį. Tarkime, DBD(a, b) = d. Daliklis d dalija skaičių a ir taip pat dalija jo dalį (a div b) \cdot b, todėl turi dalyti ir likusią skaičiaus a dalį – a mod b. Taigi skaičių a ir b didžiausias bendrasis daliklis yra ir (mažesnių) skaičių poros b ir a mod b didžiausias bendrasis daliklis, t. y. DBD(a, b) = d = DBD(b, a mod b).

Pamėginkime įvertinti Euklido algoritmo sudėtingumą. Pasiremsime nelygybe n mod m < n/2, kur n ir m – sveikieji neneigiami skaičiai ir n \geq m.

Nelygybė teisinga, nes:

  • jei m \leq n/2, tuomet n mod m < m \leq n/2;

  • jei m > n/2, tuomet n div m = 1; tada lygybę n = (n div m) m + n mod m perrašome: n = m + n mod m; gauname n mod m = n - m < n - n/2 = n/2.

Tarkime, kad a > b (jei taip nėra, tai atliekant ciklą pirmąjį kartą, šie skaičiai bus sukeisti vietomis). Ciklo viduje atliekamas operacijas galime laikyti elementariomis, tad Euklido algoritmo sudėtingumas tiesiog proporcingas tam, kiek kartų bus atliekamas ciklas while.

Panagrinėkime, kaip keičiasi kintamųjų a ir b reikšmės vykdant while ciklą. Sakykime, pradinės šių kintamųjų reikšmės yra a_0 ir b_0. Po pirmos ciklo iteracijos a_1 = b_0, o b_1 = a_0 mod b_0 < a_0/2. Po antros iteracijos a_2 = b_1 < a_0/2, o b_2 = a_1 mod b_1 < a_2. Gavome, kad atlikus dvi ciklo iteracijas, pirmojo kintamojo reikšmė sumažėja daugiau negu dvigubai ir dar vis galioja a \geq b. Po keturių iteracijų pirmojo kintamojo reikšmė bus daugiau nei keturis kartus mažesnė už pradinę ir t. t. Taigi matyti, kad ciklas bus vykdomas ne daugiau kaip 2 \log{a} kartų. Dabar jau nesunku įvertinti, kad Euklido algoritmo sudėtingumas yra O(\log{a}).

Kadangi Euklido algoritmas apibrėžiamas rekurentiniais sąryšiais:

DBD(a, b) = a, jei b = 0
DBD(a, b) = DBD(b, a mod b), jei b > 0

tai Euklido algoritmą nesunku užrašyti rekursyvia 1 funkcija:

function DBD(a, b : longint) : longint;
begin
  if b = 0 then
    DBD := a
  else
    DBD := DBD(b, a mod b);
end;

Pastebėkime, kad jei a < b, algoritmas pirmu žingsniu šiuos skaičius sukeičia vietomis, pavyzdžiui, DBD(24, 54) = DBD(54, 24) = DBD(24, 6) = DBD(6, 0) = 6.

Beje, pats Euklidas šį algoritmą aprašė kiek kitaip. Mat graikų matematikai nelaikė, kad vienetas dalija kitą teigiamą skaičių. Buvo galimi trys variantai: arba du teigiami sveikieji skaičiai yra abu lygūs vienetui, arba tarpusavyje pirminiai, arba turi bendrą didžiausią daliklį. Vienetas netgi nebuvo laikomas skaičiumi, o nulis apskritai neegzistavo.

Euklido algoritmo taikymas, mažiausio bendrojo kartotinio (MBK) radimas

Didžiausiojo bendrojo daliklio gali prireikti sprendžiant įvairius skaičiavimo uždavinius. Vienas iš pavyzdžių – prastinant trupmenas, skaitiklį ir vardiklį reikia padalyti iš didžiausio jų bendrojo daliklio.

Euklido algoritmas leidžia efektyviai apskaičiuoti ir mažiausią bendrąjį kartotinį:

function MBK(a, b : longint) : longint;
begin
  MBK := a * b div DBD(a, b);
end;

Pastaba

Svarbu nepamiršti, kad longint tipo kintamieji gali saugoti reikšmes, ne didesnes negu 2^{31} - 1. Taigi MBK bus skaičiuojamas teisingai tik tuo atveju, kai skaičius a ir b sandauga neviršija šio skaičiaus.

Naudodamiesi Euklido algoritmu galime rasti ne tik dviejų, bet ir keleto skaičių DBD bei MBK. Kadangi DBD(a, b, c) = DBD(DBD(a, b), c), ir MBK(a, b, c) = MBK(MBK(a, b), c). Šias lygybes suprasti ir įrodyti nesunku įsivaizduojant, kaip konstruotume DBD ir MBK iš skaičių a, b ir c pirminių daugiklių.

Tarkime, masyve m yra k sveikųjų skaičių. Pateiksime fragmentą, randantį visų k skaičių DBD ir MBK:

visųDBD := 0; { po pirmo žingsnio taps lygiu m[1] }
for i := 1 to k do
  visųDBD := DBD(abs(m[i]), visųDBD);
visųMBK := 1; { po pirmo žingsnio taps lygiu m[1] }
for i := 1 to k do
  visųMBK := MBK(abs(m[i]), visųMBK);

Išnašos

1

Su rekursija išsamiai susipažinsime Rekursija skyriuje.