99 1

„Algoritmizálás és adatmodellezés tanítása” beadandó feladat: „Algtan1 tanári beadandó”/99 1

Készítette: Gipsz Jakab Neptun-azonosító: ABC123 E-mail: [email protected] Kurzuskód: IT-13AAT1EG Gyakorlatvezető neve: ???

2015. március 28.

1

A fenti feladatsor itt érhető el: http://biro.inf.elte.hu/ . Értelemszerűen töltendők itt ki a szerzőre vonatkozó adatok. A lábjegyzetek a végső dokumentációból törlendők! Csak az Ön segítését szolgálja. 1/13

Tartalom Felhasználói dokumentáció .................................................................................................................. 3 Feladat .............................................................................................................................................. 3 Futási környezet ............................................................................................................................... 3 Használat .......................................................................................................................................... 3 A program indítása ....................................................................................................................... 3 A program bemenete .................................................................................................................... 3 A program kimenete ..................................................................................................................... 3 Minta bemenet és kimenet ........................................................................................................... 4 Hibalehetőségek ........................................................................................................................... 4 Fejlesztői dokumentáció ...................................................................................................................... 6 Feladat .............................................................................................................................................. 6 Specifikáció ...................................................................................................................................... 6 Fejlesztői környezet ......................................................................................................................... 6 Forráskód ......................................................................................................................................... 7 Megoldás .......................................................................................................................................... 7 Programparaméterek .................................................................................................................... 7 Programfelépítés .......................................................................................................................... 7 Függvénystruktúra ....................................................................................................................... 8 Algoritmus ................................................................................................................................... 8 A kód ............................................................................................................................................ 9 Tesztelés ......................................................................................................................................... 11 Érvényes tesztesetek .................................................................................................................. 11 Érvénytelen tesztesetek .............................................................................................................. 13 Fejlesztési lehetőségek ................................................................................................................... 13

2/13

Felhasználói dokumentáció Feladat Egy repülőút során egyenlő távolságonként mértük a felszín tengerszint feletti magasságát. Zéró magasságot ott mértünk, ahol állóvíz volt, pozitív magasságot pedig ott, ahol szárazföld. Három egymást követő mérési eredményt jelöljön A, B és C. Ekkor B  bal oldali partot jelez, ha B>0 és A=0;  jobb oldali partot jelez, ha B>0 és C=0. Készítsen programot, amely meghatároz két szigetet, melyeknél nincs egymáshoz közelebbi szigetpár, ha nincs ilyen, akkor ezt egyetlen 0-val jelezze!

Futási környezet IBM PC, exe futtatására alkalmas, 32-bites operációs rendszer (pl. Windows 7). Nem igényel egeret.

Használat A program indítása A program az ABC123\szigetek.exe néven található a tömörített állományban. A szigetek.exe fájl kiválasztásával indítható.

A program bemenete A program az adatokat a billentyűzetről vagy fájlból olvassa be a következő sorrendben: # 0.

Bemód

1.

N Magasság1 Magasság2 … MagasságN

2. 3. ... N+1.

Magyarázat

Adat

A beolvasás módja (fájlból olvasás esetén 1, billentyűzetről olvasás esetén 0). A magasságmérés hossza (2N10000). Az első magasság (0Magasság19000). A második magasság (0Magasság29000). Az N-edik magasság (0MagasságN9000).

A program kimenete A program kiírja az egymáshoz legközelebbi két sziget bal és jobb partját jelző mérés sorszámát. A kimenet első sorába az első szigetet, a második sorba a második szigetet azonosító két adat kerül.

3/13

Minta bemenet és kimenet Mintafutás billentyűzetről való beolvasás esetén

Mintafutás fájlból való beolvasás esetén A bemeneti állomány nevét –a kiterjesztésével együtt– kell megadni, és a bemeneti állományt közvetlenül a futtatható állomány mellett kell elhelyezni. Megadható a könyvtári útvonal is, amennyiben nem az exe mellett található az adatfájl.

