ODREĐIVANJE NZD I NZS POMOĆU EUKLIDOVOG ALGORITMA
Euklidov algoritam je dobio naziv po Grčkom matematičaru Euklidu i koristi se za efikasno određivanje najvećeg zajedničkog delioca, kao i određivanje najmanjeg zajedničkog sadržalaca dva ili više celih brojeva.
Određivanje najvećeg zajedničkog delioca NZD
Oređivanje NZD-a dva broja A i B zasniva se na činjenici da:
I A i B su deljivi sa NZD
Ostatak deljenja A i B je takođe deljiv sa NZD
To znači da ako su A i B celi brojevi čiji se NZD traži, i ako označimo da je d=NZD, p-rezultat deljenja a q-ostatak deljenja, onda se može napisati:
A = p*B+q , p i q su celi brojevi
Dakle, A, B i q su deljivi sa d
Pogledajmo to na sledećem primeru za brojeve A=48 i B=28
Odredimo prvo NZD:
I A i B su deljivi sa NZD
Ostatak deljenja A i B je takođe deljiv sa NZD
To znači da ako su A i B celi brojevi čiji se NZD traži, i ako označimo da je d=NZD, p-rezultat deljenja a q-ostatak deljenja, onda se može napisati:
A = p*B+q , p i q su celi brojevi
Dakle, A, B i q su deljivi sa d
Pogledajmo to na sledećem primeru za brojeve A=48 i B=28
Odredimo prvo NZD:
Slika 1: Određivanje NZD-a pomoću Euklidovog algoritma
Na slici pod a je prikazan klasičan način određivanja NZD-a i to je u ovom slučaju 4.
Na slici pod b se vidi da se NZD sadrži i u broju 48 i 28, ali i u ostatku deljenja ta dva broja. Dakle, možemo reći da:
48=1*28+20
što odgovara izrazu 1:
A = p*B+q , p i q su celi brojevi
Vidi se na slici pod b) da će B i q biti deljivi sa NZD.
Ako sada uzmemo da tražimo NZD za B i q, tj. za 28 i 20 videli bi smo da je NZD isti.
Ponavljanjem postupka deljenja prethodnog delioca sa ostatkom deljenja sve dok u jednoj iteraciji ostatak deljenja ne bude nula, doći ćemo do broja koji predstavlja NZD. Poslednji rezultat deljenja je zapravo broj koji tražimo. U našem primeru, to je broj 4. Vidi sliku pod c).
Prethodni postupak je poznat kao Euklidov algoritam.
Na slici pod b se vidi da se NZD sadrži i u broju 48 i 28, ali i u ostatku deljenja ta dva broja. Dakle, možemo reći da:
48=1*28+20
što odgovara izrazu 1:
A = p*B+q , p i q su celi brojevi
Vidi se na slici pod b) da će B i q biti deljivi sa NZD.
Ako sada uzmemo da tražimo NZD za B i q, tj. za 28 i 20 videli bi smo da je NZD isti.
Ponavljanjem postupka deljenja prethodnog delioca sa ostatkom deljenja sve dok u jednoj iteraciji ostatak deljenja ne bude nula, doći ćemo do broja koji predstavlja NZD. Poslednji rezultat deljenja je zapravo broj koji tražimo. U našem primeru, to je broj 4. Vidi sliku pod c).
Prethodni postupak je poznat kao Euklidov algoritam.
Određivanje NZD-a algoritam:
Program učitava dva cela broja a i b i određuje NZD za ta dva broja. Sa a je označen veći od ta dva, a sa b manji.
Slika 2: Algoritam za određivanje
NZD-a iterativno
Kod koji rešava ovaj problem na iterativan način bi bio:
Slika 4: Određivanje NZD-a pomoću Euklidovog algoritma-iterativno
|
Regionalni Centar za talente "Mihajlo Pupin"Osnovna delatnost Regionalnog centra za talente jeste razvoj naučno-tehničkog i istraživačkog stvaralaštva mladih u oblasti prirodnih, tehničkih, društvenih i drugih nauka. Regionalni centar imao je cilj da formira opštinske jedinice za talente na teritoriji na kojoj deluje. Posetite sajt Centra klikom na sliku ispod 
|
Prvo se učitavaju dva cela broja x i y, proverava se koji je veći i koji je manji i smeštaju se u promenljive
a-veći između x i y
b-manji između x i y
Iterativnim postupkom se dalje, ponavlja postupak traženja ostatka deljenja delioca i ostatka u deljenja prethodne iteracije. Postupak se ponavlja dok je ostatak deljenja različit od nule. Poslednji delilac u while petlji je zapravo traženi NZD.
Više o petljama u C jeziku pročitajte na web strani: Petlje u programskom jeziku C/C++
a-veći između x i y
b-manji između x i y
Iterativnim postupkom se dalje, ponavlja postupak traženja ostatka deljenja delioca i ostatka u deljenja prethodne iteracije. Postupak se ponavlja dok je ostatak deljenja različit od nule. Poslednji delilac u while petlji je zapravo traženi NZD.
Više o petljama u C jeziku pročitajte na web strani: Petlje u programskom jeziku C/C++
Određivanje NZD-a rekurzijom - algoritam:
Umesto iterativno kroz while petlju ovaj problem se može rešiti i rekurzivno:
Slika 5: Određivanje NZD pomoću Euklidovog algoritma rekurzivnom metodom
Funkcija NZDRek prima dva parametra a i b, i to tako da je prvi veći od drugog. Ako je ostatak deljenja r jednak nuli vraća se drugi broj, to jest delilac. Ako nije, postupak se ponavlja tako što funkcija poziva samu sebe i menja parametre, tako da je prvi, deljenik u stvari prethodni delilac tj. drugi parametar u prethodnom pozivu. Na drugom mestu je ostatak deljenja iz prethodnog rekurzivnog poziva.
Više o funkcijama pročitajte na web strani: Funkcije u C/C++
Više o funkcijama pročitajte na web strani: Funkcije u C/C++
Određivanje najmanjeg zajedničkog sadržalaca NZS
Najmanji zajednički sadržalac se može odrediti tako što se prvo odredi NZD i onda iz izraza
NZS(a,b)*NZD(a,b) = a*b
određuje NZS
NZS = a/(NZD(a,b) *b;
U prethodno opisanom primeru za brojeve 48 i 28:
NZS(a,b)*NZD(a,b) = a*b
određuje NZS
NZS = a/(NZD(a,b) *b;
U prethodno opisanom primeru za brojeve 48 i 28:
Slika 6: Određivanje najmanjeg zajedničkog sadržalaca
Na slici pod a) se vidi kako se određuje NZD, a na slici pod b) NZS za brojeve 48 i 28. Na slici pod c) je pokazano da je proizvod NZD i NZS jednak proizvodu brojeva 28 i 48, tj. u nekom opštem slučaju a i b.
Sledeći kod će prema tome izračunati NZS, na osnovu NZD:
Sledeći kod će prema tome izračunati NZS, na osnovu NZD:
Slika 7: Određivanje NZS-a na osnovu metode za računanje NZD-a
|
Sledeće
Maksimalna suma podniza >| |