Számítógépes implementációk 2., 2006 tavasz, C++ rész

Eredmények

A mindenkori feldolgozásnak megfelelő eredmények elérhetők ezen a linken.

Újdonságok

Órák

1. kurzus: Péntek 8:30-10:00, H57
2. kurzus: Péntek 10:15-11:45, H57
(csak az egyikre kell járni)

Követelmény

Emacs

Az emacsban alapértelmezés szerint nem úgy mûködik a delete gomb, mint azt megszokhattátok. Ennek kijavítására rakjátok be az alábbi három sort a ~/.emacs fájlba:
;; Make [Delete] work the way you expect
(cond (window-system
  (define-key function-key-map [delete] "\C-d")))

Dokumentációk

Az Interneten található rengeteg segédanyag és formális dokumentáció a felhasznált függvénykönyvtárakhoz.
Az eddig két legfontosabbé a következő módon:

Anyag

8. óra (2006.04.07.)

Két rövid programot írunk meg.

1. A wc parancs (word count)

Feladat: Számoljuk meg, hogy a standard bemeneten hány karakter, hány szó és hány sor érkezik!
Megjegyzés: Szónak nevezzük a maximális, angol abc szerinti kis és nagybetűből álló részsorozatot. Egy fájlban eggyel több sor van mint ahány sortörés karakter.
mintamegoldás

9. óra (2006.04.14.)

2. A tr parancs (translate characters)

Feladat: A bemeneten érkező bizonyos karakterek kicserélése más karakterekre. Azt, hogy milyen karaktereket kell cserélni és mire, a parancssori argumentumok határozzák meg. Két argumentumot várjon a program a parancssorból. Az első argumentum azon karaktereket tartalmazza amelyeket ki akarunk cserélni, a második argumentum pedig amire akarjuk őket cserélni. A két argumentumnak ugyanolyan hosszúnak kell lennie.
Példa:
./tr ab cd
hatására az 'a' betűket 'c'-re kell cserélni, a 'b' betűket 'd'-re.
./tr xyz uvw
hatására az 'x' betűket 'u'-re kell cserélni, az 'y' betűket 'v'-re, a 'z' betűket 'w'-re.
Megjegyzés: Miközben teszteled a programodat ügyelj arra, hogy mindig a ./tr formában indítsd el, mert ha kifelejted a ./-t a hívás elejéről, akkor a gyári tr parancsot indítod, ami jól működik :)
mintamegoldás

3. A subst parancs (word substitution)

Feladat: A bemeneten érkező bizonyos szavakat (karaktersorozatokat) kicserélni már karaktersorozatokra. A keresendő és a kicserélendő karakterláncokat a program parancssori argumentumaiban kell megadni.
Példa:
./subst alma korte
Az "almafa" bemenetet "kortefa" kimenetté változtatja.
Megjegyzés: Ezt a feladatot nagyon nehéz úgy karakterről-karakterre beolvasva megoldani, mint a korábbiakat. Ezért érdemes beolvasni egy teljes sort a bemenetről, átalakítani, és közben/utána kiírni a kimenetre. Ehhez a cin.getline() függvényt lehet használni.

10. óra (2006.04.21.)

4. A sort parancs

Feladat: A bemeneten olvasott sorokat lexikografikus sorrendben (ábécérendben) kiírni. Egy sor legfeljebb 256 karakter hosszú lehet.
Megjegyzés: először egy olyan változatot írj meg, ami legfeljebb 100 sor esetén működik. (Deklarálj egy char sorok[100][256]; kétdimenziós tömböt.) Ha ez kész és jó, akkor írj egy olyat ami tetszőlegesen sok sor esetén is működik. Ehhez a következő segítséget érdemes igénybe venni:
typedef struct sor_t {
    char betuk[256];
    sor_t *next;
} sor_t;  //ezt a deklarációt függvényeken kívülre kell tenni

...
    //és így kell majd használni
    sor_t* ujsor = new sor_t;
    cin.getline(ujsor->betuk,256);

...

    delete ujsor;


