Programozási alapismeretek 10. előadás

Programozási alapismeretek 10. előadás

Tartalom  Kiválogatás

ELTE

2013.11.19.

+ összegzés  Kiválogatás + maximumkiválasztás  Maximumkiválasztás + kiválogatás  Eldöntés + megszámolás  Eldöntés + eldöntés  Sorozatszámítás mátrixra  Eldöntés mátrixra  Tesztek előállítása

Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 10.

2/49

Kiválogatás + összegzés Feladat: Adott tulajdonságú elemek összege – feltételes összegzés. ELTE

Specifikáció:  Bemenet:

NEgész, XTömb[1..N:Egész]  Kimenet: SEgész  Előfeltétel: N0 N

 Utófeltétel:

S=

 X[i]

i 1 T(X[i]) 2013.11.19.


3/49

Kiválogatás + összegzés Specifikációa: N  Utófeltétela: Db, Y   Kiválogat és

i 1

i

T  X i  

Db

S=  X[Y[i]]

ELTE

i 1

Specifikációb:  Utófeltételb:

és

Db, Y   Kiválogat N

i 1

Xi

T  X i  

Db

S=  Y[i] i 1

2013.11.19.


4/49

Kiválogatás + összegzés 1. megoldási ötleta:

ELTE

2013.11.19.

Válogassuk ki az adott tulajdonságúakat, majd utána adjuk össze őket! Változó i:Egész Db:=0 i=1..N T(X[i]) I N Db:=Db+1  Y[Db]:=i S:=0 i=1..Db S:=S+X[Y[i]] Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 10.

5/49

Kiválogatás + összegzés 1. megoldási ötletb:

ELTE

2013.11.19.

Válogassuk ki az adott tulajdonságúakat, majd utána adjuk össze őket! Változó i:Egész Db:=0 i=1..N T(X[i]) I N Db:=Db+1  Y[Db]:=X[i] S:=0 i=1..Db S:=S+Y[i] Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 10.

6/49

Kiválogatás + összegzés 2. megoldási ötlet: Kiválogatás helyett azonnal adjuk össze a megfelelő elemeket!  nincs elem-/indexfeljegyzés (Y-ban) + nincs számlálás (Db-ben) ELTE

Változ i:Eg

S:=0 i=1..N T(X[i]) I S:=S+X[i]

2013.11.19.


N



7/49

Kiválogatás + maximumkiválasztás Feladat: Adott tulajdonságú elemek maximuma – feltételes maximumkeresés. ELTE

2013.11.19.


N:Egész, X:Tömb[1..N:Valami]  Kimenet: MaxI:Egész, Van:Logikai  Előfeltétel: N0  Utófeltétel: Van=i (1≤i≤N): T(X[i]) és Van( 1≤MaxI≤N és T(X[MaxI]) és i(1≤i≤N): T(X[i])X[MaxI]≥X[i] ) Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 10.

8/49

Kiválogatás + maximumkiválasztás Specifikáció2: N  Utófeltétel2: Van, MaxI   MaxInd i 1

Xi

T  X i  

ELTE

2013.11.19.


9/49

Kiválogatás + maximumkiválasztás A megoldás felé: Specifikáció’: N Db, Y   Kiválogat  Utófeltétel’: i 1

és ELTE

i

T  X i  

