Tipp: a diák között lépkedni a J és K billentyúkkel lehet. Szöveges kereséshez ctrl-F használható.
Letöltés
Programozás alapjai II.
(11. ea) C++
Adapter és observer terv minta,
backtrack algoritmusok
Szeberényi Imre, Somogyi Péter
BME IIT
<szebi@iit.bme.hu>
MŰE GYET E M 1 782
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
-1 -
Előző óra összefoglalása
• STL
– szabványos kivételek
– tárolók
– algoritmusok
• Egyszerű példák STL-lel
– eseményvezérelt program
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
-2 -
Ma
• Adapter tervezési minta (ism.)
• Korábbi példa továbbfejlesztése
– STL tároló használata
– STL iterátor használata
– Egy tipikus viselkedési minta és megvalósítása
• Observer
• Visszalépéses algoritmusok (backtrack)
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
-3 -
std::vektor
labor::Array
• labor::Array (9. labor, /gen_array_iter3/):
–
–
–
–
–
–
–
fix méretű (maxsize)
van aktuális mérete (siz)
van at(), de nyújtja a tömböt (maxsize-ig)
nincs operator[]
van iterátora (iterator)
konstruktorai a konténereknél megszokottak
van operator=
• std::vector:
– minden van, de nem nyújtja a tömböt az at(), de
dinamikusan képes növekedni (push_back)
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
-4 -
Egy lehetséges megvalósítás #1
template <typename T, size_t maxsiz = 6>
struct Array : public std::vector<T> {
Array(size_t n = 0, const T& value = T())
:std::vector<T>::vector(n, value) {}
template <class Iter>
Array(Iter first, Iter last)
:std::vector<T>::vector(first, last) {}
T& at(size_t i) {
if (i < maxsiz && i >= std::vector<T>::size())
std::vector<T>::resize(i+1);
return std::vector<T>::at(i);
}
const T& at(size_t i) const {
return std::vector<T>::at(i);
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
-5 -
Egy lehetséges megvalósítás #2
private:
T& operator[](size_t i);
const T& operator[](size_t i) const {
...
};
std::vector minden tagfüggvénye az öröklés révén publikálva,
a nem megfelelőeket módosított működéssel megvalósítottuk.
Ha nem jó, lehet privát örökléssel is, ekkor minden fv-hez
kell interfész. Ekkor a kompatibilitás elveszik!
Szóba jöhet még a tartalmazás (delegálás) is.
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
-6 -
Delegálással (tartalmazással) #1
template <typename T, size_t maxsiz = 6>
class Array {
std::vector<T> vec;
public:
Array(size_t n = 0, const T& value = T())
: vec(n, value) {}
template <class Iter>
Array(Iter first, Iter last) : vec(first, last) {}
T& at(size_t i) {
if (i < maxsiz && i >= vec.size())
vec.resize(i+1);
return vec.at(i);
}
const T& at(size_t i) const { return vec.at(i); }
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
-7 -
Delegálással (tartalmazással) #2
size_t size() const { return vec.size() };
size_t capacity() const { return vec.capacity() };
...
typedef typename std::vector<T>::iterator itarator;
iterator begin();
iterator end();
};
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
-8 -
Apróbb működési különbségek #1
template <typename T, size_t maxsiz = 6>
struct Array : public std::vector<T> {
Array(size_t n = 0, const T& value = T())
:std::vector<T>::vector(n, value) {}
// nagyobb lehet maxsiz-nél
// nincs maxsiz-ig lefoglalva
// modosítás:
Array(size_t n = 0, const T& value = T())
:std::vector<T>::vector(std::min(n,maxsiz), value) {
std::vector<T>::reserve(maxsiz);
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
-9 -
Apróbb működési különbségek #2
template <typename T, size_t maxsiz = 6>
template <class Iter>
Array(Iter first, Iter last)
:std::vector<T>::vector(first, last) {}
// nagyobb lehet maxsiz-nél
// nincs maxsiz-ig lefoglalva
// modosítás:
template <class Iter>
Array(Iter first, Iter last)
:std::vector<T>::vector(first, last) {
if (std::vector<T>::size() > maxsiz)
std::vector<T>::resize(maxsiz);
else
std::vector<T>::reserve(maxsiz);
}
https://git.ik.bme.hu/Prog2/eloadas_peldak/ea_11
C++ programozási nyelv © BME-IIT Sz.I.
vetor2gen_array_adapter
2021.05.03.
- 10 -
Működés leírása
A statikus modell önmagában nem elegendő
cellak[n][m]
Obj
nev, meret,
iter, ittaveg
lep
lep
Ocean
Viz
C++ programozási nyelv © BME-IIT Sz.I.
Hal
Capa
kor
kor
nemEvett
lep
lep
2021.05.03.
- 11 -
Ocean::lep()
/// Egy iterációs lépés
void Ocean::lep() {
iter++;
for (int i = 0; i < MaxN; i++)
for (int j = 0; j < MaxM; j++) {
Koord pos(i,j);
cellak[i][j]->lep(pos, *this, iter);
// hullák begyűjtése
if (cellak[i][j]->is_vege())
replObj(pos, new Viz);
}
}
// Objektum törlése és pointer átírása
void Ocean::replObj(Koord& pos, Obj* o) {
delete cellak[pos.i][pos.j];
cellak[pos.i][pos.j] = o;
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 12 -
Szekvenciadiagram
Koord pos(i,j);
cellak[i][j]->lep(pos, *this, iter);
if (cellak[i][j]->is_vege())
replObj(pos, new Viz);
Objektumok közötti
üzenetváltások időbeli
lefolyását szemlélteti.
sd lépés_ocean
Client
Idő
atlanti : Ocean
lep()
cella : Hal
<<create>>
pos : Koord
lep(pos, atlanti, iter)
üzenet
válasz
is_v ege()
v ege
opt
[ v ege ]
<<create>>
replObj(pos, v iz)
<<destroy >>
C++ programozási nyelv © BME-IIT Sz.I.
feltétel
v iz : Viz
megszűnik
2021.05.03.
- 13 -
Hal::lep()
/// Hal viselkedése
void Hal::lep(const Koord& pos, Ocean& oc, int it){
if (iter >= it) return;
iter = it;
kor++;
Koord ujPos = keres(pos, oc);
if (oc.ervenyes(ujPos)) {
oc.replObj(ujPos, this);
Obj* o;
if (kor > halSzapKor)
o = new Hal(*this);
else
o = new Viz;
oc.setObj(pos, o);
}
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 14 -
Hal::lep() szekvenciadiagramja
sd lépés_hal
atlanti : O cean
Idő
pos : Koord
cella : H al
v iz : V iz
lep(pos, atlanti, iter)
opt
[ iter < it ]
ujP os = keres()
erv enyes(ujPos)
erv
opt
[ erv ]
replaceO bj(ujPos, cella)
<<destroy>>
alt
[ kor > halS zapKor ]
<<create>>
hal : H al
setO bj(hal)
<<create>>
v iz2 : V iz
10 : setO bj(viz2)
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 15 -
Cápali és Cápeti
C++ programozási nyelv © BME-IIT Sz.I.
2011.04.26.
- 16 2021.05.03.
- 16 -
Feladat
• Egészítsük ki a korábbi modellünket:
– 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.
– Dokumentum film készül Cápeti útjáról.
• Kérdések:
– Tegyünk 3 jeladót Cápeti nyakába?
– 1 jeladó jelezzen mindenkinek?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 17 -
Observer terv. minta
Observer
-subjPtr
Subject
-obsPtr[]
+attach()
+detach()
+notify()
+update( )
ConcreteObs1
ConcreteObs2
ConcreteSubj
+update( )
C++ programozási nyelv © BME-IIT Sz.I.
+update( )
2021.05.03.
- 18 -
Subject osztály
class Subject {
set<Observer*> obs; // observerek pointere
public:
void attach(Observer* os);
void detach(Observer* os);
void notify(int reason);
virtual ~Subject();
};
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 19 -
Observer osztály
class Observer {
Subject *subj;
// megfigyelt objektum
public:
Observer(Subject* subj);
virtual void update(Subject* subj,
int reason);
virtual ~Observer();
};
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 20 -
Subject tagfüggvényei /1
void Subject::attach(Observer *o) {
obs.insert(o);
}
void Subject::detach(Observer *o) {
obs.erase(obs.find(o));
}
Subject::~Subject() {
notify(0);
// jelzi, hogy megszűnt
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 21 -
Subject tagfüggvényei /2
// minden figyelőt értesít a változásról
void Subject::notify(int reason) {
for (std::set<Observer*>::iterator it =
obs.begin(); it != obs.end(); it++ )
(*it)->update(this, reason);
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 22 -
Observer tagfüggvényei
Observer::Observer(Subject *subj) :subj(subj){
subj->attach(this);
}
void Observer::update(Subject* subj, int reason) {
if (reason == 0)
this->subj = 0;
// megszűnt: nem figyeli
}
Observer::~Observer() {
if (subj != 0)
// van még kit figyelni ?
subj->detach(this);
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 23 -
Figyelt cápa
class FigyeltCapa :public Capa, public Subject {
Koord lastPos;
public:
Koord getpos() const { return lastPos; }
void lep(Koord pos, Ocean& oc, int it);
};
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 24 -
Cápafigyelő
//A példában minden ebben az osztályban van, de célszerűen több
// figyelő kellene.
class CapaFigyelo : public Observer {
.....
public:
CapaFigyelo(FigyeltCapa *fc);
int getkor() const;
// kor lekérdezése
int getehes() const;
// éhség lekérdezése
int getszapor() const; // szaporulat lekérdezése
void update(Subject *subj, int oka);
void ut(std::ostream& os);
};
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 25 -
CapaFigyelo::update()
void CapaFigyelo::update(Subject *subj, int oka) {
if (oka != 0) {
// Tudjuk, hogy figyelt cápára mutató poi, ezért konvertálunk
FigyeltCapa *fc = dynamic_cast<FigyeltCapa*>(subj);
// Biztonságból ellenőrizzük a down cast eredményét
if (fc == 0) throw std::runtime_error("bad_cast: Figyelt");
kor = fc->getkor();
ehes = fc->getehes();
szapor = fc->getszapor();
utvonal.push_back(fc->getpos());
}
// Alaposztály update: megszünteti a regisztrációt, ha kell
Observer::update(subj, oka);
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 26 -
Figyelés indítása
FigyeltCapa *capeti = new FigyeltCapa;
CapaFigyelo mester(capeti);
CapaFigyelo filmes(capeti);
CapaFigyelo biologus(capeti);
….
cout << "Capeti kora:" << mester.getkor() << endl;
cout << "Capeti utodai:" << biologus.getszapor() << endl;
cout << "Capeti utja:";
filmes.ut(cout);
cout << endl;
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 27 -
Eredmény
Capeti kora:52
Capeti utodai:46
Capeti utja:
(2,5) (1,5) (0,5) (0,6) (0,6) (0,7) (0,7) (0,8) (0,8) (0,9) (0,9) (0,10) (0,10)
(0,11) (0,11) (0,12) (0,12) (0,13) (0,13) (0,14) (0,14) (0,15) (0,15) (0,16)
(0,16) (0,17) (0,17) (0,18) (0,18) (0,19) (0,19) (0,20) (0,20) (0,21) (0,21)
(0,22) (0,22) (0,23) (0,23) (0,24) (0,24) (0,25) (0,25) (0,26) (0,26) (0,27)
(0,27) (0,28) (0,28) (0,29) (0,29) (0,30) (0,30) (0,31) (0,31) (0,32) (0,32)
(0,33) (0,33) (0,34) (0,34) (0,35) (0,35) (0,36) (0,36) (0,37) (0,37) (0,38)
(0,38) (0,39) (0,39) (1,39) (1,39) (2,39) (2,39) (3,39) (3,39) (4,39) (4,39)
(5,39) (5,39) (6,39) (6,39) (7,39) (7,39) (8,39) (8,39) (9,39) (9,39) (8,39)
(8,38) (7,38) (6,38) (5,38) (5,38) (4,38)/
https://git.ik.bme.hu/Prog2/eloadas_peldak/ea_11
C++ programozási nyelv © BME-IIT Sz.I.
SharskAndFishes2
2021.05.03.
- 28 -
Nyolc királynő probléma
• 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.
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 29 -
Probálgatás
• Egy oszlopban csak egy királynő lehet,
ezért oszloponként próbálgatunk.
? ? ? ? ?
? ?
? ?
?
? ?
?
?
?
?
?
?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 30 -
Visszalépés (back track)
• 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.
2021.05.03.
- 31 -
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.
? ? ? ? ? ? ?
? ?
? ? ?
? ?
? ? ?
? ?
? ?
?
? ?
?
?
?
?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 32 -
Visszalépés és újból próba
• Egy lehetséges megoldást a 876. lépésben
kapunk.
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 33 -
Hogyan modellezhető ?
• 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.
• Okoskodó tábla, okos királynő
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 34 -
Okos tábla metódusai:
•
•
•
•
•
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
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 35 -
Metódus spec. - Szabad
bool Szabad(int sor, int oszlop);
– megvizsgálja, hogy az adott helyre lehet-e királynőt tenni.
– bemenet:
• sor – sor (1..8)
• oszlop – oszlop (1..8)
– kimenet:
• true – a pozíció szabad
• false – ütésben van a királynő
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 36 -
Metódus spec. - Lefoglal
void Lefoglal(int sor, int oszlop);
– Lefoglalja az adott pozíciót.
– bemenet:
• sor – sor (1..8)
• oszlop – oszlop (1..8)
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 37 -
Metódus spec. - Felszabadit
void Felszabadit(int sor, int oszlop);
– Felszabadítja az adott pozíciót.
– bemenet:
• sor – sor (1..8)
• oszlop – oszlop (1..8)
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 38 -
Metódus spec. - Rajzol
void Rajzol(int sor, int oszlop);
– Kirajzolja a táblát.
Az aktuális sor, oszlop pozícióba ? jelet tesz
– bemenet:
• sor – sor (1..8)
• oszlop – oszlop (1..8)
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 39 -
Metódus spec. - Probal
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 sikerült a 8. oszlopba is.
• false - ha nem sikerült
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 40 -
Implementáció - Probal
bool Probal(int oszlop) {
int sor = 1; bool siker = false;
következő
do {
oszlopba
if (Szabad(sor, oszlop)) {
Lefoglal(sor, oszlop)
if (oszlop < 8) siker = Probal(oszlop+1);
else
siker = true;
if (!siker)
Felszabadit(sor, oszlop);
}
sor++;
nem sikerült,
} while (!siker && sor <= 8);
visszalép
return(siker);
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 41 -
Adatszerkezet (mit kell tárolni?)
• Adott sorban van-e királynő
– 8 sor: vektor 1..8 indexszel
• Adott átlóban van-e királynő
– 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ó)
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 42 -
Átlók tárolása
sor - oszlop = állandó
1
2
3
4
5
6
7
8
sor + oszlop =
állandó
12 3 4 5 6 7 8
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 43 -
Működés megfigyelése
• A minden próbálkozást számolunk:
–
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: tab változó
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 44 -
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;
// sorok foglaltsága
// főátlók (s-o)
// mellékátlók (s+o)
// kiíráshoz kell
// kiíráshoz kell
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.
2021.05.03.
- 45 -
Tabla osztály megvalósítása /2
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;
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 46 -
Tabla osztály megvalósítása /3
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.
2021.05.03.
- 47 -
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;
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 48 -
Implementáció - kiir
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";
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 49 -
Főprogram
int main()
{
Tabla t;
if (t.Probal(1)) {
t.Rajzol(8, 0);
// végleges áll. kirajzolása
cout << "Siker";
} else
cout << "Baj van";
}
https://git.ik.bme.hu/Prog2/eloadas_peldak/ea_12
C++ programozási nyelv © BME-IIT Sz.I.
kiralyno
2021.05.03.
- 50 -
Eredmények
60.
8|*| | | | | | | |
7| | | | |*| | | |
6| |*| | | | | | |
5| | | | | |*| | |
4| | |*| | | | | |
3| | | | | | |*| |
2| | | |*| | | | |
1| | | | | | | |?|
A B C D E F G H
C++ programozási nyelv © BME-IIT Sz.I.
638.
8|*| | | | | | | |
7| | | | | | | | |
6| | | | | | | | |
5| | | | | | | | |
4| |?| | | | | | |
3| | | | | | | | |
2| | | | | | | | |
1| | | | | | | | |
A B C D E F G H
2021.05.03.
- 51 -
Eredmények /2
876.
8|*| | | | | | | |
7| | | | | | |*| |
6| | | | |*| | | |
5| | | | | | | |*|
4| |*| | | | | | |
3| | | |*| | | | |
2| | | | | |*| | |
1| | |*| | | | | |
A B C D E F G H
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 52 -
Okos királynő
Kiralyno *babu = NULL;
for (int i = 1; i <= 8; i++) {
babu = new Kiralyno(i, babu);
babu->Helyezkedj();
}
bool Kiralyno::Helyezkedj() {
while (szomszed != NULL &&
szomszed->Utesben(sor, oszlop))
if (!Lep()) return false;
return true;
}
C++ programozási nyelv © BME-IIT Sz.I.
? ? ? ? ?
? ?
? ?
?
? ?
?
?
?
?
?
?
2021.05.03.
- 53 -
Okos királynő metódusai:
• 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.
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 54 -
Metódus spec. - Utesben
bool Utesben(int sor, int oszlop);
– megvizsgálja, hogy az adott pozíció ütésben áll-e 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
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 55 -
Metódus spec. - Lep
void Lep();
– 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:
• true – tudott lépni
• false – nem tudott lépni
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 56 -
Metódus spec. - Helyezkedj
void Helyezkedj();
– 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 megfelelő helyet találni magának
• false – nem tudott megfelelő helyet találni
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 57 -
Metódus spec. - Kiir
void Kiir();
– Kiírja a saját és a szomszédok pozícióját.
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 58 -
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();
};
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 59 -
Kiralyno osztály megvalósítása/2
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;
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 60 -
Kiralyno osztály megvalósítása/3
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;
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 61 -
Kiralyno osztály megvalósítása/4
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;
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 62 -
Főprogram
int main()
{
Kiralyno *babu = NULL;
for (int i = 1; i <= 8; i++) {
babu = new Kiralyno(i, babu);
babu->Helyezkedj();
}
babu->Kiir();
}
https://git.ik.bme.hu/Prog2/eloadas_peldak/ea_12
C++ programozási nyelv © BME-IIT Sz.I.
kiralyno2
2021.05.03.
- 63 -
Megtalálja-e az egér a sajtot?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 64 -
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.
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 65 -
Megtalálja-e az egér a sajtot?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 66 -
Megtalálja-e az egér a sajtot?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 67 -
Megtalálja-e az egér a sajtot?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 68 -
Megtalálja-e az egér a sajtot?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 69 -
Megtalálja-e az egér a sajtot?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 70 -
Megtalálja-e az egér a sajtot?
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 71 -
Hogyan modellezhető ?
• Résztvevők, kapcsolatok, tevékenységek
– labirintus
•
•
•
•
•
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
– egér
• irány
• néz
• lép
– fal
• hasonlít az egérhez, de nem lép
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 72 -
Statikus modell
Labirint
Cella
Obj
n, m, poi
szomszéd,
nyom,
irány
Lép, Print
Set.., Get..
Néz,Lépj,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
C++ programozási nyelv © BME-IIT Sz.I.
Eger
Fal
jel, erő
jel, erő
Lép
Lép
2021.05.03.
- 73 -
Obj metódusai
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.
2021.05.03.
- 74 -
Eger objektum
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";
}
};
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 75 -
Cella objektum /1
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<Labnyom> 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.
2021.05.03.
- 76 -
Cella objektum /2
......
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()));}
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 77 -
Főprogram (részlet)
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.
2021.05.03.
- 78 -
Labirintus léptetés
• 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)
– Balról jobbra, és lefelé haladunk. Akkor van
baj, ha jobbra lép vagy le.
• Segédváltozókkal az objektumok pointereit
ellenőrizzük.
• Obj::Lep hibát dobhat, kezelni kell
(ld. Labirint::Lep())
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 79 -
Obj::lep(Cella& c) /1
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 {
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 80 -
Obj::Lep() /2
// 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)
}}}}
https://git.ik.bme.hu/Prog2/eloadas_peldak/ea_12
C++ programozási nyelv © BME-IIT Sz.I.
labirintus
2021.05.03.
- 81 -
Amőba
• Szereplők: tábla, korongok, játékosok
• Kis ismeri a szabályokat?
– Tábla?
– Korongok?
• Választott megvalósítás:
–
–
–
–
Tábla ismeri a korongok helyzetét, szomszédokat.
A korongok le tudják kérdezni a szomszédokat.
A korongok egy általánosított pozíciót és irányt ismernek.
Meg tudják állapítani, ha nyert helyzet van. Ekkor színt váltanak.
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 82 -
Objektum hierachia
Table belső
osztálya
Position beépíthető lenne
a Disc osztályba, de a
felelősségek így jobban
elvállnak.
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 83 -
Table::Position
•
•
•
•
•
A tárolás és a pozíció kapcsolatát elfedi.
A csak korongra tartozó információkat nyújtja.
Tárolja az x,y koordinátát, de annak felhasználását a táblára bízza.
Tábla a „barátja” így az eléri a privát tagfüggvényeket is.
A korong számára a szomszédokat ill. adott irányú szomszédokat
adja, amit a táblától kér el.
• A szomszéd fogalmat így csak a tábla értelmezi.
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 84 -
Table::Position
class Position {
friend class Table; ///< Table osztály hozzáférhet a privát adatokhoz
int x, y;
///< koordináták
Table *tp;
///< Erre a táblára hivatkozik.
int getx() const { return x; } ///< Közvetlenül is elérné, de...
int gety() const { return y; }
public:
Position(int x, int y, Table* tp) :x(x), y(y), tp(tp) {}
neighbors_type getNeighbors() { return tp->getNeighbors(x, y); }
Disc* getNext(int dir) { return tp->getNext(x, y, dir); }
};
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 85 -
Table::dirs
// Az irányokat egy egész szám jelöli ki, ami nem más,
// mint az irányok táblájának indexe.
// Az irányok fogalom így tetszőlegesen bővíthető és csak a
// tábla értelmezi
struct dir_type { int dx, dy; }
dirs[8] = { -1, -1 },
{ -1, 0 },
{ -1, 1 },
...
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 86 -
Szomszédok és irányok
typedef std::map<int, Disc*> neighbors_type;
class Table {
std::vector<std::vector<Disc*> > t;
static const int MaxDir = 8;
struct dir_type { int dx, dy; } dirs[MaxDir];
...
bool 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);
return true;
}
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 87 -
Sor ellenőrzése egyik irányban
bool Disc::check(color_type col,int dir, int max){
if (col == color) {
if (--max == 0) {
setColor(red); // átváltjuk
return true;
} else {
Disc *dp = pos.getNext(dir);
if (dp && dp->check(col, dir, max)) {
setColor(red);
return true;
}
}
}
return false;
}
C++ programozási nyelv © BME-IIT Sz.I.
2021.05.03.
- 88 -
Amőba főprogram
int main() {
Table t;
int x, y;
t.setDisc(new Disc(t.newPosition(3,3), white));
t.list(); char c = 'X';
do {
cout << c << " lepese: ";
if (!(cin >> x >> y)) break;
color_type col = c == 'O' ? white : black;
if (t.probe(x,y)) {
t.setDisc(new Disc(t.newPosition(x,y), color_type(col)));
t.list();
c = c == 'X' ? 'O' : 'X';
} else { cout << "oda nem lephet!"; }
cout << '\n';
} while (true);
}
https://git.ik.bme.hu/Prog2/eloadas_peldak/ea_12
C++ programozási nyelv © BME-IIT Sz.I.
amoba
2021.05.03.
- 89 -
