Programozási alapismeretek 3. előadás

Programozási alapismeretek 3. előadás

Tartalom  Ciklusok

–

specifikáció+„algoritmika”+kódolás  Egy ELTE

2013.09.25.

bevezető példa a tömbhöz  A tömb  Elágazás helyett tömb  Konstans tömbök

Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 3. előadás

2/42

Ciklusok Feladat: Határozzuk meg egy természetes szám (N>1) 1-től különböző legkisebb osztóját! ELTE

Specifikáció:  Bemenet:

N Egész  Kimenet: O Egész  Előfeltétel: N>1  Utófeltétel: 1

3/42

Ciklusok

ELTE

A megoldás ötlete: Próbáljuk ki a 2-t; ha nem jó, akkor a 3-at, ha az sem, akkor a 4-et, …; legkésőbb az N jó lesz! Az ezt kifejező algoritmus: i:=2

Változó i:Egész

iłN i:=i+1 O:=i 2013.09.25.


4/42

Ciklusok Feladat:

ELTE

2013.09.25.

Határozzuk meg egy természetes szám (N>1) 1-től különböző legkisebb és önmagától különböző legnagyobb osztóját! Specifikáció:  Bemenet: N Egész  Kimenet: Lko,Lno Egész  Előfeltétel: N>1  Utófeltétel: 1
5/42

Ciklusok Megjegyzés:

ELTE

Az Lno az utófeltételben az Lko ismeretében másképp is megfogalmazható: Lko*Lno=N!

Az ehhez „illeszkedő” algoritmus: i:=2

Változó i:Egész

iłN i:=i+1 Lko:=i Lno:=N Div Lko 2013.09.25.


6/42

Ciklusok Feladat:

ELTE

2013.09.25.

Határozzuk meg egy természetes szám (N>1) 1-től és önmagától különböző legkisebb osztóját (ha van)! Specifikáció:  Bemenet: N Egész  Kimenet: O Egész, Van Logikai  Előfeltétel: N>1  Utófeltétel: Van= i (2 i
7/42

Ciklusok Algoritmus:

ELTE

i:=2 i
Változó i:Egész

i N

Megjegyzés:

2

i

N

N Div i

N Div 2

azaz

i*i i

N

azaz

N

Ha i osztója N-nek, akkor (N Div i) is osztója, azaz elég az osztókat a szám gyökéig keresni!

2013.09.25.


8/42

Ciklusok Feladat: Határozzuk meg egy természetes szám (N>1) osztói összegét! ELTE

Specifikáció:  Bemenet: N Egész  Kimenet: S Egész  Előfeltétel: N>1 N i  Utófeltétel: S i 1 iN

2013.09.25.


9/42

Ciklusok Algoritmus: Változó i:Egész

S:=0 ELTE

2013.09.25.

i=1..N i|N I S:=S+i


N

10/42

Ciklusok Feladat: Határozzuk meg egy természetes szám (N>1) páratlan osztói összegét! ELTE

Specifikáció:  Bemenet: N Egész  Kimenet: S Egész  Előfeltétel: N>1 N  Utófeltétel: S= i i 1 i N és páratlan(i)

páratlan(i)=??? 2013.09.25.


11/42

Ciklusok Algoritmus1:

Változó i:Egész

S:=0

ELTE

i=1..N i|N és páratlan(i) I S:=S+i

Algoritmus2:

S:=0 i=1..N; 2-esével i|N I S:=S+i 2013.09.25.


N

Változó i:Egész

N

12/42

Ciklusok Feladat: Határozzuk meg egy természetes szám (N>1) prímosztói összegét! ELTE


N Egész  Kimenet: S Egész  Előfeltétel: N>1 N  Utófeltétel: S= i prím(i)=??? 2013.09.25.

i 2 i N és prím(i)


13/42

Ciklusok Algoritmus:

a legkisebb osztó biztosan prím; ha N-t osztjuk vele ahányszor csak tudjuk, a következő osztója (a redukált N-nek) megint prím lesz.

ELTE

Változó i:Egész

S:=0 i:=2 i N i|N

I

N

S:=S+i i|N N:=N Div i

i:=i+1 2013.09.25.


14/42

Ciklusok Feladat:

ELTE

Határozzuk meg azon i,j (i,j>1) természetes számok számát, amelyekre i*j1)!


