Nyolc királynő probléma. Programozás alapjai II. (13. ea) C++ visszalépéses (backtrack) algoritmusok táblás játékok, összefoglalás

Nyolc királynő probléma Programozás alapjai II. (13. ea) C++

• Helyezzünk el nyolc királynőt úgy egy sakktáblán, hogy azok ne üssék egymást! • Egy megoldást keresünk nem keressük az összes lehetséges elhelyezést.

visszalépéses (backtrack) algoritmusok táblás játékok, összefoglalás Szeberényi Imre BME IIT

<[email protected]>

M Ű E GY E T E M 1 7 82 C++ programozási nyelv

© BME-IIT Sz.I.

2016.05.17.

- 1C++ programozási nyelv © BME-IIT Sz.I.

Probálgatás

- 2-

Visszalépés (back track)

• Egy oszlopban csak egy királynő lehet, ezért oszloponként próbálgatunk.

• A 24. lépésben visszalépünk, és levesszük a korábban már elhelyezett királynőt.

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2016.05.17.

- 3-

Visszalépés és újból próba

C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 4-

Visszalépés és újból próba

• A 36. lépésben ismét vissza kell lépni. • A 60. lépés ismét kudarcba fullad.

• Egy lehetséges megoldást a 876. lépésben kapunk.

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 5-


2016.05.17.

- 6-

Hogyan modellezhető ?

Okos tábla metódusai:

• Okos tábla, buta királynő

• • • • •

– A sakktábla ismeri a szabályokat és nyilvántartja a királynők helyzetét. – A királynő lényegében nem csinál semmit.

• Okos királynő, buta tábla – A királynő ismeri a szabályokat és nyilvántartja a saját pozícióját. – A sakktábla nem tud semmit.

Szabad – adott pozícióra lehet-e lépni Lefoglal – adott pozíciót lefoglalja Felszabadít – adott pozíciót felszabadítja Rajzol – kirajzolja a pillanatnyi állást Probal – elhelyezi a királynőket

• Okoskodó tábla, okos királynő C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 7-

Metódus spec. - Szabad


2016.05.17.

- 8-

Metódus spec. - Lefoglal

bool Szabad(int sor, int oszlop);

void Lefoglal(int sor, int oszlop);

– megvizsgálja, hogy az adott helyre lehet-e királynőt tenni. – bemenet:

– Lefoglalja az adott pozíciót. – bemenet: • sor – sor (1..8) • oszlop – oszlop (1..8)

• sor – sor (1..8) • oszlop – oszlop (1..8)

– kimenet: • true – a pozíció szabad • false – ütésben van a királynő


2016.05.17.

- 9-

Metódus spec. - Felszabadit

2016.05.17.

- 10 -

Metódus spec. - Rajzol

void Felszabadit(int sor, int oszlop);

void Rajzol(int sor, int oszlop);

– Felszabadítja az adott pozíciót. – bemenet:

– Kirajzolja a táblát. Az aktuális sor, oszlop pozícióba ? jelet tesz – bemenet:





2016.05.17.

- 11 -


2016.05.17.

- 12 -

Metódus spec. - Probal

Implementáció - Probal bool Probal(int oszlop) { int siker = 0, sor = 1; következő do { oszlopba if (Szabad(sor, oszlop)) { Lefoglal(sor, oszlop) if (oszlop < 8) siker = Probal(oszlop+1); else siker = 1; if (!siker) Felszabadit(sor, oszlop); } sor++; nem sikerült, } while (!siker && sor <= 8); visszalép return(siker); }

bool Probal(int oszlop); – A paraméterként kapott oszlopba és az azt követő oszlopokba megpróbálja elhelyezni a királynőket – bemenet: • oszlop sorszáma (1..8)

– kimenet: • true - ha sikrült a 8. oszlopba is. • false - ha nem sikerült


2016.05.17.

- 13 -


Adatszerkezet (mit kell tárolni?)

2016.05.17.

- 14 -

Átlók tárolása

• Adott sorban van-e királynő

sor - oszlop = állandó

– 8 sor: vektor 1..8 indexszel

• Adott átlóban van-e királynő

1 2 3 4 5 6 7 8

– főátlóval párhuzamos átlók jellemzője, hogy a sor-oszlop = álladó (-7..7-ig 15 db átló) – mellékátlóval párhuzamos átlók jellemzője, hogy a sor+oszlop = álladó (2..16-ig 15 db átló)

sor + oszlop = állandó

12 3 4 5 6 7 8 C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 15 -