azaz egy új sor_t típusú objektumot lehet allokálni a new sor_t paranccsal, amelyet a programból való kilépés előtt vissza kell csinálni, tehát a memóriaterületet fel kell szabadítani, és ehhez a delete mutató parancsot kell használni, ahol mutató egy new-val allokált sor_t * típusú érték. Egy struktúra (vagy osztály) típusú mutató egy elemére a -> operátorral lehet hivatkozni: mutató->tag  Ez ekvivalens a (*mutató).tag formával, mivel egy struktúra vagy osztály (pl. sor_t) típusú v változó egy tagjára v.tag módon lehet hivatkozni.
Innen már csak azt kell észrevenni hogy a sor_t struktúra next tagja tud egy újabb sor_t-re mutatni, annak a next-je egy továbbira, stb... A láncot tradícionálisan a NULL értékkel zárjuk le (a NULL 0-át jelent csak látványosabb).

mintamegoldás a kicsire (csak akkor nézzétek meg, ha már a sajátotok kész van és működik!)

A függvénykönyvtárak hatékonyságának demonstrálására készítettem egy olyan megoldást, ami tetszőleges méretű fájlra működik és látványosan rövid. Ezt azonban zárthelyin nem fogadom el. klikk ide
mintamegoldás a nagyra
masik mintamegoldás a nagyra

11. óra (2006.04.28.)

5. feladat: Szigetek

Feladat: Kaptunk egy térképet az Indonéz szigetvilág egy részéről. Határozzuk meg, hogy a térképen hány sziget található!

A bemeneti fájl egy négyzetrács minden pontjára megmondja hogy az víz alatt van-e vagy szárazföld. Két élben szomszédos szárazföld egyazon sziget része.

A bementi fájl első sorában két szám található: n m, ahol a négyzetrácsnak n sora és m oszlopa van. Tudjuk, hogy 1<=n<=100 és 1<=m<=100. A következő n sor mindegyike m karaktert tartalmaz, a térkép megfelelő pozícióját. Ez a karakter '.' (pont) ha a megfelelő pozíción víz található, 'X' (nagy X betű), ha szárazföld. A térkép fájl által leírt része körül minden irányban az óceán található.

A kimenetre egyetlen számot kell írni, a szigetek számát.

A feladat megoldásánál feltehető, hogy a bemeneti fájl pontosan a specifikációnak megfelelő, tehát nem kell ellenőrizni.

Példa:
5 6
. . . . . .
. X . . X X
X . . . X .
X . X . X X
. X X . . .

Kimenet:
4

Mintamegoldás

12. óra (2006.05.05.)

6. feladat: Repülő

Kaptunk egy térképet Európa repülőjáratairól. Egy repülőjárat két várost köt össze, leszállás nélkül. Szeretnénk eljutni egy adott városból egy másik adott városba a lehető legkevesebb átszállással. Számítsuk ki, hogy
a) minimálisan hány átszállás szükséges ehhez
b) milyen útvonalon lehet eljutni ennyi átszállással.

A bementi fájl első sorában négy egész szám található: N M A B, szóközzel elválasztva. N a városok számát adja meg (1<=N<=1000), M a repülőjáratok számát, A a kezdeti város sorszámát (1<=A<=N), B pedig a célváros sorszámát (1<=B<=N). A következő M sor mindegyikében két egész szám található, X Y, ami azt jelenti, hogy az X és Y városok (1<=X,Y<=N) között van kétirányú repülőjárat.

A kimenet első sorába a minimális átszállások k számát kell írni. A második sorba pedig k+2 egész számot, az útvonalra eső városok sorszám
ait. A második sorban bármely két szomszédes szám között kell lennie repülőjáratnak, az első szám A kell legyen, az utolsó szám pedig B.
Ha a célváros nem érhető el a kiindulási városból, akkor a kimenet első és egyetlen sorába a -1 számot kell írni.

Példa:
5 4 1 5        <--5 város, 4 járat, 1-ből az 5-be kell eljutni.
1 3
2 5
3 4
2 3

Kimenet:
2
1 3 2 5

13. óra (2006.05.12.)