N Egész  Kimenet: S Egész  Előfeltétel: N>1 N Div 2 N Div 2 1  Utófeltétel: S= i 2 2013.09.25.

j 2 i j N


N Div 2 (N -1) Div i

1 i 2

j 2 i j N

15/42

Ciklusok Algoritmus1:

Változó i,j:Egész

S:=0 ELTE

i=2..N Div 2 j=2..N Div 2 i*j
(N-1) Div i N

S:=S+1

2013.09.25.


16/42

Ciklusok Algoritmus2: S:=0

ELTE

Változó i,j:Egész

i=2..N Div 2 j:=2 i*j
Algoritmus3: S:=0

Változó i:Egész

i=2..N Div 2 S:=S+((N-1) Div i)-1 2013.09.25.


17/42

Ciklusok Tanulságok:  Ha

ELTE

2013.09.25.

az utófeltételben , , vagy jel van, akkor a megoldás mindig ciklus!  Ha az utófeltételben vagy jel van, akkor a megoldás sokszor feltételes ciklus!  Ha az utófeltételben jel van, akkor a megoldás sokszor számlálós ciklus! ( is…)  Két egymásba ágyazott jel esetén két ciklus lesz egymás belsejében, általában.  Feltételes esetén a ciklusban elágazás lesz. Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 3. előadás

18/42

Ciklusok algoritmus – kód

Feltételes ciklus: Tipikus előfordulás: a beolvasás ellenőrzésénél (l. 2.ea.-ban) ELTE

feltétel utasítások

while (feltétel){ utasítások }

utasítások feltétel

do{ utasítások }while (feltétel);

Számlálós ciklus: i=1..N utasítások i=1..N; x-esével utasítások 2013.09.25.

for (int i=1;i<=N;++i){ utasítások }

for (int i=1;i<=N;i+=x){ utasítások }


19/42

Feladat elágazásra, vagy más megoldás kell? Feladat:

ELTE

A japán naptár 60 éves ciklusokat tartalmaz, az éveket párosítják, s mindegyik párhoz valamilyen színt rendelnek (zöld, piros, sárga, fehér, fekete). o o o o o

1,2,11,12, …,51,52: zöld évek 3,4,13,14,…,53,54: piros évek 5,6,15,16,…55,56: sárga évek 7,8,17,18,…57,58: fehér évek 9,10,19,20,…,59,60: fekete évek

Tudjuk, hogy 1984-ben indult az utolsó ciklus, amely 2043-ban fog véget érni. Írjunk programot, amely megadja egy M évről (1984≤M≤2043), hogy milyen színű! 2013.09.25.


20/42

Feladat elágazásra, vagy más megoldás kell? Specifikáció1:  Bemenet:

ELTE

2013.09.25.

Egy még „ismeretlen” halmaz

év Egész  Kimenet: s Szín  Előfeltétel: 1984≤év és év≤2043  Utófeltétel: ((év-1984) Mod 10) Div 2=0 és s=”zöld” vagy ((év-1984) Mod 10) Div 2=1 és s=”piros” vagy …  Definíció: Szín:=(”zöld”,”piros”,”sárga”,”fehér”, A Szín halmaz ”fekete”) Szöveg definiálása,

visszavezetés a Szöveg halmazra Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 3. előadás

21/42


ELTE

2013.09.25.

A Szín halmaz év Egész definiálása itt is lehetséges  Kimenet: s Szín Szín=(”zöld”,”piros”,”sárga”, ”fehér”,”fekete”) Szöveg  Előfeltétel: 1984≤év és év≤2043  Utófeltétel: ((év-1984) Mod 10) Div 2=0 és s=”zöld” vagy ((év-1984) Mod 10) Div 2=1 és s=”piros” vagy …


22/42


ELTE

2013.09.25.

A Szín halmaz év Egész definiálása itt is lehetséges  Kimenet: s Szín Szín=(”zöld”,”piros”,”sárga”, ”fehér”,”fekete”) Szöveg  Előfeltétel: 1984≤év és év≤2043  Utófeltétel: (((év-1984) Mod 10) Div 2=0 s=”zöld”) és (((év-1984) Mod 10) Div 2=1 s=”piros”) és …