Tabla osztály megvalósítása class Tabla { bool sor[8]; bool f_atlo[15]; bool m_atlo[15]; int tab[8]; int probalkozas;

- 16 -

bool Szabad(int s, int o) { return Sor(s) && Fo(s, o) && Mellek(s, o); } void Lefoglal(int s, int o) { Sor(s) = Fo(s, o) = Mellek(s, o) = false; Tab(s) = o; } void Felszabadit(int s, int o) { Sor(s) = Fo(s, o) = Mellek(s, o) = true; Tab(s) = 0; }

// sorok foglaltsága // főátlók (s-o) // mellékátlók (s+o) // kiíráshoz kell // kiíráshoz kell

2016.05.17.

2016.05.17.

Tabla osztály megvalósítása /2

bool& Sor(int i) { return sor[i-1]; } bool& Fo(int s, int o) { return f_atlo[s-o+7]; } bool& Mellek(int s, int o) { return m_atlo[s+o-2]; } int& Tab(int s) { return tab[s-1]; } C++ programozási nyelv © BME-IIT Sz.I.


- 17 -


2016.05.17.

- 18 -

Tabla osztály megvalósítása /3

Tabla osztály megvalósítása /4 bool Tabla::Probal(int oszlop) { int sor = 1; bool siker = false; do { Rajzol(sor, oszlop); if (Szabad(sor, oszlop)) { Lefoglal(sor, oszlop); if (oszlop < 8) siker = Probal(oszlop+1); else siker = true; if (!siker) Felszabadit(sor, oszlop); } sor++; } while (!siker && sor <= 8); return siker; }

public: Tabla(); bool Probal(int oszlop); void Rajzol(int sor, int oszlop); }; Tabla::Tabla() { probalkozas = 0; for (int i = 0; i < 15; i++) { f_atlo[i] = m_atlo[i] = true; if (i < 8) { sor[i] = true; tab[i] = 0; } } } C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 19 -


Működés megfigyelése

void Tabla::Rajzol(int sor, int oszlop) { cout.width(3); cout << ++probalkozas << ".\n"; for (int i = 1; i <= 8; i++) { cout.width(5); cout << 9-i << '|'; for (int j = 1; j <= 8; j++) { if (i == sor && j == oszlop) cout << "?|"; else if (Tab(i) == j) cout << "*|"; else cout << " |"; } cout << endl; } cout << " A B C D E F G H\n\n"; }

kell egy számláló: probalkozas

• Minden próbálkozást kirajzolunk: – * a már elhelyezett királynők helyére – ? a próba helyére – kell tárolni a táblát: tabla változó


2016.05.17.

- 21 -


Főprogram

2016.05.17.

- 22 -

Eredmények

