Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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 10\,000 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 M\subsetA, 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