23/42

Feladat elágazásra, vagy más megoldás kell? Algoritmus:

ELTE

y:=((év-1984) Mod 10) Div 2 y=0 y=1 y=2 y=3 y=4 s:= s:= s:= s:= s:= ”zöld” ”piros” ”sárga” ”fehér” ”fekete”

Változó y:Egész

Kérdés: Akkor is ezt tennénk, ha 5 helyett 90 ágat kellene írnunk? A válasz előtt egy új adatszerkezet: a tömb. 2013.09.25.


24/42

Tömbök Kapcsolódó fogalmak:  Sorozat:

ELTE

2013.09.25.

azonos típusú elemek egymásutánja, az elemei sorszámozhatók.  Tömb: véges hosszúságú sorozat, a sorozat iedik tagjával végezhetünk műveleteket (adott a legkisebb és a legnagyobb index, vagy az elemszám).  Index: sokszor 1..N, máskor 0..N–1.  Tömbelem-műveletek: elemérték-hivatkozás, elemérték-módosítás (az elem indexeléssel kiválasztva). Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 3. előadás

25/42

Tömbök (algoritmusban)

Deklarációs példák:

ELTE

X:Tömb[1..N:Egész] Y:Tömb[0..4:Szöveg] Az előbbi példa színek halmazát reprezentálhatjuk egy konstans tömbbel: Konstans Színek:Tömb[0..4:Szöveg]= (”zöld”,”piros”,”sárga”,”fehér”,”fekete”)

Hivatkozási példák: X[1]:=X[N]; Y[i]:=Színek[0] Y:=Színek 2013.09.25.


26/42

Tömbök

Tömb-elemszám indexelés 0..??? indexelés 0..N Tömb-elemszám

(algoritmusban+kódban)

Deklarációs példák –

ELTE

a C++ kódjukkal:

int X[N+1] X:Tömb[1..N:Egész] Y:Tömb[0..4:Szöveg] string Y[5] Az előbbi példa Szín halmazát reprezentálhatjuk egy konstans tömbbel: Konstans Színek:Tömb[0..4:Szöveg]= (”zöld”,”piros”,”sárga”,”fehér”,”fekete”)

const string Szinek[5]={"zöld","piros", "sárga","fehér","fekete"};

2013.09.25.


27/42

Tömbök (C++ kódban – áttekintés)

Statikus tömbök: 

Deklaráció: const int MaxN=???;//tömb max.elemszáma típus tömb[MaxN]; //tömbdeklaráció //0..MaxN-1 közötti indexekkel …

ELTE



Hivatkozások:

Eltérés a specifikációban és az algoritmusban szokásostól!

… tömb[ind] … //tömbérték-hivatkozás … tömb[ind]=kif;//tömbérték-módosítás …

2013.09.25.


28/42


Statikus tömb konstansok: 

Deklaráció: const int N=???;//tömb elemszáma const típus tömb[N]={t1,t2,…,tN}; //konstans tömb deklarációja, //0..N-1 közötti indexekkel

ELTE

vagy

Figyeljünk a sizeof szintaxisára: más adatra, és más típusra!

2013.09.25.

const típus tömb[]={t1,t2,…,tN}; //konstans tömb deklarációja const int N=sizeof tömb/sizeof(típus); //tömb elemszáma //indexek: 0..N-1 közötti


29/42


Dinamikus tömbök: 

Deklaráció: int N; …

ELTE



//tömb aktuális elemszám

Létrehozás: N=???;//N meghatározása, pl. beolvasása típus tömb[N];//tömbhelyfoglalás N db //típus típusú elem számára



Hivatkozások (nincs változás): … tömb[ind] … //tömbérték-hivatkozás … tömb[ind]=kif;//tömbérték-módosítás …

2013.09.25.


30/42


Tömb beolvasása (ellenőrzéssel):

Algoritmikusan: Be: N [HelyesN(N))]

A HelyesN-be beleértem ELTE a szintaktikus és szemantikus ellenőrzést is.

bool hiba; //van-e hiba? … do{ cout << "Elemszám:"; cin >> N; hiba=!HelyesN(N); if (hiba) { cout << "hibaüzet" << endl; } }while (hiba); L. még korábban!

