HORVÁTH ZSÓFIA
1. Beadandó feladat
[email protected]
(HOZSAAI.ELTE)
2011. ápr 7.
8-as csoport
10-es Feladat: Keressünk egy egész számokat tartalmazó négyzetes mátrixban olyan oszlopot, ahol a főátló alatti elemek mind nullák!
Megoldasi terv: Specifikacio: A = (mat: Zn×m,ind: N, l: L) Ef =(mat = mat`) n-1 Uf =( Ef ^ (l,ind) = SEARH (mind_nulla(i)) i=1
függvény szignatúra: mind_nulla: Z L
függvény definíciója: n mind_nulla (k) : ∀ SEARCH (mat [i,j]≠0) j=1+i
Lineáris keresésbe ágyazott optimista lineáris keresés.
Struktogram:
1
HORVÁTH ZSÓFIA
1. Beadandó feladat
[email protected]
(HOZSAAI.ELTE)
2011. ápr 7.
8-as csoport
Alternatív Megoldasi terv: Specifikacio: A = (matrix: Zn×m, l: L) Ef =( matrix = matrix` ^ n ≥2) n-1 Uf =( Ef ^ l= SEARH (matrix [n+1][n] ==0)) i=1
függvény szignatúra: mind_nulla: Z L
függvény definíciója: n-1 mind_nulla (k) : ∀ SEARCH (matrix [n+1][n]==0) j=1
Lineáris keresésbe ágyazott optimista lineáris keresés.
Struktogram:
2
HORVÁTH ZSÓFIA
1. Beadandó feladat
[email protected]
(HOZSAAI.ELTE)
2011. ápr 7.
8-as csoport
Implementacio: Program vaz Függvények – egyszerű – kapcsolódási szerkezete:
main()
beolvas_param()
beolvas()
oszlop_nulla()
mind_nulla()
fileKi()
Bemeno adatok formaja A program az adatokat be egy külső fájlból olvassa be, közvetlenül nem lehet megadni őket. Ha a programot parancssorból indítjuk úgy, hogy paraméterként megadjuk a bemenő adatokat tartalmazó szöveges állomány nevét, akkor innen olvassa be a program az adatokat. Ha nem adunk meg a parancssorban állomány nevet vagy nem parancssorból indul a program, akkor a program újra megkérdezi az adatbevitelhez az állomány nevét. Ha rosszul adja meg az állománynevet vagy nem létező fájlnevet ad meg a felhasználó, akkor a program újra bekéri a beolvasni kívánt adatot, azaz a fájl nevét a kiterjesztésével. A bemeneti állomány formája kötött, s arról feltesszük, hogy helyesen van kitöltve, ezért ezt külön nem ellenőrizzük. Az első sorban a mátrix sor– és oszlopszáma szerepel, szóközökkel elválasztva. (Mivel négyzetes mátrixokra akarjuk használni a programot, az oszlop és sorszáma azonos, de ha nem a program úgyis lefut, csak rossz eredményt ad.) Ezt követően olvashatók a mátrix elemei –csak a konzolablakban– , ezek is szóközökkel elválasztva, majd egy szöveges válasz. Igaz eredményt kapva a program azt is megmondja, melyik oszlopban van a főátló alatt csak nulla. Minden sor végén (az utolsó sor végén is) sorvége jel legyen. Példák:
2 2 0 0 1 0
3 1 2 1
3 2 3 0 4 0 0
4 1 0 0 0
4 2 6 0 0
3 7 1 0
4 8 2 5
5 9 4 1 6 0
5 8 3 2 7 0
7 2 3 8 0
6 1 4 9 1
5 0 5 0 0
3
HORVÁTH ZSÓFIA
1. Beadandó feladat
[email protected]
(HOZSAAI.ELTE)
2011. ápr 7.
8-as csoport
A program fuggvenyei main() Feladat: A főprogram gondoskodik a beolvasás, a kiértékelés és a kiíratás részek aktivizálásáról.
Bemenő adatok: int n, m vector
> matrix
a mátrix méreteit tartalmazó azonos értékű változók a mátrix elemeit tartalmazó mátrix
Kimenő adatok: Válasz: Volt ilyen oszlop, Nem volt ilyen oszlop. Válasz: Melyik oszlop volt, ha volt.
(szöveges válasz) (visszatérési-érték)
Tevékenység: Elvégzi a fájlból való beolvasást. Ezután meghívja a feladatot megoldó mind_nulla() függvényt. Ennek eredményétől függően pozitív vagy negatív választ ír a standard kimenetre és a fájlba.
Definíció: Helye: 1bead10.cpp
beolvas() Feladat: A mátrix sor- és oszlop nagyságát, illetve a mátrix elemeit olvassa be a megadott beviteli állományból.
Bemenő adatok: string fajlnev
az inputfájl neve
Kimenő adatok: int n, m vector > matrix
a mátrix méreteit tartalmazó azonos értékű változók a mátrix elemeit tartalmazó mátrix
Tevékenység: Elvégzi a fájlból való beolvasást és megfelelő méretűre (n és „m”) állítja be a mátrix sor és oszlop „tömbjét”, majd feltölti az értékeit intekkel. A beolvasott adatok a konzolablakban is megjelennek.
Definíció: Helye: 1bead10.cpp void beolvas(vector > &mat) beolvas_param()
Csupán annyiban különbözik a beolvas() függvénytől, hogy a cmd-ből való indításánál hat.
Definíció: Helye: 1bead10.cpp void beolvas_param(vector > &mat, string fname) 4
HORVÁTH ZSÓFIA
1. Beadandó feladat
[email protected]
(HOZSAAI.ELTE)
2011. ápr 7.
8-as csoport
bool oszlop_nulla() Feladat: Megnézi, hogy van-e olyan oszlop, amiben a főátló alatti elemek mind nullák.
Bemenő adatok: vector > matrix
a mátrix neve
Kimenő adatok: bool értékt
ami vagy true vagy false
Tevékenység: Optimista Lineáris Keresés: Végigmegy a mátrix oszlopainak (a főátló alatti) elemein és amint olyan elemet talál köztük, ami nem nulla, továbblép a következő oszlopra. Ezt a műveletet az utolsó előtti oszlopig ismételi. Ha nem talált olyan oszlopot, ami mind 0 visszaadja a „p” változónak a hamis értéket, ha talált csak 0-ból álló főátló alatti elemeket, akkor kilép a ciklusból és a „p” értékét beállítja igaznak.
Definíció: Helye: 1bead10.cpp bool oszlop_nulla(vector< vector > &mat,bool &p, int i, int &ind)
mind_nulla() Feladat: Megnézi, hogy van-e olyan oszlop, amire igazat ad az „oszlop_nulla()” függvény.
Bemenő adatok: vector > matrix
a négyzetes mátrix neve.
Kimenő adatok: bool változó
ami vagy true vagy false
Tevékenység: Lineáris Keresés: Végigmegy a mátrix oszlopaira kapott logikai eredményeken, melyet a „bool oszlop_nulla()” függvény adott az adott oszlopoknak és megkeresi az első olyat, mely igaz. Ha nem talált, akkor a mátrixnak egyik oszlopában sincs a főátló alatt csak 0.
Definíció: Helye: 1bead10.cpp bool mind_nulla(vector > &mat, int &ind,bool &l)
fileKi() Feladat: Az „eredmeny.txt” fájlba kiírja a választ.
Kimenő adatok: válasz
Volt ilyen oszlop és melyik; Nem volt ilyen oszlop.
Definíció: Helye: 1bead10.cpp void fileKi(string valasz, bool l,int ind)
5
HORVÁTH ZSÓFIA
1. Beadandó feladat
[email protected]
(HOZSAAI.ELTE)
2011. ápr 7.
8-as csoport
Tesztelesi terv Tesztesetek a feladat specifikációja alapján (fekete doboz tesztelés) 1. Ha a mátrix elemeinek száma kisebb, mint 2, a program lefut, eredmény: nem volt ilyen nap. (6.txt) 2. Ha egyáltalán nincs benne olyan sor akkor válaszként hamisat ad. (1.txt) 3. Ha rosszul van kitöltve a fájl, akkor is lefut, de hamis értéket ad vissza. (3.txt) 4. Ha minden eleme 0, akkor már az első oszlop után igaz eredményt ad vissza. (4.txt) 5. Ha a legutolsó elem 0, akkor is hamisat dob, hiszen az még maga a főátló. (2.txt) 6. Ha az elemek helyett karaktereket tartalmazó fájlt nyit meg. (7.txt)
Tesztesetek a megoldó kód alapján (fehér doboz tesztelés) 1. A beolvasást végző függvények tesztelése:
Parancssorból indítás fájlnévvel és anélkül. Nem létező vagy rossz fájlnév megadása. Üres állomány esetén a program áll, majd hibát észlel és leáll. (5.txt) 2. Az oszlop _nulla () függvény tesztelése:
1. 2. 3. 4. 5.
ha sehol sincs benne nulla (1.txt) ha az első oszlop mind nulla (8.txt) ha a második oszlop nulla (matrix.txt) ha mind nulla (4.txt) ha a főátló nulla (9.txt)
3. A mind_nulla () függvény tesztelése:
1. igaz eredmények: a. matrix.txt, 4.txt, 8.txt 2. hamis eredmények: a. 1.txt, 2.txt
6