Problem S. 11. (October 2005)
S. 11. We often categorize things according to various properties and look for relations among them. Write a program to make logical deductions among properties.
The program should read the input from the keyboard (or standard input): each line will contain a proposition or a question. The program should answer them in the next line on the screen (or standard output).
Propositions or questions refer to various properties. An elementary property consists of a single word, e.g., small or red. Every word is considered as an elementary property, except for the following ones: NOT EXIST, EXIST, AND, OR, NOT, IF and THEN.
Negation of an elementary property is formed by attaching the prefix NOT, e.g., the negation of red is NOT RED.
Compound properties are formed by joining some elementary properties or negations of elementary properties using the words AND or OR, e.g., small AND NOT red. However, mixing these conjunctive words, as in big AND red OR blue, is not allowed.
Three types of propositions are allowed with the following syntax:
EXIST (property)
NOT EXIST (property)
IF (property) THEN (property)
A question is formed by putting a question mark at the end of a proposition.
The program should give any of the following answers to a given proposition:
UNDERSTOOD if the proposition corresponds to a new piece of information
I KNOW if the proposition is a consequence of earlier ones
CONTRADICTION (the program should ignore these propositions)
I DO NOT UNDERSTAND if the input is syntactically incorrect
The program should reply to a question with
YES, or NOT EXIST if the question referred to a true proposition
NO, or BUT EXIST if the question referred to a false proposition
I DO NOT KNOW if the answer might be true or false
The program runs until the user aborts it. You may assume that the number of elementary properties is at most 8 and the input consists of at most lines. Upper and lower case letters should be considered equal. Every character which is not a letter or question mark should be considered as ``space''.
Example (answers of the computer are in italics):
IF dog OR cat OR horse THEN hairy AND fourlegged UNDERSTOOD IF dachshund OR foxterrier THEN dog UNDERSTOOD IF foxterrier THEN fourlegged I KNOW IF mosquito THEN sixlegged UNDERSTOOD IF dachshund THEN hairy? YES EXIST dachshund? I DO NOT KNOW EXIST dachshund UNDERSTOOD NOT EXIST hairy AND dog? BUT EXIST IF fourlegged THEN NOT sixlegged UNDERSTOOD EXIST horse AND mosquito? NOT EXIST NOT EXIST sixlegged AND dachshund? NO EXIST fourlegged OR sixlegged AND NOT hairy? I DO NOT UNDERSTAND |
The source code (s11.pas, s11.c, ...) of the program should be submitted.
(10 pont)
Deadline expired on November 15, 2005.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Először is megjegyezzük, hogy a feladatbeli példában kilencféle elemi tulajdonság szerepel. A rugalmasság kedvéért a programunkat úgy valósítjuk meg, hogy az elemi tulajdonságok maximális számát egy makróban definiáljuk.
A program működési elve
A programban 10-féle elemi tulajdonságot engedünk meg. Egy tetszőleges dologra, objektumra mindegyik tulajdonság vagy teljesül, vagy pedig nem teljesül; ebből a szempontból egy objektum legfeljebb 210=1024-féle lehet. Ezért definiálunk 1024-féle tulajdonság atomot, amelyek megfelelnek az elemi tulajdonságok részhalmazainak. Minden elemi és összetett tulajdonságot az atomok egy részhalmazaként képzelünk el. A részhalmazban szereplő elemi tulajdonságok igazak az adott atomra, a részhalmazon kívüli elemi tulajdonságok pedig nem teljesülnek rá.
A HA-AKKOR és a NINCS alakú állítások bizonyos atomokról azt állítják, hogy olyan tulajdonságú dolog nincs. Ezek az állítások tehát a lehetséges atomok halmazát szűkítik; az ilyen állításokat szűkítésnek fogjuk nevezni. A LÉTEZIK állítások pedig atomok halmazairól állítják, hogy legalább az egyikük létezik. Ezek az egzisztencia állítások.
A program tárolja a lehetséges atomok halmazát, és ezt minden egyes elfogadott szűkítéskor módosítja. Azokat a nem üres halmazokat pedig, amelyekről valamelyik LÉTEZIK állításból tudjuk, hogy nem lehetnek üresek, külön-külön eltároljuk. Szűkítéskor a nem üres halmazokból is töröljük a meg nem engedett elemeket.
A szűkítések ellenőrzése két részből áll. A szűkítés mindig azt állítja, hogy atomok csak egy bizonyos A halmazban lehetnek. Ha az A halmaz diszjunkt valamelyik nem üres B halmazzal, az ellentmondás. Az ilyen szűkítés nem megengedett, illetve kérdés esetén a válasz NEM. Az ellenőrzés második részeként ellenőrizzük a megengedett atomok M halmazát. Ha MA, akkor a szűkítés nem jelent új információt; a válasz IGEN, illetve TUDOM. Ha a szűkítés új információt jelent, akkor M-et és az összes nem üres halmazt elmetsszük A-val.
Az egzisztencia állítások ellenőrzése szintén két részből áll. Egy egzisztencia állítás azt mondja, hogy egy bizonyos A halmaz nem üres. Ha A diszjunkt a megengedett atomok halmazával, akkor ez ellentmondás. Ha pedig valamelyik korábbi nem üres halmaz részhalmaza A-nak, akkor az információ nem új.
A program felépítése
A példaprogramot C++-ban írtuk, és Linux alatt, GCC 3.3.3 fordítóval fordítottuk.
A program elején az ETN makróban definiáltuk az elemi tulajdonságok maximális számát, az ATN makróban pedig az atomokét.
Az atomokat megszámozzuk 0-tól 1023-ig. A tulajdonságokat egészekből álló halmazokkal reprezentáljuk:
typedef std::set<int> Tulajdonsag;
Az uresHalmaz és a teljesHalmaz változókat a részletszámolásoknál használjuk; az egyik halmaz üres, a másik a teljes {0,1,2,...,1023} halmaz.
A tulajdonságok legfontosabb műveleteit és relációit a * (metszet), + (unió), - (különbség, illetve komplementer), << és >> (részhalmaz) operátorok valósítják meg.
Az elemi tulajdonságokat is kódolnunk kell. A tulajdonsagKod függvény egy tulajdonságnevet alakít számmá; a visszaadott számok a 2-hatványok (1,2,4,8,...). Az elemiTulajdonsag függvény pedig tulajdonságnevet tulajdonsággá konvertál; a visszadott halmaz azokat az atomokat tartalmazza, amelyek sorszáma tartalmazza a tulajdonságkódnak megfelelő bitet, pl. a 2 kódú tulajdonsághoz tartozó halmaz: {2,3,6,7,10,11,...}
A lehetsegesHalmaz változó tartalmazza azokat az atomokat, amelyeket egyik szűkítés sem zárt még ki; értéke kezdetben a teljes halmaz. A nemUresHalmazok vektorban pedig azokat a halmazokat soroljuk fel, amelyek valamelyik egzisztencia állítás alapján nem lehetnek üresek.
A SzukitesEllenorzes ellenőrzi, hogy egy szűkítő állítás a korábbiak alapján igaz, hamis vagy új információ. A függvény paramétere azon atomok halmaza, amiket az állítás megenged. A SzukitesBejegyzes az új szűkítő információ bejegyzésére szolgál; az új megengedett halmazzal elmetszi a lehetsegesHalmaz-t és a nemUresHalmazok mindegyik elemét.
A Nincs és a HaAkkor függvények értelemszerűen a NINCS, illetve HA-AKKOR alakú állításokat és kérdéseket dolgozzák fel. Mindkét függvényben a kerdes argumentum mondja meg, hogy új állításról, vagy csak kérdésről van szó. Mindkét program meghívja a SzukitesEllenorzes függvényt, szükség esetén a Szukitesbejegyzes-t, és kiírja a képernyőre a választ.
Hasonlóan, az EgzisztenciaEllenorzes, EgzisztenciaBejegyzes és Letezik függvények dolgozzák fel a LETEZIK állátásokat és kérdéseket.
Az állítások és kérdések interpretációját további részekre bontottuk. A programban nem használtunk kivételeket (excpetionöket); helyette a voltHiba változóban jelezzük, ha az interpretáció nem sikerült.
Az osszetettTulajdonsag függvény szavak egy sorozatát alakítja atomok halmazává. A szavakat a szavak vektorban kapjuk, az átalakítandó tartomány első és utolsó elemének indexe elso, illetvet utso. Ez a függvény kezeli a NEM, az ÉS és a VAGY relációkat.
A SzavakraTordeles függvény egy stringet bont szavakra. A kérdőjel önálló szó.
Végül az EgySorFeldolgozasa függvény egy stringet szavakra bont, megvizsgálja az első szót és hogy az utolsó szó kérdőjel-e, és meghívja a HaAkkor, Nincs vagy a Letezik függvényt.
A sorok beolvasása végtelen ciklusban a main függvényben történik.
// S. 10. // Mekk Elek 11. o. t. // Nekeresd, Ezermesterképző Intézet // kaposzta@nekeresd.hu // Ezt a programot Linux alatt, GCC 3.3.3 fordítóval teszteltük. // -------------------------------------------------------------------- #include <iostream> #include <string> #include <map> #include <set> #include <vector> #define ETN 10 // Az elemi tulajdonságok maximális száma #define ATN (1 << 10) // Az atomi tulajdonságok max. száma // ==================================================================== // Összetett tulajdonságok kezelése. Az összetett tulajdonságok // tulajdonságatomok halmazai. Az atomokat megszámozzuk, az összetett // tulajdonságokat reprezentáló "Tulajdonsag" tipus ezért egészek egy // halmaza lesz. typedef std::set<int> Tulajdonsag; Tulajdonsag uresHalmaz; Tulajdonsag teljesHalmaz; // Az összes atom halmaza. Értéket a main-ben kap // -------------------------------------------------------------------- // VAGY művelet -- két tulajdonsághalmaz uniója Tulajdonsag operator + ( const Tulajdonsag &A, const Tulajdonsag &B ) { Tulajdonsag C; std::set_union( A.begin(), A.end(), B.begin(), B.end(), std::inserter( C, C.begin() )); return C; } // -------------------------------------------------------------------- // ÉS művelet -- két tulajdonsághalmaz metszete Tulajdonsag operator * ( const Tulajdonsag &A, const Tulajdonsag &B ) { Tulajdonsag C; std::set_intersection( A.begin(), A.end(), B.begin(), B.end(), std::inserter( C, C.begin() )); return C; } // -------------------------------------------------------------------- // Különbséghalmaz Tulajdonsag operator - ( const Tulajdonsag &A, const Tulajdonsag &B ) { Tulajdonsag C; std::set_difference( A.begin(), A.end(), B.begin(), B.end(), std::inserter( C, C.begin() )); return C; } // -------------------------------------------------------------------- // Tagadás -- komplementum képzés Tulajdonsag operator - ( const Tulajdonsag &A ) { return teljesHalmaz - A; } // -------------------------------------------------------------------- // Részhalmaz ellenőrzése bool operator << ( const Tulajdonsag &A, const Tulajdonsag &B ) { return ( (A-B).size() == 0 ); } bool operator >> ( const Tulajdonsag &A, const Tulajdonsag &B ) { return ( B << A ); } // ==================================================================== // Elemi tulajdonságok kezelése // Tulajdonság kódjának kikeresése. A függvény egy elemi tulajdonság // nevét kapja, és visszaadja a kódot. Ha a tulajdonság még nem // szerepelt, a következő szabad kódot kapja. Ha az elemi // tulajdonságok száma túl nagy, kilép a programból. int tulajdonsagKod( const std::string nev ) { // A korábbi név-kód párok static std::map<std::string,int> kodTabla; // Kikeressük a nevet a táblázatból std::map<std::string,int>::const_iterator it; it = kodTabla.find( nev ); // Ha szerepel a táblázatban, akkor megvan a kód if (it != kodTabla.end()) { return it->second; } // Nem szerepel a táblázatban. Ellenőrizzük, tele-e a táblázat if ( kodTabla.size() >= ETN ) { std::cout << "Túl sok elemi tulajdonság!" << std::endl; exit( 1 ); } // A kód a tábla mérete-edik 2-hatvány int kod = 1 << kodTabla.size(); kodTabla.insert( std::make_pair( nev, kod )); return kod; } // -------------------------------------------------------------------- // Elemi tulajdonság (szó) tulajdonsággá konvertálása Tulajdonsag elemiTulajdonsag( const std::string &nev ) { int kod = tulajdonsagKod( nev ); // A tulajdonság kódja int i; Tulajdonsag T; for (i=0; i<ATN; i++) { if ( i & kod ) T.insert( i ); } return T; } // ==================================================================== // A felhasználó által adott információk feldolgozása, tárolása. Tulajdonsag lehetsegesHalmaz; // Azok az atomok, amik létezhetnek (amikről senki // sem mondta, hogy nem léteznek) std::vector<Tulajdonsag> nemUresHalmazok; // Azon tulajdonságok felsorolása, // amiknek a kapott információ // alapján létezniük kell. // -------------------------------------------------------------------- // Szűkítő jellegű állítások és kérdések (HA .. AKKOR, NINCS) // ellenőrzése és feldolgozása. Egy szűkítés azt állítja vagy kérdezi, // hogy atomok csak egy bizonyos halmazban vannak(-e). Pl. a "NINCS A" // azt állítja, hogy csak az A tulajdonságban felsorolt atomok // létezhetnek. // A függvény bemenete tehát egy tulajdonság, és az a kérdés, hogy // létezik-e ezen kívül atom. Az eredmény háromféle lehet: // 0 = az eddigi információ alapján nem tudjuk // 1 = biztosan nem létezik -- az új állítás a korábbiakból következik // 2 = biztosan létezik -- az új állítás a korábbiaknak ellentmond int SzukitesEllenorzes( const Tulajdonsag &A ) { uint i; // Ha valamelyik biztosan nem üres halmazzal diszjunkt, akkor // ellentmond az eddigi információnak for (i=0; i<nemUresHalmazok.size(); i++) if (nemUresHalmazok[i] * A == uresHalmaz) return 2; // Ellenőrizzük, hogy az A-ban minden lehetséges atom szerepel-e if (lehetsegesHalmaz << A) return 1; else return 0; } // --------------------------------------------------------------------- // A szűkítés bejegyzése az adatbzázisba void SzukitesBejegyzes( const Tulajdonsag &A ) { uint i; // Szűkítjük a lehetséges atomok halmazát lehetsegesHalmaz = lehetsegesHalmaz * A; // Szűkítjüka biztosan létező halmazokat is for (i=0; i<nemUresHalmazok.size(); i++) nemUresHalmazok[i] = nemUresHalmazok[i] * A; } // --------------------------------------------------------------------- // "NINCS A" feldolgozása. Ha csak kérdés, akkor kerdes=true. A // függvény kiírja a választ a képernyőre, és nem ad vissza semmit void Nincs( const Tulajdonsag &A, bool kerdes ) { Tulajdonsag B = -A; switch (SzukitesEllenorzes( B )) { case 0: // Új információ if (kerdes) std::cout << "NEM TUDOM" << std::endl; else { SzukitesBejegyzes( B ); std::cout << "ÉRTEM" << std::endl; } break; case 1: // Következik a korábbiakból if (kerdes) std::cout << "NINCS" << std::endl; else std::cout << "TUDOM" << std::endl; break; case 2: // Ellentmond a korábbiaknak if (kerdes) std::cout << "DE IGEN" << std::endl; else std::cout << "EZ ELLENTMOND A KORÁBBIAKNAK" << std::endl; break; } } // --------------------------------------------------------------------- // "HA A AKKOR B" feldolgozása void HaAkkor( const Tulajdonsag &A, const Tulajdonsag &B, bool kerdes ) { Tulajdonsag C = -A + B; // A C halmaz az, amire szűkít switch (SzukitesEllenorzes( C )) { case 0: // Új információ if (kerdes) std::cout << "NEM TUDOM" << std::endl; else { SzukitesBejegyzes( C ); std::cout << "ÉRTEM" << std::endl; } break; case 1: // Következik a korábbiakból if (kerdes) std::cout << "IGEN" << std::endl; else std::cout << "TUDOM" << std::endl; break; case 2: // ellentmond a korábbiaknak if (kerdes) std::cout << "NEM" << std::endl; else std::cout << "EZ ELLENTMOND A KORÁBBIAKNAK" << std::endl; break; } } // --------------------------------------------------------------------- // Egzisztencia állítások (LÉTEZIK) ellenőrzése és feldolgozása. A // függvény bemenete ismét egy tulajdonság, amiről azt // állítjuk/kérdezzük, hogy az eddigi információ alapján van-e benne // létező atom. A lehetséges válaszok: // 0 = az eddigi információ alapján nem tudjuk // 1 = biztosan létezik -- a korábbiakból következik, hogy a halmaz // nem üres // 2 = biztosan nem létezik -- a halmaz a korábbiak alapján üres int EgzisztenciaEllenorzes( const Tulajdonsag &A ) { uint i; // Ellenőrizzük, hogy a halmazban csupa nemlétező atom van-e if (lehetsegesHalmaz * A == uresHalmaz) return 2; // Ha a halmaz tartalmazz valamelyik korábbi, semmiképpen sem üres // halmazt, akkor a halmaz biztosan nem üres for (i=0; i<nemUresHalmazok.size(); i++) if (A >> nemUresHalmazok[i]) return 1; return 0; } // --------------------------------------------------------------------- // Egzisztencia állítás bejegyzése void EgzisztenciaBejegyzes( const Tulajdonsag &A ) { // Az újabb nem üres halmazt hozzávesszük a listához nemUresHalmazok.push_back( A * lehetsegesHalmaz ); } // --------------------------------------------------------------------- // "LÉTEZIK A" feldolgozása. Ha kerdes=true, akkor csak kérdezzük void Letezik( const Tulajdonsag &A, bool kerdes ) { switch (EgzisztenciaEllenorzes( A )) { case 0: // Új információ if (kerdes) std::cout << "NEM TUDOM" << std::endl; else { EgzisztenciaBejegyzes( A ); std::cout << "ÉRTEM" << std::endl; } break; case 1: // Következik a korábbiakból if (kerdes) std::cout << "IGEN" << std::endl; else std::cout << "TUDOM" << std::endl; break; case 2: // Ellentmond a korábbiaknak if (kerdes) std::cout << "NEM" << std::endl; else std::cout << "EZ ELLENTMOND A KORÁBBIAKNAK" << std::endl; break; } } // ==================================================================== // Az input sorok interpretálása. // Ha valamikor hiba volt (pl. az ÉS és VAGY keverése), itt jelezzük bool voltHiba; // -------------------------------------------------------------------- // Szavak egy sorozatának tulajdonsággá konvertálása. A szavak tömbb // elso-edik szavától az utso-adik szaváig Tulajdonsag osszetettTulajdonsag( const std::vector<std::string> &szavak, int elso, int utso ) { Tulajdonsag osszeg; int tipus = 0; // 1 = a tagok VAGY-gyal vannak kapcsolva. // 2 = ÉS-sel. 0 = Még nem tudjuk int i; // A tulajdonságnak legalább egy szóból kell állnia if (elso > utso) { voltHiba=true; return uresHalmaz; } // Sorban megyünk a tagokon i=elso; while (i<=utso) { // Ha ez nem az első tag, relációjelnek kell következnie. if (i>elso) { if (szavak[i]=="VAGY") { // Ha már volt ÉS, az hiba if (tipus == 2) { voltHiba = true; return uresHalmaz; } tipus = 1; } else if (szavak[i]=="ÉS") { // Ha már volt VAGY, az hiba if (tipus == 1) { voltHiba = true; return uresHalmaz; } tipus = 2; } else { voltHiba = true; return uresHalmaz; } // Nem relációjel :-( ++i; // feldolgoztuk a relációjelet } // Ellenőrizzük, a végére értünk-e if (i>utso) { voltHiba=true; return uresHalmaz; } // A következő tag ami csak XXX vagy NEM XXX alakú lehet int tagadjuk=0; if (szavak[i]=="NEM") { tagadjuk=1; ++i; if (i>utso) { voltHiba=true; return uresHalmaz; } } // A tulajdonság neve nem lehet védett szó if ( szavak[i]=="NEM" || szavak[i]=="VAGY" || szavak[i]=="ÉS" || szavak[i]=="HA" || szavak[i]=="AKKOR" || szavak[i]=="VAGY" || szavak[i]=="LÉTEZIK" || szavak[i]=="NINCS" || szavak[i]=="?" ) { voltHiba = true; return uresHalmaz; } // Az új tag kiszámítása és hozzáadása az öüsszeghez Tulajdonsag ujTag = tagadjuk ? - elemiTulajdonsag( szavak[i] ) : elemiTulajdonsag( szavak[i] ); switch (tipus) { case 0: osszeg = ujTag; break; case 1: osszeg = osszeg + ujTag; break; case 2: osszeg = osszeg * ujTag; break; } ++ i; } return osszeg; } // --------------------------------------------------------------------- // Egy teljes sor szavakra tördelése. A kérdőjel önálló szó std::vector<std::string> szavakraTordeles( const std::string &sor ) { std::vector<std::string> eredmeny; std::string ujSzo; int i,n; n = sor.length(); for (i=0; i<n; i++) { char c = toupper( sor[i] ); // A következő karakter, nagybetűvé konvertálva if (!isalpha(c) && c!='?') c = ' '; // Ha nem betű vagy kérdőjel, akkor szóköz if (c=='?') { // Ha kérdőjel, akkor az előző szónak is vége if (ujSzo!="") { eredmeny.push_back( ujSzo ); ujSzo = ""; } eredmeny.push_back( "?" ); } else if (c==' ') { if (ujSzo!="") { eredmeny.push_back( ujSzo ); ujSzo = ""; } } else ujSzo += c; } if (ujSzo!="") eredmeny.push_back( ujSzo ); return eredmeny; } // --------------------------------------------------------------------- // Egy sor feldolgozása, megválaszolása void EgySorFeldolgozasa( const std::string &sor ) { std::vector<std::string> szavak = szavakraTordeles( sor ); int n = szavak.size(); bool kerdes; voltHiba = false; // Üres sorokat nem értünk if (n==0) { std::cout << "NEM ÉRTEM" << std::endl; return; } // Ha az utolsó szó egy kérdőjel, akkor kérdés if (szavak[n-1]!="?") kerdes = false; else { kerdes = true; --n; } if (szavak[0]=="HA") { // Megkeressük az AKKOR szót int k=0; while (k<n && szavak[k]!="AKKOR") ++k; Tulajdonsag A = osszetettTulajdonsag( szavak, 1, k-1 ); // A HA és AKKOR közötti rész Tulajdonsag B = osszetettTulajdonsag( szavak, k+1, n-1 ); // Az AKKOR utáni rész if (voltHiba) std::cout << "NEM ÉRTEM" << std::endl; else HaAkkor( A, B, kerdes ); } else if (szavak[0]=="NINCS") { Tulajdonsag A = osszetettTulajdonsag( szavak, 1, n-1 ); if (voltHiba) std::cout << "NEM ÉRTEM" << std::endl; else Nincs( A, kerdes ); } else if (szavak[0]=="LÉTEZIK") { Tulajdonsag A = osszetettTulajdonsag( szavak, 1, n-1 ); if (voltHiba) std::cout << "NEM ÉRTEM" << std::endl; else Letezik( A, kerdes ); } else // Az első szó valami más... std::cout << "NEM ÉRTEM" << std::endl; } // --------------------------------------------------------------------- int main( int argc, char **argv ) { setlocale( LC_ALL, "hu_HU" ); // Inicializáljuk a teljesHalmaz és a lehetsegesHalmaz változókat int i; for (i=0; i<=ATN; i++) teljesHalmaz.insert( i ); lehetsegesHalmaz = teljesHalmaz; // Végtelen ciklusban olvasunk és értelmezünk while (1) { std::string sor; std::getline( std::cin, sor ); if (sor=="") break; EgySorFeldolgozasa( sor ); } } // ==================================================================== |
A dolgozatok tanulságai
A hibátlanul működő programokra 7 pont járt, a dokumentációra pedig legfeljebb a programra kapott pontszám fele, így gyűlhetett össze a maximális 7+3 pont.
A dokumentáció hiányosságai
Továbbra is nagyon hiányosak a programok dokumentációi. Ennek egyik oka talán az is lehet, hogy az elvárásaink nem elég világosak. Ezért most újra szeretnénk összefoglalni, hogy az S-jelű feladatok esetében egy jó leírás milyen részekből állhat. Mindenekelőtt a legfontosabb cél, hogy a javító vagy akárki más -- akár maga a program írója bizonyos idő elteltével -- könnyen megérthesse a program működését, és akár a programban előforduló hibákat is kijavíthassa.
- Az algoritmus működési elve. Elmagyarázzuk, hogy a program mit csinál, és miért működik. Az algoritmust többnyire érdemes külön fájlban leírni; a dokumentációnak ez a része egyrészt terjedelemesebb, másrészt olyan eszközöket (képletek, ábrák) is tartalmazhat, amiket a program szövegében nehéz elhelyezni.
- Áttekintés a program megvalósításáról. Ebben szerepel, hogy milyen programnyelven használtok, milyen operációs rendszeren és milyen fordítóval fordítottátok, a program milyen fontosabb részekből áll, és a használatához milyen esetleges változtatások szükségesek stb. Ez szerepelhet a forráskód elején is.
- A fontosabb változók és eljárások jelentése. Ez egy fontos összekötő kapocs az algoritmus leírása és a programkód között; elmagyarázza, hogy az adott változó vagy eljárás az algoritmus melyik részét valósítja meg. Ez részben a program áttekintésében, részben a forráskódban érdemes leírni.
- A forráskódban elhelyezett kommentek. Ezek célja a közvetlen forráskód megértése; ha valamelyik részlet értelme nem derülne ki azonnal az olvasó számára, akkor teszünk mellé egy rövid megjegyzést.
A legtöbb dolgozatból teljesen hiányzott az algoritmus és a program áttekintése. A kódban elhelyezett kommentek pedig csak egy-egy részletet próbáltak megmagyarázni, a program globális bemutatása nélkül. Így pedig nagyon nehéz megérteni, hogy a program maga hogyan működik.
Típushibák
Több versenyző nem bontotta az elemi tulajdonságokat atomokra. Emiatt a programjuk nem is működhetett helyesen. Ha a programjuk erre a leegyszerűsített esetre hibátlanul működött volna, 2+1 pontot kaphattak ... volna.
Az ékezetes karakterek kezelésa sajnos nagyon szorosan kapcsolódik az operációs rendszer által használt karakterkódoláshoz, és nagyon nehéz lenne a programot úgy megírni, hogy minden gépen egyformán jól működjön. A kódolásból származó problémákat nem tekintettük hibának, nem vontunk le érte pontot. Azokat a programokat, amiknél az ékezetes betűk kezelése gondot okozott, a forráskód módosításával, ékezetes betűk nélkül teszteltük.
Sajnos többeknél érzékelhető volt, hogy nem hagytak maguknak elegendő időt a feladat megoldására. Leginkább ez az oka a sok 0 pontos dolgozatnak. Pedig egy ilyen összetett feladat esetében a program tesztelésére és dokumentálására is időt kell hagyni.
Letölthető fájlok
C++ forráskód: s11.cpp
Tesztadatok: s11teszt.zip
Kós Géza
Statistics:
13 students sent a solution. 9 points: Grósz Dániel. 6 points: 1 student. 5 points: 1 student. 2 points: 1 student. 0 point: 9 students.
Problems in Information Technology of KöMaL, October 2005