2013.09.25.


31/42


Tömb beolvasása (ellenőrzéssel): Algoritmikusan: Be: v(1..N) [Helyes(v(1..N))]

A Helyes-be beleértem a szintaktikus és ELTE szemantikus ellenőrzést is.

bool hiba; //van-e hiba? for (int i=0;i> cin N; >> v[i]; << i+1 <
Térjünk vissza a kérdésre… 2013.09.25.


L. még korábban! 32/42

Elágazás helyett tömb Specifikáció:  Bemenet:

ELTE

2013.09.25.

év Egész  Kimenet: s Szín Szín=(”zöld”,”piros”,”sárga”, ”fehér”,”fekete”) Szöveg Konstans Színek Tömb[0..4:Szín]= (”zöld”,”piros”,”sárga”,”fehér”,”fekete”)  Előfeltétel: 1984≤év és év≤2043  Utófeltétel: s=Színek[((év-1984) Mod 10) Div 2] Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 3. előadás

33/42

Elágazás helyett tömb Algoritmus: y:=((év-1984) Mod 10) Div 2 s:=Színek[y]

Változó y:Egész

ELTE

2013.09.25.


34/42

Konstans tömbök alkalmazása Feladat: Írjunk programot, amely egy 1 és 99 közötti számot betűkkel ír ki! ELTE

Leglogikusabb helyre téve. Az algoritmus szempontjából bemenet…

2013.09.25.


N Egész Konstans egyes Tömb[0..9:Szöveg]= (””, ”egy”,…,”kilenc”) Konstans tizes Tömb[0..9:Szöveg]= (””, ”tizen”,…,”kilencven”)  Kimenet: S Szöveg  Előfeltétel: 1 N 99 Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 3. előadás

35/42

Konstans tömbök alkalmazása  Utófeltétel:

ELTE

N=10 S=”tíz” és N=20 S=”húsz” és N {10,20} S=tizes[N Div 10]+ egyes[N Mod 10]

Algoritmus: N=10 N=20 N {10,20} S:=”tíz” S:=”húsz” S:=tizes[N Div 10]+ egyes[N Mod 10]

2013.09.25.


36/42

Konstans tömbök alkalmazása Feladat: Írjunk programot, amely egy hónapnévhez a sorszámát rendeli! ELTE

2013.09.25.


H Szöveg Konstans HóNév Tömb[1..12:Szöveg]= (”január”,…,”december”)  Kimenet: S Egész  Előfeltétel: H HóNév  Utófeltétel: 1 S 12 és HóNév[S]=H Horváth-Papné-Szlávi-Zsakó: Programozási alapismeretek 3. előadás

37/42

Konstans tömbök alkalmazása Algoritmus: Változó i:Egész

i:=1 HóNév[i] H i:=i+1

ELTE

S:=i Kérdés: mi lenne, ha az ef. nem teljesülne? Futási hiba? Végtelen ciklus? 2013.09.25.


38/42

Konstans tömb – mit tárolunk? Feladat: Egy nap a nem szökőév hányadik napja?

Specifikáció1: ELTE

 Bemenet:

H,N Egész Konstans hó Tömb[1..12:Egész]= (31,28,31,…,31)  Kimenet: S Egész  Előfeltétel: 1≤H≤12 és 1≤N≤hó[H]  Utófeltétel:

H 1

S

N

hó[i] i 1

2013.09.25.


39/42

Konstans tömb – mit tárolunk? Algoritmus:

ELTE

S:=N i=1..H–1 S:=S+hó[i]

Változó i:Egész

Megjegyzés: Szökőév esetén H≥3 esetén Set 1-gyel meg kellene növelni! (És az előfeltétel is módosul.)

2013.09.25.


40/42

Konstans tömb – mit tárolunk? Egy másik megoldás: Tároljuk minden hónapra, hogy az előző hónapokban összesen hány nap van! ELTE

Specifikáció2:  Bemenet:

… Konstans hó Tömb[1..12:Egész]= (0,31,59,90,…,334)  Utófeltétel: S=N+hó[H] Kérdés: Ez jobb megoldás? Mi lesz az előfeltétellel? 2013.09.25.


41/42

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

Programozási alapismeretek 3. előadás

Recommend Documents