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.

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 $a$ iš $b$ )
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;

long long DBD(long long a, long long b) {
    long long c;
    while (b > 0) {
        c = a;
        a = b;
        b = c % b;
    }
    return a;
}

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;

long long DBD(long long a, long long b) {
    return b == 0 ? a : DBD(b, a%b);
}

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;

long long MBK(long long a, long long b) {
    return a / DBD(a,b) * b;
}

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);

int visųDBD = 0; // po pirmo žingsnio taps lygiu m[0]
for(int i = 0; i < n; i++) {
    visųDBD = DBD(visųDBD, abs(m[i]));
}

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

int visųMBK = 1; // po pirmo žingsnio taps lygiu m[0]
for(int i = 0; i < n; i++) {
    visųMBK = MBK(visųMBK, abs(m[i]));
}

Išnašos

1: Su rekursija išsamiai susipažinsime Rekursija skyriuje.

Pirmasis algoritmas – Euklido algoritmas didžiausiam bendrajam dalikliui rasti¶

Didžiausias bendrasis daliklis ir mažiausias bendrasis kartotinis¶

Euklido algoritmas¶

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

Informatikos olimpiados: algoritmai ir taikymo pavyzdžiai

Navigacija

Related Topics