int main() { Tabla t;

60. 8|*| | | | | | | | 7| | | | |*| | | | 6| |*| | | | | | | 5| | | | | |*| | | 4| | |*| | | | | | 3| | | | | | |*| | 2| | | |*| | | | | 1| | | | | | | |?| A B C D E F G H

if (t.Probal(1)) { t.Rajzol(8, 0); // végleges áll. kirajzolása cout << "Siker"; } else cout << "Baj van"; }


- 20 -

Implementáció - kiir

• A minden próbálkozást számolunk: –

2016.05.17.

2016.05.17.

- 23 -


638. 8|*| | | | | | | | 7| | | | | | | | | 6| | | | | | | | | 5| | | | | | | | | 4| |?| | | | | | | 3| | | | | | | | | 2| | | | | | | | | 1| | | | | | | | | A B C D E F G H

2016.05.17.

- 24 -

Eredmények /2

Okos királynő Kiralyno *babu = NULL; for (int i = 1; i <= 8; i++) { babu = new Kiralyno(i, babu); babu->Helyezkedj(); }

876. 8|*| | | | | | | | 7| | | | | | |*| | 6| | | | |*| | | | 5| | | | | | | |*| 4| |*| | | | | | | 3| | | |*| | | | | 2| | | | | |*| | | 1| | |*| | | | | | A B C D E F G H


bool Kiralyno::Helyezkedj() { while (szomszed != NULL && szomszed->Utesben(sor, oszlop)) if (!Lep()) return false; return true; }

2016.05.17.

- 25 -

Okos királynő metódusai:

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?


2016.05.17.

- 26 -

Metódus spec. - Utesben

• Utesben – Ellenőrzi, hogy az adott pozíció ütésben áll-e. • Lep – Előre lép az adott oszlopban, ha nem tud, akkor az oszlop elejére áll és a tőle balra levőt lépteti. • Helyezkedj – Jó helyet keres magának. • Kiír – kiírja a pozícióját.

bool Utesben(int sor, int oszlop); – megvizsgálja, hogy az adott pozíció ütésben álle a saját pozíciójával, ha nem, akkor azonos paraméterekkel meghívja a szomszéd Utesben() tagfüggvényét. – bemenet: • sor – sor (1..8) • oszlop – oszlop (1..8)

– kimenet: • true – a pozíció ütésben áll • false – nincs ütési helyzet


2016.05.17.

- 27 -

Metódus spec. - Lep

2016.05.17.

- 28 -

Metódus spec. - Helyezkedj

void Lep();

void Helyezkedj();

– Előre lép az adott oszlopban, ha nem tud, akkor az oszlop elejére áll és meghívja a tőle balra levőt királynő Lep() tagfüggvényét. – bemenet: – kimenet:

– Megvizsgála a saját pozícióját, hogy megfelelőe. Ha ütésben áll, akkor meghívja Lep() tagfüggvényét. Ha tudott lépni, akkor ismét megvizsgálja a saját pozícióját. – bemenet: – kimenet:

• true – tudott lépni • false – nem tudott lépni



• true – tudott megfelelő helyet találni magának • false – nem tudott megfelelő helyet találni

2016.05.17.

- 29 -


2016.05.17.

- 30 -

Metódus spec. - Kiir

Kiralyno osztály megvalósítása class Kiralyno { int sor; // sor 1-8 int oszlop; // oszlop 1-8 Kiralyno *szomszed; // szomszéd pointere public: Kiralyno(int o, Kiralyno *sz): szomszed(sz), oszlop(o) { sor = 1; } bool Utesben(int s, int o); bool Lep(); bool Helyezkedj(); void Kiir(); };

void Kiir(); – Kiírja a saját és a szomszédok pozícióját.


2016.05.17.

- 31 -

Kiralyno osztály megvalósítása/2

2016.05.17.

- 33 -


2016.05.17.

- 34 -

2016.05.17.

- 36 -

Főprogram

bool Kiralyno::Helyezkedj() { while (szomszed != NULL && szomszed->Utesben(sor, oszlop)) if (!Lep()) return false; return true; } void Kiralyno::Kiir() { if (szomszed != NULL) szomszed->Kiir(); cout << (char)(oszlop-1+'A') << 9-sor << endl; } 2016.05.17.

- 32 -

bool Kiralyno::Lep() { if (sor < 8) { sor++; return true; // tudott lépni } if (szomszed != NULL) { // nem tud, van szomsz. if (!szomszed->Lep()) return false; if (!szomszed->Helyezkedj()) return false; } else { return false; } sor = 1; return true; }



2016.05.17.


bool Kiralyno::Utesben(int s, int o) { int d = oszlop - o; // oszlop differencia if (sor == s || sor + d == s || sor - d == s) return true; else if (szomszed != NULL) // ha van szomszéd return szomszed->Utesben(s, o); // akkor azzal is else return false; }



int main() { Kiralyno *babu = NULL; for (int i = 1; i <= 8; i++) { babu = new Kiralyno(i, babu); babu->Helyezkedj(); } babu->Kiir(); } - 35 -


Megtalálja-e az egér a sajtot?

Egér algoritmusa • Minden cellából először jobbra, majd le, ezután balra és végül fel irányokba indul. • Minden cellában otthagyja a nyomát, azaz azt, hogy onnan merre indult legutoljára. • Csak olyan cellába lép be, ahol nincs "nyom". • Ha már nem tud hova lépni, visszalép.


2016.05.17.

- 37 -



2016.05.17.

2016.05.17.

2016.05.17.

- 38 -


- 39 -





2016.05.17.

- 40 -


- 41 -


2016.05.17.

- 42 -



2016.05.17.


- 43 -


Hogyan modellezhető ?

2016.05.17.

- 44 -

Statikus modell

• Résztvevők, kapcsolatok, tevékenységek – labirintus • • • • •

Labirint

cellákból épül fel a celláknak szomszédai vannak tárolja a rajta álló valamit és annak nyomát megkéri a rajta álló valamit, hogy lépjen kirajzolja az állást

Cella

n, m, poi

szomszéd, nyom,

Lép, Print

Set.., Get..

– egér • irány • néz • lép

Az attribútumok megadása nem teljes, csak vázlatos! A teljes program ill. dokumentáció letölthető a tárgy honlapjáról

– fal • hasonlít az egérhez, de nem lép C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 45 -

Obj metódusai

irány Néz,Lépj,Lép

Eger

Fal

jel, erő

jel, erő

Lép


Lép

2016.05.17.

- 46 -

Eger objektum

class Obj { protected: int ir; // ebbe az irányba tart most public: Obj() :ir(-1) {}; // kezdő irány Obj *Nez(int i, Cella &c, bool b = false); void Lepj(int i, Cella &c, bool b = false); virtual char Jele() = 0; // jel lekérdzése virtual int Ereje() = 0; // erő lekérdezése virtual void Lep(Cella &c); // léptet virtual void operator()(Obj*) {}; // ha "megették" }; C++ programozási nyelv © BME-IIT Sz.I.

Obj

2016.05.17.

class Eger :public Obj { const int ero; const char jel; public: Eger(char j = 'e', int e = 10) :ero(e), jel(j) {} char Jele() { return(jel); } // jele int Ereje() { return(ero); } // ereje void operator()(Obj *p) { // meghívódik, ha megették cout << "Jaj szegeny " << Jele(); cout << " megetvett a(z):"; cout << p->Jele() << " jelu\n"; } }; - 47 -


2016.05.17.

- 48 -

Cella objektum /1

Cella objektum /2

class Cella { int x, y; // geometriai koordináták Cella *sz[4]; // szomszédok, ha NULL, akkor nincs Obj *p; // cella tartalma. URES, ha nincs Lista ny; // lábnyomok listája public: enum irany { J, L, B, F }; // nehéz szépen elérni.. Cella() { SetPos(0, 0); } void SetPos(int i, int j); void SetSz(int n, Cella *cp) { sz[n] = cp; }// szomszéd Cella *GetSz(int n) { return(sz[n]); } ..... C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

...... void SetObj(Obj *a) { p = a;} // objektum beírása Obj *GetObj() { return(p); } // objektum lekérdezése void SetNyom(int n); // lábnyom beírása int GetNyom(const Obj *a); // lábnyom lekérdezése void DelNyom() {ny.Torol(Labnyom(GetObj()));} }

- 49 -

Főprogram (részlet)

2016.05.17.

2016.05.17.

• Végig kell járni a cellákat – meghívni az ott "lakó" objektum léptetését

• Figyelni kell. hogy nehogy duplán léptessünk. (bejárási sorrend elé lépett)

- 51 -


2016.05.17.

Obj::lep() /1

Obj::Lep() /2

if (c.GetNyom(this) < 0) // ha nem volt nyoma, indul c.SetNyom(F+1); // így nem tud visszalépni if (++ir <= F) { // ha van még bejáratlan irány if (Obj *p = Nez(ir, c)) { // ha van szomszéd if (Ereje() > p->Ereje()) { // ha Ő az erősebb (*p)(this); // meghívjuk a függv. operátorát Lepj(ir, c); // rálépünk (eltapossuk) ir = -1; // most léptünk be: kezdő irány } } } else {

// nincs már bejáratlan irány if ((ir = c.GetNyom(this)) > F) { // kezdő nem lép vissza. throw std::logic_error("Kezdo pozicioba jutott"); } else { // visszalépés if (Obj *p = Nez(ir, c, true)) { // lehet, h. van ott valaki if (Ereje() > p->Ereje()) { // Ő az erősebb (*p)(this); // meghívjuk a függv. operátorát Lepj(ir, c, true); // visszalépünk és eltapossuk ir ^= 2; // erre ment be (trükk: a szemben levő irányok csak a 2-es bitben különböznek) }}}}


- 50 -

Labirintus léptetés

Labirint lab(4,5); // 4 * 5 os labirintus Eger e1, e2; // 2 egér; jele: e lab.SetObj(2, 3, e1); // egerek elhelyezése lab.SetObj(1, 4, e2); try { char ch; lab.Print(); // kiírjuk a labirintust while (cin >> noskipws >> ch, ch != 'e') { lab.Lep(); lab.Print(); // léptetés } } catch (exception& e) { cout << e.what() << endl; } C++ programozási nyelv © BME-IIT Sz.I.


2016.05.17.

- 53 -


2016.05.17.

- 52 -

- 54 -

Amőba

Objektum hierachia

• Szereplők: tábla, korongok, játékosok • Kis ismeri a szabályokat? – Tábla? – Korongok?

• Választott megvalósítás:

Table belső osztálya

– Tábla ismeri a korongok helyzetét, szomszédokat – A korongok le tudják kérdezni a szomszédokat – Meg tudják állapítani, ha nyert helyzet van. Ekkor színt váltanak.


2016.05.17.

Position beépíthető lenne a Disc osztályba, de a felelősségek így jobban elvállnak.

- 55 -


Szomszédok és irányok

bool Disc::check(color_type col,int dir,int max) { if (col == color) { if (--max == 0) { setColor(red); return true; } else { Disc *dp = pos.getNext(dir); if (dp && dp->check(col, dir, max)) { setColor(red); return true; } } } return false; }

class Table { std::vector<std::vector > t; static const int MaxDir = 8; struct dir_type { int dx, dy; } dirs[MaxDir]; ... void Disc::checkAll() { Table::neighbors_type nb = pos.getNeighbors(); for(Table::neighbors_type::iterator it= nb.begin(); it != nb.end(); ++it) { if ((it->second)->check(color, it->first)) setColor(red); } } 2016.05.17.

- 56 -

Sor ellenőrzése egyik irányban

typedef std::map neighbors_type;


2016.05.17.

- 57 -


2016.05.17.

- 58 -

Objektum • OBJEKTUM: konkrét adat és a rajta végezhető műveletek megtestesítője

Programozás alapjai II. (13. ea) C++

• • • • •

Év végi összefoglalás Szeberényi Imre BME IIT

<[email protected]>

M Ű E GY E T E M 1 7 82 C++ programozási nyelv

© BME-IIT Sz.I.

2016.05.17.

egyedileg azonosítható viselkedéssel és állapottal jellemezhető felelőssége és jogköre van képes kommunikálni más objektumokkal a belső adatszerkezet, és a műveleteket megvalósító algoritmus rejtve marad • könnyen módosítható • újrafelhasználható • általánosítható

- 59 C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 60 -

Class

OO paradigmák • egységbezárás (encapsulation)

• Objektum osztály ≡ objektum fajta, típus (viselkedési osztály) • Osztály ≠ Objektum • Objektum ≡ Egy viselkedési osztály egy konkrét példánya.

– osztályok (adatszerkezet, műveletek összekapcsolása)

• többarcúság (polymorphism) – műveletek paraméter függőek, tárgy függőek (kötés)

osztály

• példányosítás (instantiation) • öröklés (inheritance) • generikus adatszerkezet alapú megoldások C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

Komplex k1, k2, k3; objektumok - 61 -


Létrehozás, megsemmisítés, értékadás • Konstruktor

KONSTRUKTOR: Definíció és inicializálás összevonása. DESTRUKTOR: Az objektum megszüntetése.

// létrehozás

class Komplex { double re, im; ez az alapértelmezés public: Komplex() { } // konstruktornak nincs típusa Komplex(double r, double i) { re = r; im = i; } ~Komplex() {} // destruktornak nincs paramétere ... }; ideiglenes objektum Komplex k1; Komplex k2 = k1; // másoló (copy) konstruktorral Komplex k3 = Komplex(1.2, 3.4);

// megsemmisítés

– automatikusan létrejön: meghívja az adattagok és ősök destruktorát

• operator=(const X&) // értékadó operátor

automatikusan létrejön: meghívja az adattagok és ősök értékadó operátorát, ha objektum, egyébként bitenként másol.


2016.05.17.

- 63 -


• A kezdeti értékadáskor még inicializálatlan a változó (nem létezik), ezért nem lehet a másolással azonos módon kezelni. • Mikor hívódik a másoló konstruktor?

2016.05.17.

- 64 -

• Megszünteti a saját részt: – – – –

inicializáláskor (azonos típussal inicializálunk) függvény paraméterének átadásakor függvény visszatérési értékének átvételekor ideiglenes változók összetett kifejezésekben kivétel dobásakor


2016.05.17.

Destruktor feladatai

Inicializálás miért más mint az értékadás?

– – – – –

- 62 -

Konstruktor és destruktor

– default: X() // nincs paramétere automatikusan létrejön, ha nincs másik konst. – másoló: X(const X&) // referencia paramétere van, automatikusan létrejön: meghívja az adattagok és ősök másoló konst.-rát, ha obj. egyébként bitenként másol.

• Destruktor

2016.05.17.

végrehajtja a programozott törzset tartalmazott objektumok destruktorainak hívása virtuális függvénymutatók visszaállítása virtuális alaposztály mutatóinak visszaállítása

• Hívja a közvetlen, nem virtuális alaposztályok destruktorait. • Öröklési lánc végén hívja a virtuális alaposztályok destruktorait. - 65 -


2016.05.17.

- 66 -

Statikus tag

Statikus tagfüggvény

• Az osztályban statikusan deklarált tag nem példányosodik. • Pontosan egy példány létezik, amit explicit módon definiálni kell (létre kell hozni). • Minden objektum ugyanazt a tagot éri el. • Nem szükséges objetummal hivatkozni rá.

• Csak egy példányban létezik. • Statikus tagfüggvény nem éri el az objektumpéldányok nem statikus adattagjait. class A { int a; Nem éri el! public: static void f() { cout << a;} };

pl: String::SetUcase(true);

• Statikus tagként az osztály tartalmazhatja önmagát. • Felhasználás: globális változók elrejtése C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 67 -


Alapértelmezett tagfüggvények – default: X() // nincs paramétere – másoló: X(const X&) // referencia paraméter

• Destruktor • operator=(const X&) // értékadó • operator&() // címképző • operator,(const X&) // vessző A konstruktor/destruktor és az értékadó operátor alapértelmezés szerint meghívja az adattagok és ősök megfelelő tagfüggvényét. Ha azonban saját függvényünk van, akkor abban csak az történik, amit beleírtunk. Kivéve a konstruktor/destruktor alapfunkcióit (default létrehozás, megsemmisítés.) 2016.05.17.

- 68 -

Operátorok kiértékelése

• Konstruktor


2016.05.17.

- 69 -

• ha a bal oldal osztály, akkor meg kell vizsgálni, hogy van-e megfelelő alakú tagfüggvény • ha nincs, vagy beépített típus, de a jobb oldal osztály, akkor • meg kell vizsgálni, hogy van-e megfelelő alakú globális függvény Mikor kell globális függvény? – ha a bal oldal nem osztály (pl. 2 + X ) – vagy nincs a kezünkben (pl. cout << X)


2016.05.17.

- 70 -

Védelem összefoglalása

A védelem enyhítése: friend class Komplex { double re, im; public: ..... Komplex operator+(const Komplex& k) { Komplex sum(k.re + re, k.im + im); return(sum); } Komplex operator+(const double r) { return(operator+(Komplex(r))); } friend ostream& operator<<(ostream& s, const Komplex& k); }; ostream& operator<<(ostream& s, const Komplex& k) } s << k.re << ',' << k.im << 'j'; return(s); }

public:

külső

származtatott

tagfüggvény és barát

√

√

√

√

√

protected: private:

√

Így láncolható cout << k1 << k2; C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 71 -


2016.05.17.

- 72 -

Öröklés

Kompatibilitás/2

• Az öröklés olyan implementációs és modellezési eszköz, amelyik lehetővé teszi, hogy egy osztályból olyan újabb osztályokat származtassunk, melyek rendelkeznek az eredeti osztályban már definiált tulajdonságokkal, szerkezettel és viselkedéssel. • Újrafelhasználhatóság szinonimája. • Nem csak bővíthető, hanem a tagfüggvények át is definiálhatók. C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 73 -

Generikus osztályok és függv.

veréb

kutya

ponty

bálna

A típusú objektum kompatibils B-vel, ha A típusú objektum bárhol és bármikor alkalmazható, ahol B használata megengedett. (pl: kutya kompatibilis az emlőssel) C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 74 -

Array i10; Array<double, 5> d5; Array cp20;

template void rendez (T a[], int n) { for (int i = 1; i < n; i++) { T tmp = a[i]; int j = i-1; while (j >= 0 && a[j] > tmp) { a[j+1] = a[j]; j--; } int t[100]; a[j+1] = tmp; } rendez(t, 100); }

- 75 -

Predikátumok


2016.05.17.

- 76 -

Predikátumok /2 Template paraméterként átadott predikátumok.

• Az algoritmusok tovább általánosíthatók ún. predikátumokkal. • Ezek a logikai függvények, vagy függvényobjektumok befolyásolják az algoritmust működését.

template bool hasonlitFv(T a, T b) { return a > b; } template<> bool hasonlitFv(char* a, char* b) { // specializáció return strcmp(a, b) >= 1; }

template void rendez (T a[], int n) { for (int i = 1; i < n; i++) { T tmp = a[i]; int j = i-1; while (j >= 0 && Has(a[j], tmp)) { a[j+1] = a[j]; j--; } a[j+1] = tmp; } } int t[100]; rendez(t, 100); C++ programozási nyelv © BME-IIT Sz.I.

galamb

vízi

emlős

template class Array { T t[s]; public: T& operator[](int i); };

– Típust paraméterként adhatunk meg. – A generikus osztály v. függvény később a típusnak megfelelően példányosítható. – A specializáció során a sablonból az általánostól eltérő példány hozható létre. – A függvényparaméterekből a konkrét sablonpéldány levezethető. – Függvénysablon átdefiniálható. 2016.05.17.

madár

általánosítás

Generikus osztályok és függv. /2

• Generikus osztályokkal és függvényekkel általános szerkezetekhez jutunk:


állat

specializáció

int t[6] = { 1, 2, -8, 0, 12, 3 }; rendez >(t, 6); char *txt[] = { "szilva", "alma", "korte" }; rendez >(txt, 3);

2016.05.17.

- 77 -


2016.05.17.

- 78 -

Predikátumok /3

Bejárók

Függvényparaméterként átadott predikátumok:

• Tárolók -> adatsorozatok tárolása

template ilyen fv. poi T kivalaszt(T a[], int n, S cmp) { T tmp = a[0]; for (int i = 1; i < n; i++) if (cmp(a[i], tmp)) tmp = a[i]; return tmp; } template bool hasonlitFv(T a, T b) { return a > b; }

• Iterátor: általánosított adatsorozat elemeire hivatkozó elvont mutatóobjektum. • Legfontosabb műveletei:

– adatsorozat elemeit el kell érni – tipikus művelet: "add a következőt"

– – – – –

int t[6] = { 1, 2, -8, 0, 12, 3 }; kivalaszt(t, 6, HasonlitFv); kivalaszt(t, 6, hasonlitFv);//„kitalálja” templ. par.


2016.05.17.

- 79 -

Bejárók /2 • • • • •

éppen akt. elem elérése (* ->) következő elemre lépés (++) mutatók összehasonlítása ( ==, != ) mutatóobjektum létrehozása az első elemre ( begin() ) mutatóobjektum létrehozása az utolsó utáni elemre ( end() )


Kivétel2

Kritikus műveletek

template void PrintFv(Iter first, Iter last){ while (first != last) cout << *first++ << endl; } int tarolo[5] = { 1, 2, 3, 4, 5 }; PrintFv(tarolo, tarolo+5); Array<double, 10> d10; PrintFv<>(d10.begin(), d10.end()); 2016.05.17.

- 81 -


2016.05.17.

- 82 -

Kivételkezelés/3 • Célszerű kivétel osztályokat alkalmazni, (pl. std::exceptions) amiből származtatással újabb kivételeket lehet létrehozni. • A dobás értékparamétert dob, ezért az elkapáskor számolni kell az alaposztályra történő konverzióval (adatvesztés). Célszerű pointert, vagy referenciát alkalmazni. Kell másoló konstruktor.

• A dobott kivétel alap ill. származtatott objektum is lehet. try { throw E(); } catch(H) { // mikor jut ide ? } H és E azonos típusú, H bázisosztálya E-nek, H és E mutató és teljesül rájuk 1. vagy 2., H és E referencia és teljesül rájuk 1. vagy 2.


Kivétel1

További műv.

Kivételkezelés/2

1. 2. 3. 4.

- 80 -

Kivételkezelés = globális goto

Nem kell ismerni a tároló belső adatszerkezetét. Tároló könnyen változtatható. Generikus algoritmusok fel tudják használni. Indexelés nem mindig alkalmazható, de iterátor.. A pointer az iterátor egy speciáis fajtája.


2016.05.17.

2016.05.17.

- 83 -


2016.05.17.

- 84 -

Szabványos kivételek (stdexcept) bad_alloc bad_cast bad_typeid bad_exception ios_base::failure range_error overflow_error undeflow_error lenght_error domain_error out_of_range invalid_argument

Szabványos kivételek/2 class exeption { ... Aut. típuskonverzió letiltása public: exception() throw(); exception(const exception&) throw(); execption& operator=(const exception&) throw(); virtual ~exception() throw(); virtual const char *what() const throw(); }; class runtime_error : public exception { public: explicit runtime_error(const string& what_arg); }; class logic_error : public exception { public: explicit logic_error(const string& what_arg ); };

exception

runtime_error

logic_error


2016.05.17.

- 85 -


Szabványos kivételek/3

Általános célú, újrafelhasználható elemek: – – – – – –

..... } catch (exception& e) { cout << "exeptionból származik" cout << e.what() << endl; } catch (...) { cout << "Ez valami más\n"; }

tárolók, majdnem tárolók algoritmusok függvények bejárók memóriakezelők adatfolyamok

http://www.sgi.com/tech/stl/ http://www.cppreference.com/cppstl.html http://www.cplusplus.com/reference/stl/ 2016.05.17.

- 87 -


Tárolók (konténerek) • • • • • •

vector i1(10, -3); vector<double> d1(100); i1[8] = 12; i1.at(9) = 13; for (vector<double>::size_type i = 0; i < d1.size(); i++) d1[i] = 3.14; for (vector::iterator i = i1.begin(); i < i1.end(); i++) cout << *i << endl; 2016.05.17.

2016.05.17.

- 88 -

2016.05.17.

- 90 -

Szabványos tárolók

• Tetszőleges adatok tárolására • Sorban, vagy tetszőleges sorrendben érhetők el az adatok. • Tipizált felületek


- 86 -

Szabványos könyvtár (STL)

• A standard könyvtár nem bővíti az exception osztály függvényeit, csak megfelelően átdefiniálja azokat. • A felhasználói programnak nem kötelessége az exceptionből származtatni, de célszerű. referencia try {


2016.05.17.

- 89 -

vector list deque stack queue priority_queue


• • • •

map multimap set multiset

• • • •

string array valarray bitset

STL tárolók összefoglalása

STL tárolók összefoglalása /2

• A tárolók nem csak tárolják, hanem "birtokolják is az elemeket"

• • • • • • • •

– elemek létrehozása/megszüntetése

• Két fajta STL tároló van: • Sorozat tárolók (vector, list, deque) – A programozó határozza meg a sorrendet:

• Asszociatív tárolók (set, multiset, map, multimap) – A tároló határozza meg a tárolt sorrendet – Ez elemek egy kulccsal érhetők el. C++ programozási nyelv © BME-IIT Sz.I.

- 91 -

2016.05.17.


Tárolók fontosabb műveletei

Iterá- s Konstr. to- i destr. ro z op= k e

m a x _ s i z e

e m p t y

r e s i z e

fr o n t

b a c k

a s s o i p a g [] t n

i n s e rt

e r a s e

s w a p

c l e a r

p u s h _ fr o n t

p o p _ fr o n t

p u s h _ b a c k

p o p _ b a c k

+

+

+ + + + + + + + + + + + +

deque

+

+

+ + + + + + + + + + + + + + + + +

list

+

+

+ + + + + +

+

+

+ + +

multiset

+

+

+ + +

map

+

+

+ + +

multimap

+

+

+ + +

+ +

+ + + + + + + + + + + + +

- 92 -

• • • • • • •

Nem módosító sorozatműveletek Sorozatmódosító műveletek Rendezés, rendezett sorozatok műveletei Halmazműveletek Kupacműveletek Mimimum, maximum Permutációk

+ + + + +

+ + + + + + + +


2016.05.17.

- 93 -


• unary_function, binary_function

• • • • • • • •

template struct unary_function { typedef Arg argument_type; typedef Result result_type; }; struct Valami : public uanry_function { .......... }; .......... Valami::argument_type ........ Valami::result_type ........ ..... 2016.05.17.

2016.05.17.

- 94 -

Predikátumok és aritm. műv.

Függvényobjektumok


2016.05.17.

Algoritmusok

vector

set

vector list deque map set stack queue priority_queue

- 95 -

equal_to, not_equal_to, greater, less, greater_equal, less_equal logical_and, logical_or logical_not


• • • • • •

plus minus multiplies divides modulus negate

2016.05.17.

- 96 -

Lekötők, átalakítók, típusok • bind2nd() • bind1st()

• binder1st • binder2nd

• mem_fun() • mem_fun_ref() • prt_fun()

• • • •

• not1() • not2()

Nem csak C++-t tanultunk! • OO tervezés – dolgok szereplők számbavétele – viselkedésük modellezése – újrafelhasználhatóság, generikusság

mem_fun1_ref_t mem_fun1_t mem_fun_ref_t mem_fun_t

• • • •

• unary_negate • binary_negate


2016.05.17.

- 97 -

Modellezési példa 1.

OO modell leírása Fejlesztő környezet Dokumentálás pici UNIX


2016.05.17.

- 98 -

Terv: elvi kapcsolati szint

• Modellezzük hallgatók, tantárgyak, feleletek kapcsolatát: – Hallgatók tárgyakat vehetnek fel – Tárgyakhoz számonkérések tartoznak – Számonkérések eredményét tárolni kell

• • • •

Mik az olbjektumok (szereplők) Ki miért felel? Ki mihez férhet hozzá? Ki milyen interfészt ad?


2016.05.17.

- 99 -

Megvalósítási szint

2016.05.17.

- 100 -

Modell: heterogén koll. • Óceán olyan alapobjektumra mutató pointert tárol mely objektumból származtatható hal, cápa, stb. • Óceán ciklikusan bejárja a tárolót és a pointerek segítségével minden objektumra meghív egy metódust, ami a viselkedést szimulálja. • Minden ciklus végén kirajzolja az új populációt.

Kik a szereplők? Ki miért felel? Mihez férhet hozzá? Milyen interfészt ad? C++ programozási nyelv © BME-IIT Sz.I.


2016.05.17.

- 101 -


2016.05.17.

- 102 -

Statikus modell

Modellezési példa kieg. • Egészítsük ki a korábbi modellünket:

Obj

Ocean

– Az állatvédők tudni akarják, hogy mekkora utat tesz meg élete során Cápeti, a cápa. – A tengerbiológusok tudni akarják, hogy hányszor szaporodik Cápeti. – A dokumentum film készül Cápeti útjáról.

cellak[n][m] lep

lep

Hal

Capa

kor

kor nemEvett

lep

lep

• Kérdések: – Tegyünk 3 jeladót Cápeti nyakába? – 1 jeladó jelezzen mindenkinek?


2016.05.17.

- 103 -

Observer terv. minta Observer -subjPtr

ConcreteObs1

-obsPtr[] +attach() +detach() +notify()

ConcreteSubj +update( )


2016.05.17.

- 105 -

WhereAmI 47 19


2016.05.17.

- 106 -

UNIX-szal kezdtük a félévet • Néhány gondolat a UNIX-os fejlesztőeszközökről befejezésül: • Számtalan eszköz, többek által ma már elavultnak tekintett, ugyanakkor hatékony, egységes parancssoros felülettel. • Kiemelt a szövegfeldolgozás/elemzés hatékony támogatása. • Egyre több next, next, next, finish program, a PC-s változatokban, ami nem mindig jelent előnyt.

!!!!!!!!!!! !!! !!! !!!!!!! ! !!!!!!!!!!!!!!!!! !!!!! ! ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!!!!! !!!! ! !! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!! !!!"!!! !!!!!!!!!!!!!!!!! !! ! !!!!!!!!! !! ! !!!!!!!!!!!!!!!!!!!! ! ! !!!! ! !!!!!!!!!!!!!!!!!!!!!!!!!! !!!!! !!!!!!!!!!!!! !!! !!! ! !!!!! !!!!!!!!!! ! !! ! !!!!!!!! !!!!! !! !!!!!! !!!! ! !!!!! !!!! !! !!!!!!!! !! !! !! ! !


- 104 -

main(l ,a,n,d)char**a;{ for(d=atoi(a[1])/10*80atoi(a[2])/5-596;n="@NKA\ CLCCGZAAQBEAADAFaISADJABBA^\ SNLGAQABDAXIMBAACTBATAHDBAN\ ZcEMMCCCCAAhEIJFAEAAABAfHJE\ TBdFLDAANEfDNBPHdBcBBBEA_AL\ H E L L O, W O R L D! " [l++-3];)for(;n-->64;) putchar(!d+++33^ l&1);}

ConcreteObs2

+update( )

2016.05.17.

A forma is fontos !

Subject

+update( )


2016.05.17.

- 107 -


2016.05.17.

- 108 -

Fejlesztést segítő eszközök • • • • • • • •

lex (csak gondolatébresztőként)

make sccs, rcs, cvs, svn, git prof lex (flex) yacc (bison) awk perl .............


• Lexikai analizátor generátor • Reguláris kifejezésekkel megadott lexikai elemek felismeréséhez C programot generál. • Önállóan is felhasználható (–ll), de legtöbbször beépítik egy másik programba.

2016.05.17.

- 109 -

• Compiler generáló eszköz környezetfüggetlen nyelvhez. • A nyelvtani szabályokból előállítja a nyelvtant felismerő C programot. • Önállóan is használható (-ly), de legtöbbször beépítik másik programba.

2016.05.17.

2016.05.17.

- 110 -

Péda: római számok konverziója

yacc (csak gondolatébresztőként)



- 111 -

romailex.l

%token RDIG %{ int last = 0; %} %% list: | list '\n' | list number '\n' { printf("-> %d\n", $2); last = 0; } | list error '\n' { yyerrok; }; number: RDIG { last = $$=$1; } | RDIG number { if ($1 >= last) $$ = $2 + (last=$1); else $$ = $2 - (last=$1); }; C++ programozási nyelv © BME-IIT Sz.I.

2016.05.17.

- 112 -

Köszönöm a figyelmet

%} extern int yylval; %} %% I { yylval= 1; return RDIG; } V { yylval= 5; return RDIG; } X { yylval= 10; return RDIG; } L { yylval= 50; return RDIG; } C { yylval= 100; return RDIG; } D { yylval= 500; return RDIG; } M { yylval=1000; return RDIG; } [^IVXLCDM] { return(yytext[0]); }


2016.05.17.

- 113 -


2016.05.17.

- 114 -

Nyolc királynő probléma. Programozás alapjai II. (13. ea) C++ visszalépéses (backtrack) algoritmusok táblás játékok, összefoglalás

Recommend Documents