Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 11. feladat (2005. október)

S. 11. A világ dolgait szeretjük különböző tulajdonságok szerint csoportosítani, és a tulajdonságok között összefüggéseket keresni. Írjunk programot, amely tulajdonságok között von le logikai következtetéseket.

A program bemenetének, amit a billentyűzetről (a standard bemenetről) olvas, minden sora egy-egy állítást vagy kérdést tartalmaz; ezekre egy-egy sorban kell válaszolnia a képernyőre (a standard kimenetre).

Az állítások és kérdések különböző tulajdonságokra vonatkoznak. Az elemi tulajdonságok egyetlen szóból állnak, pl. kicsi, piros. A NINCS, LÉTEZIK, ÉS, VAGY, NEM, HA, AKKOR szavak tiltottak, de minden más szót elemi tulajdonságnak tekintünk.

Az elemi tulajdonságok tagadását úgy képezzük, hogy eléjük írjuk, hogy NEM. Például a piros tagadása az, hogy NEM piros.

Az összetett tulajdonságokat úgy képezzük, hogy néhány elemi tulajdonságot vagy elemi tulajdonságok tagadásait összekapcsoljuk az ÉS vagy a VAGY szavakkal, pl. kicsi ÉS NEM piros. A kétféle összekapcsolás kombinálását (pl. nagy ÉS piros VAGY kék) nem engedjük meg.

Háromféle állítást engedünk meg. Ezek szintaxisa:

   LÉTEZIK (tulajdonság)

   NINCS (tulajdonság)

   HA (tulajdonság) AKKOR (tulajdonság)

Kérdést úgy képezünk, hogy egy állítás végére kérdőjelet írunk.

Az állításokra a program a következőket válaszolhatja:

   ÉRTEM ha új információt kapott

   TUDOM ha az állítás következik a korábbiakból \

   EZ ELLENTMOND A KORÁBBIAKNAK (ilyenkor figyelmen kívül hagyja)

   NEM ÉRTEM ha szintaktikusan helytelen az input

Hasonlóan a kérdésekre adható válaszok:

   IGEN, illetve NINCS ha a kérdés igaz állításra vonatkozott

   NEM, illetve DE IGEN ha a kérdés hamis állításra vonatkozott

   NEM TUDOM ha a válasz igaz és hamis is lehet

A program addig fusson, amíg a felhasználó le nem állítja. Feltételezhetjük, hogy az elemi tulajdonságok száma legfeljebb 8, és az input legfeljebb 10000 sorból áll. A kis- és nagybetűket tekintsük azonosnak. Minden olyan karaktert, ami nem betű vagy kérdőjel, tekintsünk a szóközzel azonosnak.

Példa (dőlt betűvel szedtük a számítógép válaszait):

HA kutya VAGY macska VAGY ló AKKOR szőrös ÉS négylábú
ÉRTEM
HA tacskó VAGY foxi AKKOR kutya
ÉRTEM
HA foxi AKKOR négylábú
TUDOM
HA szúnyog AKKOR hatlábú
ÉRTEM
HA tacskó AKKOR szőrös?
IGEN
LÉTEZIK tacskó?
NEM TUDOM
LÉTEZIK tacskó
ÉRTEM
NINCS szőrös ÉS kutya?
DE IGEN
HA négylábú AKKOR NEM hatlábú
ÉRTEM
LÉTEZIK ló ÉS szúnyog?
NEM
NINCS hatlábú ÉS tacskó?
NINCS
LÉTEZIK négylábú VAGY hatlábú ÉS NEM szőrös?
NEM ÉRTEM

Beküldendő a program forráskódja (s11.pas, s11.c, ...)

(10 pont)

A beküldési határidő 2005. november 15-én LEJÁRT.

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

Statisztika:

13 dolgozat érkezett.
9 pontot kapott:Grósz Dániel.
6 pontot kapott:1 versenyző.
5 pontot kapott:1 versenyző.
2 pontot kapott:1 versenyző.
0 pontot kapott:9 versenyző.

A KöMaL 2005. októberi informatika feladatai