Misja Tereski
Chciałbym Wam przedstawić kilka rodzajów algorytmu znajdującego największy wspólny dzielnik liczb, powszechnie znanego jako Algorytm Euklidesa.
Kompletny opis działania algorytmu Euklidesa : klik 1) Wyznaczanie NWD(największego wspólnego dzielnika) dla dwóch liczb sposobem z dzieleniem. Download: Rapidshare, Hotfile, Megaupload, Przeklej i Inne program alg_euklidesa; // z dzieleniem uses crt; var m,n,r : QWord; BEGIN clrscr; writeln('Program oblicza NWD przez sposob dzielenia.'); readln; write('Podaj pierwsza liczbe: '); readln(m); write('Podaj druga liczbe: '); readln(n); writeln; writeln('Nacisnij enter...'); readln; writeln; { *********************************** } { Dla liczby m - mniejszej lub rownej n } IF m >= n THEN Begin while n <> 0 do begin r := n; n := m mod n; m := r; end; writeln('NWD tych dwoch liczb to: ',m); End { *********************************** } { Dla liczby m - wiekszej od n } else Begin while n <> 0 do begin r := n; n := m mod n; m := r; end; writeln('NWD tych dwoch liczb to: ',m); End; readln; end. Download bez limitów 2) Wyznaczanie NWD(największego wspólnego dzielnika) dla dwóch liczb sposobem z odejmowaniem. Download: Rapidshare, Hotfile, Megaupload, Przeklej i Inne program alg_euklidesa; // z odejmowaniem uses crt; { *************** } Var a,b:Word; Var NWD:Word; Var w:byte; { *************** } BEGIN REPEAT clrscr; write('Podaj liczbe a: '); readln(a); write('Podaj liczbe b: '); readln(b); clrscr; IF ( a<>b ) THEN REPEAT Begin IF ( a>b ) THEN a:=a-b; IF ( a<b ) THEN b:=b-a; End; UNTIL a=b; NWD:=a; writeln('NWD tych liczb wynosi: ',NWD); writeln; writeln; write('Ponownie? 1 - tak, 0 - nie : '); read(w); UNTIL w=0; END. Download bez limitów 2) Wyznaczanie NWD(największego wspólnego dzielnika) dla n liczb pobranych z pliku (Algorytm ten jest bardziej zaawansowany, opis do niego znajduje się niżej). Download: Rapidshare, Hotfile, Megaupload, Przeklej i Inne program nwd_n_liczb; uses crt; Type Ttab = array of word; var tab:Ttab; f:text; k:text; licznik:word; wiersz:word; const s = 'C:\liczby.txt'; // w tym pliku dodajemy liczby, z których chcemy wyznaczyć nwd || wpisujemy je po jednej liczbie w wierszu const x = 'C:\nwd_n.txt'; // do tego pliku zapisywany jest NWD tych n liczb pobranych z pliku liczby.txt {************************************************************************} Procedure Szukam_Dzielnika (var t:Ttab); var r,i,p : word; nwd : word; wers : word; begin ASSIGN(f,s); RESET(f); i:=0; nwd:=0; textcolor(yellow); writeln(' Liczby z pliku to: '); textcolor(lightgray); writeln; WHILE NOT EOF(f) DO begin readln(f,wers); t[i]:=wers; if (i mod 10 = 0) then writeln; write(' ',t[i]); i:=i+1; end; writeln; writeln('--------------------------------------------'); writeln; i:=0; WHILE ((t[i]>0) and (t[i+1]>0)) DO begin if t[i] > t[i+1] then t[i]:=t[i] mod t[i+1] else t[i+1]:=t[i+1] mod t[i]; nwd:=t[i]+t[i+1]; i:=i+1; end; textcolor(yellow); write(' NWD = ',nwd); ASSIGN(k,x); REWRITE(k); writeln(k,'NWD tych liczb wynosi: ',nwd); CLOSE(k); textcolor(lightgray); CLOSE(f); end; BEGIN ASSIGN(f,s); RESET(f); clrscr; writeln; textcolor(yellow); writeln(' ************************************'); write(' *'); textcolor(lightgray); write(' Trwa pobieranie liczb z pliku...'); textcolor(yellow); writeln(' *'); writeln(' ************************************'); textcolor(lightgray); writeln; writeln('--------------------------------------------'); writeln; delay(2000); licznik:=0; // *** Sprawdzenie ile liczb jest w pliku txt *** // WHILE NOT EOF(f) DO begin readln(f,wiersz); licznik:=licznik+1; end; // *** Kontynuowanie dzialania programu *** // setlength(tab,licznik); writeln(' Liczby wczytane!'); writeln; writeln('--------------------------------------------'); writeln; writeln(' Ilosc liczb w pliku liczby.txt wynosi: ',length(tab)); writeln; writeln('--------------------------------------------'); writeln; CLOSE(f); Szukam_Dzielnika(tab); readkey; END. Download bez limitów Powyższy program jest jedynym dostępnym programem tego typu w sieci, mojego autorstwa. Etapy jego działania: Download: Rapidshare, Hotfile, Megaupload, Przeklej i Inne 1) Zainicjowanie pliku liczby.txt. 2) Wczytanie do pamięci liczb pobranych z pliku liczby.txt. 3) W pierwszym etapie działania procedury Szukam_Dzielnika(t:Ttab) wypisywane na ekran są wszystkie liczby z pliku liczby.txt. Liczby te są także zapisywane do tablicy t[i]. W drugim etapie działania tej procedury wyszukiwany jest NWD tych liczb. 4) Następuje zainicjowanie & utworzenie pliku nwd_n.txt i zapisanie do niego wyniku, czyli wartości nwd. 5) W bloku głównym następuje sprawdzenie ile liczb jest w pliku liczby.txt, a następnie tworzona jest tablica dynamiczna o ilości elementów zaczytanej z wcześniejszego sprawdzenia(zmienna licznik). 6) Następuje wywołanie procedury Szukam_Dzielnika(). UWAGA!!! Aby program poprawnie zadziałał musi na dysku C:\ istnieć plik o nazwie liczby.txt z liczbami naturalnymi w środku. Download bez limitów Screeny z działania programu : 1) Screen z pliku liczby.txt http://img685.imageshack.us/img685/9277/screen11q.jpg 2) Screen z działania programu http://img130.imageshack.us/img130/6803/screen22n.jpg 3) Screen z utworzonego przez program pliku nwd_n.txt http://img413.imageshack.us/img413/6809/screen33f.jpg 4) Dwa pierwsze sposoby można przedstawić za pomocą funkcji. Będzie wtedy to tzw. wywołanie rekurencyjne. Download: Rapidshare, Hotfile, Megaupload, Przeklej i Inne function nwd(a,b:integer):integer; begin while a<>b do if a>b then a:=a-b else b:=b-a; nwd:=a; end; Download bez limitów Dziękuje i zapraszam na kolejne poradniki & programy mojego autorstwa. Jaspher © Maciej Sikorski, 2010 Wszelkie prawa zastrzeżone. |