Programozási tételek

Sorozathoz egy érték vagy sorozat hozzárendelése

Összegzés tétele (pl.)

Adott egy N elemű számsorozat: A(N). Számoljuk ki az elemek összegét!

S:=0
Ciklus I=1-től N-ig
	S:=S+A(I)
Ciklus vége

Eldöntés tétele (pl.)

Adott egy N elemű sorozat és egy a sorozaton értelmezett T tulajdonság.

Van-e a sorozatnak legalább egy T tulajdonságú eleme?

I:=1
Ciklus amíg I<=N és A(I) nem T tulajdonságú
	I:=I+1
Ciklus vége
VAN:=(I<=N)
(A "VAN" egy logikai változó, amely akkor és csak akkor igaz, ha I<=N)

Kiválasztás tétele (pl.)

Adott egy N elemű sorozat, egy - a sorozat elemein értelmezett - T tulajdonság. Azt is tudjuk, hogy

a sorozatban van legalább egy T tulajdonságú elem. A feladat ezen elem sorszámának meghatározása.

I:=1
Ciklus amíg A(I) nem T tulajdonságú
	I:=I+1
Ciklus vége
SORSZ:=I

Megszámlálás tétele (pl.)

Adott egy N elemű sorozat és egy - a sorozat elemein értelmezett - T tulajdonság.

Feladat a T tulajdonsággal rendelkező elemek megszámolása.

S:=0
Ciklus I=1-től N-ig
	Ha A(I) T tulajdonságú akkor S:=S+1
Ciklus vége

Maximum (minimum) kiválasztás tétele (pl.)

Adott egy N elemű sorozat és elemein a kisebb-nagyobb reláció. Mi a sorozat legnagyobb (legkisebb) elemének indexe?

INDEX:=1
Ciklus I=2-től N-ig
	Ha A(INDEX) < A(I) akkor INDEX:=I
Ciklus vége

Lineáris keresés tétele (pl.)

Általános feladat: N elemű sorozat és a sorozat elemein értelmezett T tulajdonság.

Van-e T tulajdonságú elem és ha van, akkor mi a sorszáma? (Eldöntés és kiválasztás együtt.)

I:=1
Ciklus amíg I<=N és A(I) nem T tulajdonságú
	I:=I+1
Ciklus vége
VAN:=(I<=N)
Ha VAN akkor INDEX:=I

Logaritmikus keresés tétele

Általános feladat: N elemű rendezett sorozat és egy keresett elem (X). Szerepel-e a keresett elem a sorozatban és ha igen, akkor mi a sorszáma?

Kihasználjuk, hogy a sorozat rendezett, így el tudjuk dönteni, hogy a keresett elem az éppen vizsgált elemhez képest hol helyezkedik el.

AH, FH: intervallum alsó és felső végpontjai.

AH:=1  F:=N
Ciklus
	K:=INT((AH+FH)/2)
	Ha A(K) < X akkor AH:=K+1
	Ha A(K) > X akkor FH:=K-1
	amíg AH <= FH és A(K) ≠ X
Ciklus vége
VAN:=(AH<=FH)
Ha VAN akkor INDEX:=K

Megjegyzések: azért hívják logaritmikus keresésnek, mert kb. log N a ciklus lépésszáma.

Kiválogatás tétele (pl.)

Egy N elemű sorozat összes T tulajdonságú elemét kell meghatározni.

A kiválogatott elemek sorszámait gyűjtsük össze egy B() vektorban!

J:=0
Ciklus I=1-től N-ig
	Ha A(I) T tulajdonságú, akkor J:=J+1  B(J):=I
Ciklus vége

A pici kék "(pl.)"-re téve az egérkurzort, megjelenik egy másik feladat, amit célszerű gyakorlásként megoldani!