Hibalehetőségek Adat-beolvasási mód nem 0 vagy 1. Ha fájlból jönnek az adatok, akkor nem létezik (az adott könyvtárban) a paraméterként megadott nevű fájl. Az operációs rendszer által az útvonal-megadásra megkívánt szintaktikai elvárások megsértése esetén a fájl nem lesz megnyitható. A mérések száma nem egész szám, vagy nem esik a 2..10 000 intervallumba. Valamely magassági érték nem szám, vagy nem esik a 0..9 000 intervallumba. Fájlos input esetén az adatok helyességét nem vizsgálja a program. Billentyűzet-inputnál hiba esetén a program azzal jelzi a hibát, hogy újra kérdezi azt.

4/13

Mintafutás hibás bemeneti adatok esetén: Hibás adatforrás-, majd fájl-választás:

Hibás numerikus adat-megadás:

5/13

Fejlesztői dokumentáció Feladat Egy repülőút során egyenlő távolságonként mértük a felszín tengerszint feletti magasságát. Zéró magasságot ott mértünk, ahol állóvíz volt, pozitív magasságot pedig ott, ahol szárazföld. Három egymást követő mérési eredményt jelöljön A, B és C. Ekkor B  bal oldali partot jelez, ha B>0 és A=0;  jobb oldali partot jelez, ha B>0 és C=0. Készítsen programot, amely meghatároz két szigetet, melyeknél nincs egymáshoz közelebbi szigetpár, ha nincs ilyen, akkor ezt egyetlen 0-val jelezze!

Specifikáció A specifikációban nem foglalkozunk az adatforrással, csak a feladat lényegi részére koncentrálunk. Bemenet:

NN, MagasságokN*

Kimenet:

VanEL, Szig1,Szig2Sziget, Sziget=BalJobb, Bal,Jobb=N

Előfeltétel: N[2..10000]  i[1..N]: Magasságoki[0..9000] Utófeltétel: db=∑N−1 i=2 SzigetKezdet(i)  szigekSziget*  i[1..db]: (szigeki.Bal[2..N]  szigeki.Jobb[1..N-1]  szigeki.Bal≤szigeki.Jobb  SzigetKezdet(szigeki.Bal)  SzigetVég(szigeki.Jobb)  i[szigeki.Bal..szigeki.Jobb]: Magasságoki>0)  db<2  VanE=Hamis  db2  VanE=Igaz  i[1..db-1]: Szig1=szigeki  Szig2=szigeki+1  i[1..db-1]: szigeki+1.Bal-szigeki.JobbSzig2.Bal-Szig1.Jobb Definíció:

SzigetKezdet: NL SzigetKezdet(i):=Magasságoki>0  Magasságoki-1=0 SzigetVég: NL SzigetVég(i):=Magasságoki>0  Magasságoki+1=0

Megjegyzés: a „ha nincs ilyen” kitételt (a VanE=Hamis esetben) a program egyetlen 0 kiírásával fogja jelezni, nem pedig a logikai érték megjelenítésével (hűen a feladat eredeti kiírásához).

Fejlesztői környezet IBM PC, exe futtatására alkalmas operációs rendszer (pl. Windows 7). fpc Pascal-fordítóprogram (v2.6.4), Geany (v1.23.1) fejlesztői környezet.

6/13

Forráskód A teljes fejlesztői anyag –kicsomagolás után– az ABC123 nevű könyvtárban található meg. A fejlesztés során használt könyvtár-struktúra: Állomány

Magyarázat

ABC123\szigetek.exe

futtatható kód

ABC123\forras\szigetek.pas ABC123\forras\AltRutinok.inc ABC123\forras\FajlRutinok.inc

Pascal forrás általános rutinokat tartalmazó inklúd-állomány fájlkezelő rutinokat tartalmazó inklúd-állomány

ABC123\teszt1.txt ABC123\teszt2.txt ABC123\teszt3.txt ABC123\teszt4.txt ABC123\teszt5.txt

teszt-bemeneti fájl1 teszt-bemeneti fájl2 teszt-bemeneti fájl3 teszt-bemeneti fájl4 teszt-bemeneti fájl5

ABC123\doksi\szigetek.docx

dokumentációk (ez a fájl)

Megoldás Programparaméterek Konstans MaxN MaxMagasság

: Egész(10000) [a mérések maximális száma] : Egész(9000) [a maximális magasság]