7. feladat: repülõ - pénzért

Most is megkaptuk a repülõjáratok listáját, de most azt is tudjuk, hogy egy járaton való utazásért mennyit kell fizetnünk. A-ból B-be szeretnénk eljutni a lehetõ legolcsóbban.
A bemeneti fájl nagyrészt azonos a fenti feladattal, csak most az éleket leíró sorokban van egy harmadik szám, az él költsége. A költség 0 és 10000 közötti egész szám.
A kimenet elsõ sorába most a minimális összköltséget kell írni, vagy a NINCS szót ha nincs út A-ból B-be.
Példa:
5 6 1 5
1 2 3
5 3 9
4 3 13
2 3 22
1 4 7
5 4 1

Kimenet:
8
1 4 5

13. óra (2006.05.12.)

Zárthelyi: Mérő

   Van két kannánk, az első űrtartalma A liter, a másodiké B liter. Ki kell mérnünk N liter vizet a második kannába. Kezdetben mindkét kanna üres. A kannákkal a következő műveleteket végezhetjük:
      TA az első kannát teletöltjük a csapról,
      TB a második kannát teletöltjük a csapról,
      UA az első kannát kiürítjük,
      UB az második kannát kiürítjük,
      AB az első kannából áttöltjük a benne lévő vizet a második kannába úgy, hogy ha mind belefér,
akkor mind áttöltjük, egyébként annyit töltünk át, hogy a második kanna tele legyen,
      BA a második kannából áttöltjük a benne lévő vizet az első kannába úgy, hogy ha mind belefér,
akkor mind áttöltjük, egyébként annyit töltünk át, hogy az első kanna tele legyen.
   Írj programot, amely a két kanna űrtartalma és az előállítandó N mennyiség ismeretében meghatározza a legrövidebb olyan műveletsort, amelyet sorban végrehajtva a második kannában N liter víz lesz!
   A standard bemeneten a három egész szám érkezik N A B sorrendben, egy szóközzel elválasztva. Az előállítandó N a vízmennyiség (1<=N<=20), A és B az első és második kanna űrtartalma (1<=A,B<=20).
   A standard kimenetre a megoldás műveletsorát (soronként egy-egy műveletet) kell írni. Ha nincs megoldás, akkor az első és egyetlen sor a NINCS szöveg legyen.
   Legfeljebb hármas jegyért nem a legrövidebb, hanem tetszőleges helyes műveletsort kiíró programot is elfogadunk.

   Példa:
   2 3 7

   Kimenet:
   TA
   AB
   TA
   AB
   TA
   AB
   UB
   AB

Megoldás:
A három tanult algoritmus (komponensek számának meghatározása mélységi bejárással, szélességi bejárás legrövidebb utak keresésére, és Dijkstra algoritmusa  súlyozott gráfban való legrövidebb utak keresésére) közül kellett kiválasztani azt, amelyik alkalmazható a feladatra. Ez a legrövidebb utak keresése, súlyozatlan gráfban.
Definiálni kell a gráfot. A csúcspontok legyenek a rendszer állapotai, azaz hogy melyik kannában mennyi víz van. Ez összesen legfeljebb 21*21 állapot. Egy állapotból irányított él vezet egy mésikba, ha egy művelettel el lehet jutni bele. A műveletet érdemes címkeként ráírni az élre.
Az öntögetés megoldható akkor és csak akkor, ha van irányított út a (0,0) állapotból valamely i-re az (i,N) állapotba. Ekkor a legrövidebb útnak megfelelő öntögetési címkék pont a kívánt kimenetet adják.
Tehát két részfeladat van: 1. megkonstruálni a gráfot (például adjacencialistás reprezentációban), majd 2. lefuttatni rá a tanult szélessségi keresés algoritmust. A két részt össze is lehet vonni, mert a gráfot menet közben is elő lehet állítani, hiszen bármelyik csúcsból a hat művelet szimulálásával meg tudjuk mondani, hogy mely másik csúcsokba lehet eljutni élen. És pont erre van szükség a szélességi keresés belső ciklusában.
Mintamegoldás.