Pascal II. 01. Eljárások, függv... 01. Gyakorló feladatok 02. Felsorolt típus, ... 02. Gyakorló feladatok 03. Állományok kezelése 03. Gyakorló feladatok 04. Unitok, CRT unit 04. Gyakorló feladatok 05. DOS unit, rendezé... 05. Gyakorló feladatok 06. Rekurzió, quicksort 06. Gyakorló feladatok 07. Backtracking 07. Gyakorló feladatok 08. GRAPH unit 08. Gyakorló feladatok 09. Kép mozgatása 09. Gyakorló feladatok 10. Winmouse unit 10. Gyakorló feladatok 11. Dinamikus adatsze... 11. Gyakorló feladatok 12. Dinamikus adatsze... 12. Gyakorló feladatok 13. Dinamikus adatsze... 13. Gyakorló feladatok
|
Programozás 2 (Pascal)
6
Rekurzió,
quicksort
6.1 Rekurzió
Rekurzió
az, amikor egy eljárás vagy függvény -
közvetve vagy közvetlenül - önmagát
hívja. A végtelen rekurzió
elkerülésére mindig szükségünk van egy
feltételre, amely valamilyen lépésszám
után leállítja a rekurziót. A
következõ program eljárása ciklus helyett
rekurziót alkalmaz adott számú csillag
kirajzolására:
program Pelda23;
uses crt;
procedure csillagok(mennyi:integer);
begin
if mennyi>0 then begin
write('*');
csillagok(mennyi-1);
end;
end;
begin
clrscr;
csillagok(10);
end.
Az
elv: adott számú csillagot úgy rajzolunk ki, hogy kirajzolunk egy csillagot,
majd kirajzoljuk a maradékot. A mennyi paraméter azt jelzi, hogy mennyi csillagot
kell még kirajzolni.
A
matematikában találkozhatunk rekurzív
definíciókkal, pl. 0! (nulla faktoriális)
értéke 1, n! pedig n*(n-1)!. Tehát egy szám
faktoriálisát úgy számíthatjuk ki,
hogy kiszámítjuk a nála eggyel kisebb szám
faktoriálisát és megszorozzuk a számmal. A
rekurzió véget ér, ha eljutunk a 0-hoz. Ez pascal
programban így néz ki:
program Pelda24;
uses crt;
var k:integer;
function
fakt(n:integer):longint;
begin
if n>0 then fakt:=n*fakt(n-1)
else fakt:=1;
end;
begin
clrscr;
write('Kerek egy egesz szamot (0..12): ');
readln(k);
writeln(k,'! = ',fakt(k));
end.
6.2 Gyorsrendezés (QuickSort)
A módszer lényege: Tekintsük a tömb
középsõ elemét (felezzük a
tömböt). Ez az elem az ú.n. pivot (vezérelem).
Balról keressük meg azt az elsõ elemet, mely
ennél nem kisebb, jobbról azt az elsõ elemet,
amely ennél nem nagyobb. Cseréljük ki a két
elemet, s folytassuk a cserélgetést egészen addig,
amíg a bal oldalon a középsõ elemnél
(mely természetesen cserélõdhet menet közben)
csupa nem nagyobb, jobb oldalon pedig csupa nem kisebb elem áll.
Rekurzív hívással most rendezzük a tömb
alsó és felsõ felét, majd ezeknek
alsó és felsõ felét, és így
tovább.
A
QuickSort-tal kiegészített rendezést bemutató
program:
program Pelda25;
uses crt, dos;
const elemekszama = 30000;
var a,b:array [1..elemekszama] of integer;
ido:longint;
i:integer;
procedure kiiras;
var i:integer;
begin
for i:=1 to elemekszama do write(a[i],' ');
writeln;
writeln;
end;
procedure stopperbe;
var t1,t2,t3,t4:word;
begin
gettime(t1,t2,t3,t4);
ido:=t4+100*(t3+60*(t2+60*t1));
end;
procedure stopperki;
var t1,t2,t3,t4:word;
begin
gettime(t1,t2,t3,t4);
ido:=t4+100*(t3+60*(t2+60*t1))-ido;
end;
{ egyszeru rendezes }
procedure simplesort;
var i,j,x:integer;
begin
for i:=1 to elemekszama-1 do
for j:=i+1 to elemekszama do
if a[i]>a[j] then begin
x:=a[i];
a[i]:=a[j];
a[j]:=x;
end;
end;
{ rendezes a legkisebb
elem kivalasztasaval }
procedure minsort;
var i,j,min,x:integer;
begin
for i:=1 to elemekszama-1 do
begin
min:=i;
for j:=i+1 to elemekszama do
if a[j]<a[min] then min:=j;
x:=a[i];
a[i]:=a[min];
a[min]:=x;
end;
end;
{ rendezes a szomszedos
elemek cserejevel }
procedure bubblesort;
var i,j,x:integer;
ok:boolean;
begin
i:=elemekszama-1;
ok:=false;
while (i>=1) and (not ok) do
begin
ok:=true;
for j:=1 to i do
if a[j]>a[j+1] then begin
x:=a[j];
a[j]:=a[j+1];
a[j+1]:=x;
ok:=false;
end;
dec(i);
end;
end;
{ rendezes beszurasos
modszerrel }
procedure insertsort;
var i,j,x,ment:integer;
begin
for i:=2 to elemekszama do
begin
if a[i]<a[i-1] then begin
ment:=a[i];
j:=i;
repeat
dec(j);
a[j+1]:=a[j];
until (j=1) or (a[j-1]<=ment);
a[j]:=ment;
end;
end;
end;
{ gyorsrendezes }
procedure quicksort(bal,jobb:integer);
var i,j,pivot,x:integer;
begin
i:=bal;
j:=jobb;
pivot:=a[(i+j) div 2];
while i<=j do
begin
while a[i]<pivot do inc(i);
while a[j]>pivot do dec(j);
if i<=j then begin
x:=a[i];
a[i]:=a[j];
a[j]:=x;
inc(i);
dec(j);
end;
end;
if bal<j then quicksort(bal,j);
if i<jobb then quicksort(i,jobb);
end;
{ foprogram }
begin
clrscr;
writeln(elemekszama,' drb. elem rendezese:');
writeln;
randomize;
for i:=1 to elemekszama do b[i]:=random(64000)-32000;
{ mindig a-t fogjuk
rendezni, b-ben meghagyjuk a kigeneralt szamokat}
a:=b;
{ rendezes }
stopperbe;
simplesort;
stopperki;
{ kiiras }
writeln('SimpleSort: ',ido,' szazadmasodperc');
a:=b;
{ rendezes }
stopperbe;
minsort;
stopperki;
{ kiiras }
writeln('MinSort: ',ido,' szazadmasodperc');
a:=b;
{ rendezes }
stopperbe;
bubblesort;
stopperki;
{ kiiras }
writeln('BubbleSort: ',ido,' szazadmasodperc');
a:=b;
{ rendezes }
stopperbe;
insertsort;
stopperki;
{ kiiras }
writeln('InsertSort: ',ido,' szazadmasodperc');
a:=b;
{ rendezes }
stopperbe;
quicksort(1,elemekszama);
stopperki;
{ kiiras }
writeln('QuickSort: ',ido,' szazadmasodperc');
end.
Rendezési algoritmusokat animációk
segítségével bemutató program letölthető itt:
rendalgo.exe
|