Van=Db>0 és Van( 1≤MaxI≤N és T(X[MaxI]) és MaxI  MaxInd XYi Db

i1

Kiolvasható az algoritmikus ötlet: Válogassuk ki az adott tulajdonságúakat, majd keressünk maximumot, ha van értelme! 2013.11.19.


10/49

Kiválogatás + maximumkiválasztás 1. megoldás algoritmusa: Válogassuk ki az adott tulajdonságúakat, majd …! ELTE

Db:=0 i=1..N T(X[i]) I Db:=Db+1 Y[Db]:=i Van:=Db>0 …

2013.11.19.

Változó i:Egész


N



11/49

Kiválogatás + maximumkiválasztás 1. megoldása algoritmusa: … , majd keressünk maximumot, ha van értelme! ELTE

I

… Van

MaxI:=Y[1] i=2..Db X[Y[i]]>X[MaxI] I MaxI:=Y[i]  2013.11.19.


N

 N

12/49

Kiválogatás + maximumkiválasztás 2. megoldási ötlet (és algoritmusa):

Induljunk ki a specifikációban észrevett tételekből: a kiválogatás helyett keressük meg az első T-tulajdonságút, …

ELTE

i:=1

Változó i:Egész

iN és T(X[i]) i:=i+1 Van:=iN …

2013.11.19.


13/49

Kiválogatás + maximumkiválasztás 2. megoldási ötlet (és algoritmusa): … majd válasszuk ki az ilyenek maximumát! … Van

ELTE

I

N

MaxI:=i i=i+1..N I T(X[i]) és X[i]>X[MaxI] N MaxI:=i 

2013.11.19.


14/49

Kiválogatás + maximumkiválasztás 3. megoldási ötlet (és algoritmusa): Kiválogatás, ill. keresés helyett azonnal válasszuk ki a maximumot! ELTE

Kell egy fiktív 0. elem a maximumkiválasztáshoz, ami kisebb minden normál elemnél.

Változó i:Egész

X[0]:=- MaxI:=0 i=1..N T(X[i]) és X[i]>X[MaxI] I MaxI:=i  Van:=MaxI>0 2013.11.19.


N

15/49

Maximumkiválasztás + kiválogatás Feladat: Összes maximális elem kiválogatása.

Specifikáció: ELTE

NEgész,X Tömb[1..N:Valami]  Kimenet: DbEgész, MaxITömb[1..Db:Egész]  Előfeltétel: N>0  Utófeltétel:N Db = 1 és Max=X[MaxI[1]] és  Bemenet:

i 1 X[i]  Max

i(1≤i≤Db): j(1≤j≤N): X[MaxI[i]]≥X[j] és MaxI(1,2,…,N) 2013.11.19.


16/49

Maximumkiválasztás + kiválogatás Feladat: Összes maximális elem kiválogatása.


 Bemenet:

NEgész, XTömb[1..N:Valami]  Kimenet: DbEgész, MaxITömb[1..Db:Egész]  Előfeltétel: N>0 N  Utófeltétel: Max=MaxÉrt X[i] és i=1

Db, MaxI   Kiválogat N

i 1

i

X i  Max

2013.11.19.


17/49

Maximumkiválasztás + kiválogatás 1. megoldási ötlet: Határozzuk meg a maximumot, majd válogassuk ki a vele egyenlőeket! ELTE

Max:=X[1] i=2..N X[i]>Max I Max:=X[i] …

2013.11.19.

Változó Max:Valami i:Egész




N

18/49

Maximumkiválasztás + kiválogatás 1. megoldási ötlet: Határozzuk meg a maximumot, majd válogassuk ki a vele egyenlőeket! …

ELTE

Db:=0 I

i=1..N X[i]=Max

Db:=Db+1 MaxI[Db]:=i 2013.11.19.


N



19/49

Maximumkiválasztás + kiválogatás 2. megoldási ötlet: A pillanatnyi maximálissal egyenlőeket azonnal válogassuk ki! Változó ELTE

Db:=1 MaxI[1]:=1 Max:=X[1]

Max:Valami i:Egész

i=2..N X[i]>Max X[i]=Max I I Db:=1 Db:=Db+1 MaxI[1]:=i MaxI[Db]:=i Max:=X[i]  2013.11.19.


20/49

Eldöntés + megszámolás Feladat: Van-e egy sorozatban legalább K darab adott tulajdonságú elem? ELTE


N,KEgész, XTömb[1..N:Valami]  Kimenet: VanLogikai  Előfeltétel: N0 [és K>0] N  Utófeltétel: db=  1 és Van=db≥K i 1 T(X[i])

2013.11.19.


21/49

Eldöntés + megszámolás 1. megoldási ötlet:

ELTE

2013.11.19.

Számoljuk meg, hogy hány adott tulajdonságú van, majd nézzük meg, hogy ez legalább K-e! (Azaz valójában nincs: eldöntés tétel!) Változó i:Egész db:=0 i=1..N T(X[i]) I N db:=db+1  Van:=db≥K


22/49

Eldöntés + megszámolás 2. megoldási ötlet: Ha már találtunk K darab adott tulajdonságút, akkor ne nézzük tovább! ELTE

db:=0 i:=1 i≤N és db
2013.11.19.

Változó i:Egész




N

23/49

Keresés + megszámolás Feladat: Melyik egy sorozatban a K. adott tulajdonságú elem (ha van egyáltalán)? ELTE


N,KEgész, XTömb[1..N:Valami]  Kimenet: VanLogikai, KIEgész  Előfeltétel: N0 és K>0 i  Utófeltétel: Van=i(1iN):  1 =K és Van→1KIN és

2013.11.19.


KI

j 1 T(X[j])

 1=K

j 1 T(X[j])

és T(X[KI]) 24/49

Keresés + megszámolás 1. megoldási ötlet:

ELTE

Az előbbi ötlet: „számoljuk meg, hogy hány adott tulajdonságú van, majd nézzük meg, hogy ez legalább K-e…” kevés, még hátra van a K. újbóli megkeresése… A működőnek látszó ötlet: a megszámolás helyett kiválogatás kell… és a keresésre nincs szükség… … de ez is túl hosszadalmas!

2013.11.19.


25/49

Keresés + megszámolás 2. megoldási ötlet: Ha már találtunk K darab adott tulajdonságút, akkor ne nézzük tovább: keresés a K.-ig. ELTE

db:=0 i:=1 i≤N és db
2013.11.19.

Változó i:Egész




N

26/49

Keresés + megszámolás 2. megoldási ötlet: Ha megtaláltunk a K.-kat, akkor jegyezzük föl az indexét! ELTE

… Van

I

N

KI:=i-1

2013.11.19.


27/49

Eldöntés + eldöntés Feladat: Van-e két sorozatnak közös eleme?


 Bemenet:

N,MEgész, XTömb[1..N:Valami], YTömb[1..M:Valami]  Kimenet: VanLogikai  Előfeltétel: N0 és M0  Utófeltétel: Van=i(1≤i≤N), j(1≤j≤M): X[i]=Y[j] N M  Utófeltétel’: Van    Xi  Y j i 1

2013.11.19.

j1


28/49

Eldöntés + eldöntés 1. megoldási ötlet: Határozzuk meg a két sorozat közös elemeit (metszet), s ha ennek elemszáma legalább 1, akkor van közös elem! ELTE

Specifikáció:  Az  

utófeltétel „igazítása”: a metszet részeredménye volt: DbEgész a módosított utófeltétel: metszet utófeltétele és Van=Db>0.

Megjegyzés: A metszet = kiválogatás + eldöntés 2013.11.19.


29/49

Eldöntés + eldöntés 2. megoldási ötlet: Ha már találtunk 1 darab közös elemet, akkor ne nézzük tovább! Változó ELTE

2013.11.19.

i:=0 Van:=Hamis i
i,j:Egész

31/49

Összegzés mátrixra Feladat: Egy mátrix elemeinek összege.


 Bemenet:

N,MEgész, XTömb[1..N,1..M:Egész]  Kimenet: SEgész  Előfeltétel: N,M0 N

 Utófeltétel:

M

 X[i, j]

S=

i 1 j1

2013.11.19.


32/49

Összegzés mátrixra Algoritmus: A megoldás lényegében csak abban különbözik az alapváltozattól, hogy a mátrix miatt két –egymásba ágyazott– ciklusra van szükség. ELTE

Változó i,j:Egész

S:=0 i=1..N j=1..M S:=S+X[i,j]

2013.11.19.


33/49

Eldöntés mátrixra Feladat: Van-e egy mátrixban adott tulajdonságú elem? ELTE

2013.11.19.


N,MEgész, XTömb[1..N,1..M:Valami]  Kimenet: VanLogikai  Előfeltétel: N,M0  Utófeltétel: Van=i(1≤i≤N), j(1≤j≤M): T(X[i,j]) Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 10.

34/49

Eldöntés mátrixra Algoritmus: Az alapváltozathoz képest itt meg kell fogalmazni a mátrix elemein való –nem feltétlenül– végighaladást, soronként, balról jobbra! Változó ELTE

iN és nem T(X[i,j]) j<M I j:=1 j:=j+1 i:=i+1 Van:= iN 2013.11.19.

i,j:Egész

i:=1 j:=1


N

35/49



i,j:Egész

i:=1 j:=1


N

36/49



i,j:Egész

i:=1 j:=1


N

37/49



i,j:Egész

i:=1 j:=1


N

38/49

Tesztek előállítása

ELTE

Feladat (teszteléshez): Egy repülőgéppel Európából Amerikába repültünk. Az út során X kilométerenként mértük a felszín tengerszint feletti magasságát (0). 0 magasságot ott mértünk, ahol tenger van, >0-t pedig ott, ahol szárazföld. Adjuk meg a szigeteket! 120 100 80 60 40 20

2013.11.19.


49

47

45

43

41

39

37

35

33

31

29

27

25

23

21

19

17

15

13

9

11

7

5

3

1

0

39/49

Tesztek előállítása Specifikáció  Bemenet:

ELTE

NEgész, MagTömb[1..N:Egész]  Kimenet: DbEgész, K,VTömb[1..Db:Egész]  Kis teszteket készíthetünk a tesztelési elveknek megfelelően, például:

N=3, Mag=(1,0,1)  nincs sziget N=5, Mag=(1,0,1,0,1)  egy sziget N=7, Mag=(1,0,1,0,1,0,1)  több sziget N=7, Mag=(1,0,1,1,1,0,1)  hosszabb sziget

 Hogyan 2013.11.19.

készítünk nagy teszteket?


40/49

Szabályos tesztek  Készíthetünk

szabályos teszteket egyszerű ciklusokkal. Például így:

ELTE

2013.11.19.

N:=1000 i=1..10 Mag[i]:=11–i i=11..900 Mag[i]:=0 i=901..N Mag[i]:=i–900

Változó i:Egész

 Európa  tenger  Amerika


41/49

Véletlen tesztek (alapok – véletlenszámok) A

ELTE

2013.11.19.

véletlenszámokat a számítógép egy algoritmussal állítja elő egy kezdőszámból kiindulva. x0  f(x0)=x1  f(x1)=x2  …  A „véletlenszerűséghez” megfelelő függvény és jó kezdőszám szükséges.  Kezdőszám: (pl.) a belső órából vett érték.  Függvény (az ún. lineáris kongruencia módszernél): f(x) = (A*x+B) Mod M, ahol A, B és M a függvény belső konstansai.


42/49

Véletlen tesztek (alapok – C++)

C++: rand() véletlen egész számot ad 0 és egy maximális érték (RAND_MAX) között. srand(szám) kezdőértéket állít be. ELTE

 Véletlen(a..b){a,…,b}

v=rand() % (b-a+1)+a  Véletlen(N){1,…,N} v=rand() % N+1  véletlenszám[0,1)Valós

v=rand()/(RAND_MAX+1.0) A

generátor használata kockadobásra: #include

… srand(time(NULL)); i=rand() % 6 +1;

2013.11.19.


43/49

Véletlen tesztek  Véletlen

tesztekhez használjunk véletlenszámokat! Például így: Változó

ELTE

2013.11.19.

i:Egész N:=1000 M:=Véletlen(10) i=1..M Mag[i]:=Véletlen(5..10)  Európa i=M+1..900  tenger és véletlenszám<0.5 I N szigetek Mag[i]:=0 Mag[i]:=1 i=901..N  Amerika Mag[i]:=Véletlen(3..8) Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 10.

44/49

Véletlen tesztek (Példa – C++) Specifikációs komment: Az előbbi algoritmus általánosítása!

Kód:

ELTE

Fájlkezeléshez

2013.11.19.


45/49

Véletlen tesztek (Példa – C++) Függvényprototípusok

ELTE

Kód:

Főprogram

2013.11.19.


46/49

Véletlen tesztek (Példa – C++) A lényegi eljárás

Kód:

ELTE

2013.11.19.


47/49

Véletlen tesztek (Példa – C++) Alprogramok implementációja

Kód:

ELTE

2013.11.19.


Kód jegyzetként

48/49

Véletlen tesztek (Példa – C++)

Az eredményfájl

ELTE

… és elemzése:

2013.11.19.


Adatfájl jegyzetként

49/49

Programozási alapismeretek 10. előadás vége

Programozási alapismeretek 10. előadás

Recommend Documents