Típus TMaggasságok TSziget

= Tömb(1..MaxN:Egész) = Rekord(bal,jobb:Egész)

Változó N Magasságok Szig1,Szig2

: Egész : TMagasságok : TSziget

Programfelépítés A program által használt modulok (és helyük): szigetek.pas – Crt.ppu – AltRutinok.inc – TextRutinok.inc –

2

program, a forráskönyvtárban képernyő-, és billentyűkezelés, a Pascal rendszer része általános segéd rutinok, a forráskönyvtárban2 karakteres fájlt kezelő segéd rutinok, a forráskönyvtárban

A „Bíró”-rendszerbe való feltöltéskor ezekre nincs szükség, csak a véglegeshez kellenek. A különválasztásra is „csak” az elegancia okán került sor. 7/13

Függvénystruktúra Főprogram

AdatBeolvasas

LegkozelebbiSzigetek

EredmenyKiir

UjLap

A teljes program algoritmusa Program Szigetek: [programparaméterek:] Konstans MaxN:Egész(10000) [a mérések maximális száma, a bekéréshez] MaxMagasság:Egész(9000) [a maximális magasság, a bekéréshez] Típus TMagasságok=Tömb(1..MaxN:Egész) TSziget=Rekord(bal,jobb:Egész) Változó [Bemenet:] N:Egész Magasságok:TMagasságok [Kimenet:] VanE:Logikai Szig1,Szig2:TSziget [főprogram:] AdatBeolvasás(N,Magasságok) LegközelebbiSzigetek(N,Magasságok,VanE,Szig1,Szig2) EredményKiirás(VanE,Szig1,Szig2) Program vége. [alprogramok:] Eljárás AdatBeolvasás(Változó n:Egész, magok:TMagasságok): Változó beMod:Egész f:SzövegFájl fN:Szöveg Be:beMod [’0’ vagy ’1’] Ha beMod=’1’ akkor [fájlból olvasás:] Be:fN [OlvasásraNyit(f,fN)] Olvas(f,n) Olvas(f,magok(1..n)) 3 Lezár(f) különben [billentyűről olvasás:] Be:n [n[2..MaxN]] Be:magok(1..n) [n[0..MaxMagasság]] Elágazás vége Eljárás vége.

3

Ez az alábbi rövidített leírása: Ciklus i=1-től n-ig Olvas(f,magok(i)) Ciklus vége

8/13

BillreVar

Eljárás LegkozelebbiSzigetek(Konstans n:Egész, magok:TMagasságok, Változó vanE:Logikai, sz1,sz2:TSziget): [Lokális konstansok, típusok, változók:] Kosntans MaxSz:Egész(MaxN Div 2) sziget0:TSziget=(bal:0,jobb:0) Típus TSzigetek=Tömb(0..MaxSz:TSziget) Változó db,i, minI,minT:Egész szigek:TSzigetek [szigetek inicializálása:] szigek(0..MaxSz):=sziget0 4 [szigetek kiválogatása:] db:=0 Ciklus i=2-től n-1-ig Ha magok(i)>0 és magok(i-1)=0 akkor db:+1 szigek(db).bal:=i Elágazás vége Ha magok(i)>0 és magok(i+1)=0 akkor szigek(db).jobb:=i Elágazás vége Ciklus vége Ha db>0 és szigek(db).jobb=0 akkor db:-1 [a túlpart bal partja, amely nem sziget] Ha db<2 akkor [nincs két legközelebbi sziget:] vanE:=Hamis különben [van legalább két sziget:] [minimális távolság:] minI:=1; minT:=szigek(2).bal-szigek(1).jobb Ciklus i=2-től db-1-ig Ha szigek(i+1).bal-szigek(i).jobb<minT akkor minI:=i; minT:=szigek(i+1).bal-szigek(i).jobb Elágazás vége Ciklus vége szig1.bal:=szigek(minI).bal; szig1.jobb:=szigek(minI).jobb sz2.bal:=szigek(minI+1).bal; sz2.jobb:=szigek(minI+1).jobb vanE:=Igaz Elágazás vége Eljárás vége. Eljárás EredményKiirás(Konstans vanE:Logikai, sz1,sz2:TSziget): Ha vanE akkor Ki: 0 Különben Ki: sz1.bal,sz1.jobb,sz2.bal,sz2.jobb [a megkívánt formátum szerint] Elágazás vége Eljárás vége.

