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.
Euklidov algoritam, jedan je od najstarijih poznatih matematičkih algoritama. Prvi put je opisan u Euklidovim „Elementima“ pre više od 2000 godina, a njegova osnovna struktura ostala je nepromenjena do danas. Ovaj algoritam se koristi za efikasno pronalaženje najvećeg zajedničkog delioca (GCD) dva ili više celih brojeva. Njegova jednostavnost, preciznost i široka primena čine ga jednim od najvažnijih alata u matematičkim i algoritamskim disciplinama.
Euklidov algoritam se prvenstveno koristi za pronalaženje najvećeg zajedničkog delioca (GCD) dva broja. Ovo je korisna procedura u mnogim matematičkim i inženjerskim problemima, jer omogućava uprošćavanje razlomaka, analizu cikličnih procesa i rešavanje problema deljivosti. Osim za pronalaženje GCD, algoritam se koristi i za izračunavanje najmanje zajedničke komponente (LCM) dva broja, što dodatno povećava njegovu praktičnu vrednost.
Zašto je to važno?
Euklidov algoritam se široko koristi u različitim oblastima:
Euklidov algoritam se široko koristi u različitim oblastima:
- Matematika: Algoritam se koristi u teoriji brojeva za rešavanje problema deljivosti, kao i za generisanje proširenih verzija algoritma koje omogućavaju rešavanje Diofantovih jednačina.
- Programiranje: Kao jedan od osnovnih algoritama, često se koristi u softverskom inženjerstvu i algoritamskim izazovima. Njegova efikasnost i jednostavnost čine ga savršenim primerom algoritamske optimizacije.
- Kriptografija: U savremenim aplikacijama, Euklidski algoritam je ključni element u algoritmima za generisanje i analizu kriptografskih ključeva, kao što su RSA i Diffie-Hellman protokoli.
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.
Primeri i kontekst
Pored primera sa A=48 i B=28, uključivanje više različitih primera sa većim brojevima može da ilustruje robusnost Euklidovog algoritma.
NZS(A,B)=∣A*B∣/NZD(A,B)
Pokazivanje kako Euklidov algoritam indirektno pomaže u pronalaženju LCM-a bi podvukao njegovu svestranost.
- Primer sa većim brojevima. Hajde da izračunamo NZD za A=987654 i B=123456. Ovo naglašava efikasnost algoritma, čak i sa značajnim numeričkim ulazima, naglašavajući njegovu primenljivost u računarskim kontekstima.
- Primena u stvarnom svetu: Kriptografija. U kriptografskim algoritmima kao što je RSA, Euklidov algoritam igra ključnu ulogu u izračunavanju modularnih inverza. Demonstracija ovog slučaja upotrebe može pokazati kako algoritam podržava moderne bezbednosne sisteme, čineći teorijski aspekt povezanim sa scenarijima iz stvarnog sveta.
- Određivanje NZS -a korišćenjem NZD-a.Primer izračunavanja najmanjeg zajedničkog sadržaoca(NZS) dva broja koristeći njihov NZD može proširiti kontekst:
NZS(A,B)=∣A*B∣/NZD(A,B)
Pokazivanje kako Euklidov algoritam indirektno pomaže u pronalaženju LCM-a bi podvukao njegovu svestranost.
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
Prošireni Euklidov algoritam
Uvod u prošireni euklidski algoritam je moćno proširenje standardnog Euklidovog algoritma. Dok Euklidov algoritam određuje najveći zajednički delilac (NZD) dva cela broja, proširena verzija takođe pronalazi cele brojeve x i y koji zadovoljavaju jednačinu:
ax+by=GCD(a,b)
Ova dodatna funkcionalnost ga čini neprocenjivim u oblastima kao što su rešavanje linearnih Diofantovih jednačina i modularna aritmetika.
Matematika iza algoritma:
Rešavanje Diofantovih jednačina su jednačine gde se rešenja traže u celim brojevima. Prošireni Euklidov algoritam pruža konstruktivan način da se pronađu takva rešenja za jednačinu
ax+by=d,
gde je d NZD za a i b. Radeći unazad od euklidskih koraka, on određuje koeficijente x i y. Ovaj proces osigurava da je jednačina zadovoljena ovim celim brojevima.
Praktične primene u kriptografiji i teoriji brojeva.
Prošireni Euklidov algoritam se široko koristi u:
Iterativna implementacija:
Iterativni pristup izračunava NZD uz istovremeno održavanje koeficijenata x i y. Algoritam skladišti srednje vrednosti i ažurira ih kako se proces deljenja odvija. Ovo je efikasno za okruženja u kojima je dubina steka ograničenje.
Rekurzivna implementacija:
Rekurzivni metod prati intuitivniji pristup, direktno rešavajući za x i y dok odmotava rekurzivne pozive. Ovo je generalno jednostavnije za razumevanje i implementaciju, ali može biti ograničeno dubinom rekurzije u nekim programskim okruženjima.
Primer: Modularni inverz i rešavanje kongruencija
Pronalaženje modularnog inverza: Da biste izračunali modularni inverz od a % m(a modul m), koristite prošireni euklidov algoritam da biste pronašli k tako da je ax+my=1. Vrednost k po modulu m je inverzna. Primer koda:
ax+by=GCD(a,b)
Ova dodatna funkcionalnost ga čini neprocenjivim u oblastima kao što su rešavanje linearnih Diofantovih jednačina i modularna aritmetika.
Matematika iza algoritma:
Rešavanje Diofantovih jednačina su jednačine gde se rešenja traže u celim brojevima. Prošireni Euklidov algoritam pruža konstruktivan način da se pronađu takva rešenja za jednačinu
ax+by=d,
gde je d NZD za a i b. Radeći unazad od euklidskih koraka, on određuje koeficijente x i y. Ovaj proces osigurava da je jednačina zadovoljena ovim celim brojevima.
Praktične primene u kriptografiji i teoriji brojeva.
Prošireni Euklidov algoritam se široko koristi u:
- Kriptografija: Računanje modularnih inverza u algoritmima kao što je RSA za efikasno šifrovanje i dešifrovanje.
- Teorija brojeva: Rešavanje linearnih kongruencija i pronalaženje celih brojeva koji zadovoljavaju određena modularna svojstva.
- Računarstvo: Primene u heširanju, kompresiji podataka i teoriji kodiranja.
Iterativne i rekurzivne implementacije sa objašnjenjima
Iterativna implementacija:
Iterativni pristup izračunava NZD uz istovremeno održavanje koeficijenata x i y. Algoritam skladišti srednje vrednosti i ažurira ih kako se proces deljenja odvija. Ovo je efikasno za okruženja u kojima je dubina steka ograničenje.
Rekurzivna implementacija:
Rekurzivni metod prati intuitivniji pristup, direktno rešavajući za x i y dok odmotava rekurzivne pozive. Ovo je generalno jednostavnije za razumevanje i implementaciju, ali može biti ograničeno dubinom rekurzije u nekim programskim okruženjima.
Primer: Modularni inverz i rešavanje kongruencija
Pronalaženje modularnog inverza: Da biste izračunali modularni inverz od a % m(a modul m), koristite prošireni euklidov algoritam da biste pronašli k tako da je ax+my=1. Vrednost k po modulu m je inverzna. Primer koda:
#include <iostream>
#include <tuple>
// Funkcija za proširen Euklidov algoritam
std::tuple<int, int, int> extended_gcd(int a, int b) {
if (b == 0) {
return {a, 1, 0};
}
int gcd, x1, y1;
std::tie(gcd, x1, y1) = extended_gcd(b, a % b);
int x = y1;
int y = x1 - (a / b) * y1;
return {gcd, x, y};
}
// Testiranje funkcije
int main() {
int a = 48, b = 18;
int gcd, x, y;
std::tie(gcd, x, y) = extended_gcd(a, b);
std::cout << "NZD: " << gcd << ", x: " << x << ", y: " << y << std::endl;
return 0;
}
#include <tuple>
// Funkcija za proširen Euklidov algoritam
std::tuple<int, int, int> extended_gcd(int a, int b) {
if (b == 0) {
return {a, 1, 0};
}
int gcd, x1, y1;
std::tie(gcd, x1, y1) = extended_gcd(b, a % b);
int x = y1;
int y = x1 - (a / b) * y1;
return {gcd, x, y};
}
// Testiranje funkcije
int main() {
int a = 48, b = 18;
int gcd, x, y;
std::tie(gcd, x, y) = extended_gcd(a, b);
std::cout << "NZD: " << gcd << ", x: " << x << ", y: " << y << std::endl;
return 0;
}
Objašnjenje:
- Ulazni parametri: Funkcija prima dva cela broja a i b.
- Rekurzija: Kada je b jednako 0, funkcija vraća NZD kao a, i koeficijente x = 1, y = 0.
- Rekurzivni poziv: Poziva se funkcija sa b i a % b.
- Izračunavanje koeficijenata: Vrednosti x i y se računaju na osnovu rezultata iz rekurzivnog poziva.
- Tuple: Korišćenje std::tuple za vraćanje tri vrednosti (GCD, x, y).
- NZD: 6
- x: -1
- y: 3
|
Sledeće
Maksimalna suma podniza >| |