4

Ez az alábbival ekvivalens, rövidebb leírás:

Ciklus i=0-tól MaxSz-ig szigek(0.MaxSz):=sziget0 Ciklus vége

9/13

A kód A sziget.pas fájl tartalma: (* Készítette: Gipsz Jakab Neptun: ABC123 E-mail: [email protected] Feladat: Algtan1 tanári beadandó/99 *) Program Szigetek; Uses Crt; {$i AltRutinok.inc} {$i FajlRutinok.inc} //a program: Const Cim='Legközelebbi szigetek'; MaxN=10000; MaxMagassag=9000; Type TMagassagok=Array [1..MaxN] of Integer; TSziget=Record bal,jobb:Integer End; Var //Bemenet: N:Integer; Magassagok:TMagassagok; //Kimenet: VanE:Boolean; Szig1,Szig2:TSziget; Procedure AdatBeolvasas(Var n:Integer; Var magok:TMagassagok); … Begin … End; Procedure LegkozelebbiSzigetek(Const n:Integer; magok:TMagassagok; Var vanE:Boolean; Var sz1,sz2:TSziget); … Begin … End; Procedure EredmenyKiir(Const VanE:Boolean; Const sz1,sz2:TSziget); Begin … End; Begin UjLap(Cim); AdatBeolvasas(N,Magassagok); LegkozelebbiSzigetek(N,Magassagok,VanE,Szig1,Szig2); EredmenyKiir(VanE,Szig1,Szig2); BillreVar; End.

10/13

Az AltRutinok.inc fájl tartalma: (* Készítette: Szlávi Péter Neptun: ZDOF7J E-mail: [email protected] Feladat: általánosan használható rutinok *) Procedure UjLap(Const cim:String); … Begin … End; …

A TextRutinok.inc fájl tartalma: (* Készítette: Szlávi Péter Neptun: ZDOF7J E-mail: [email protected] Feladat: Text fájlok kezelését támogató rutinok *) Function OlvasasraNyit(Var f:Text; Const fN:String):Boolean; … Begin … End; …

Tesztelés Érvényes tesztesetek 1.

teszteset: be1.txt Bemenet – nincs sziget; minimális hossz

N=2 Magasság1 = 0 Magasság2 = 0 Kimenet

0

11/13

2.

teszteset: be2.txt Bemenet – kontinenssel kezdődik, van legalább 2 sziget

N = 12 Magasság1 = 3 Magasság2 = 0 Magasság3 = 2 Magasság4 = 0 Magasság5 = 4 Magasság6 = 3 Magasság7 = 0 Magasság8 = 0 Magasság9 = 3 Magasság10 = 0 Magasság11 = 2 Magasság12 = 0 Kimenet

Szig1 = 3 3 Szig1 = 5 6 3.

teszteset: be3.txt Bemenet – kontinenssel végződik, van legalább 2 sziget

N=… Magasság1 = … … Kimenet

… 4.

teszteset: be4.txt Bemenet – nincs kontinens, egy sziget van

N=… Magasság1 = … … Kimenet

… 5.

teszteset: be5.txt Bemenet – csak kontinens van

N=… Magasság1 = … … Kimenet

…

12/13

Érvénytelen tesztesetek 6.

teszteset Bemenet – Rossz adatforrás

Adatforrás = „fájlból” Kimenet

Újrakérdezés 7.

teszteset Bemenet – Rossz fájlnév

Adatforrás = 1 Fájlnév= „C:\rosszKonyvtar” Fájlnév= „C:\joKonyvtar\rosszFajlnev” Kimenet

Újrakérdezés Újrakérdezés 8.

teszteset

…

Fejlesztési lehetőségek 1. Hibás fájl-bemenetek felismerése, és a hiba helyének (sor sorszámának) kiírása. 2. A hibára utaló hibaüzenetek megadása. 3. Többszöri futtatás megszervezése

13/13