Post on 01-Feb-2018
LECTOR ADRIAN RUNCEANU
Programare orientată pe obiecte
Universitatea “Constantin Brâncuşi” din Târgu-Jiu
Facultatea de Inginerie
Departamentul de Automatică, Energie şi Mediu
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
2
Curs 8
Polimorfism
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
3
Polimorfismul este legat de moștenire. Considerăm o clasa O1 care conține o metodă
M1 care o apelează pe alta M2 din aceeași clasă. O altă clasă O2 o moștenește pe prima. În cadrul
acesteia redefinim metoda M2, dar nu redefinim metoda M1.
Declarăm un obiect de tip O2 și apelăm metoda M1.
Problema este următoarea: care va fi metoda apelată de M1, M2 din O1 sau M2 din O2 ?
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
4
class O1 { metoda M2 {….} metoda M1 { metoda M2 ; } }; class O2: public O1 { metoda M2 { redefinită } }; int main() { O2 obiect; Obiect.M1; } În situația de mai sus va fi apelată metoda M2 din O1.
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
5
Exemplu: Considerăm următorul mod care
evidențiază situația precedentă: metoda care() apelează metoda tipar(), redefinită.
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
6
#include<iostream.h> class unu{ public: void care() { tipar() ; } void tipar() { cout<<"unu\n"; } };
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
7
class doi : public unu { void tipar() { cout<<"doi\n"; } };
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
8
int main() { unu x; doi y; x.care(); y.care(); }
Rezultatul executiei este:
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
9
În acest moment apare întrebarea:
De ce am mai redefinit o funcție (metodă) în noua clasă care moștenește clasa de bază, dacă nu putem folosi funcția (metoda) redefinită și o apelăm tot pe cea veche ?
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
10
O astfel de metodă de selecție a metodei prin obiectul care o apelează se numește selecție statică.
Codul de apel al funcției este obținut la compilare și rămâne nemodificat pe parcursul executării programului.
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
11
Soluția rezolvării unei astfel de probleme este să se facă selecția în momentul apelului (și nu la compilare).
În astfel de cazuri programatorul trebuie să decidă momentul în care metoda să fie selectată.
O astfel de selecție se numește selecție dinamică sau virtuală.
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
12
Pentru a realiza selecția virtuală trebuie să procedăm astfel:
1. când se declară în cadrul clasei de bază, o metodă ce va redefinită, se adaugă după declarație cuvântul virtual
2. orice redefinire a metodei, în cadrul claselor derivate, se va face utilizând același cuvânt cheie virtual
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
13
Exemplul anterior se modifică corespunzător prin adăugarea cuvantului cheie virtual, atât în cadrul clasei de bază unu, cât și în cadrul clasei derivate doi.
Rezultatul obținut este următorul:
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
14
#include<iostream.h> class unu{ public : void care() { tipar() ; } virtual void tipar() { cout<<"unu\n"; } };
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
15
class doi : public unu { virtual void tipar() { cout<<"doi\n"; } };
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
16
int main() { unu x; doi y; x.care(); y.care(); }
Rezultatul execuției este:
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
17
O aplicație implementată a
polimorfismului
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
18
La cursul de Proiectarea algoritmilor am învățat despre metoda backtracking standardizat.
Am observat acolo că metoda în sine constă dintr-o unică secvență de instrucțiuni care apela diferite funcții care aveau întotdeauna același nume, dar care se modificau de la un program la altul.
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
19
Vom încerca acum, să construim o clasă în care funcțiile init(), am_succesor() și celelalte să fie definite inițial cu valori simple, iar apoi în clasele derivate să poată fi redefinite astfel încât să rezolve fiecare problemă în parte.
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
20
Dificultatea constă în faptul că funcția run() care conține algoritmul de backtracking va apela funcțiile init(), succesor(), ș.a.m.d. și deci obiectul care o folosește trebuie să conțină și aceste funcții.
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
21
De aceea ele vor fi definite din start – în clasa de bază – ca fiind virtuale, pentru ca apoi în clasele derivate să poată fi redefinite corespunzător fiecarei clase în parte care rezolvă un anumit tip de problemă.
Deci, vom aplica polimorfismul.
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
22
Inițial în fișierul cu numele ‘back.cpp’, vom declara clasa bkt, în care funcțiile:
Deoarece ele nu vor fi niciodată apelate în cadrul acestei clase, vor avea ‘corpul’ vid.
init() am_succesor() e_valid() solutie() si tipar() vor fi declarate virtuale
init() am_succesor() e_valid() solutie() si tipar() vor fi declarate virtuale
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
23
De asemenea, tot în fișierul cu numele ‘back.cpp’. variabilele:
care se găsesc în orice program backtraking, vor fi declarate aici.
n - numarul de elemente care se prelucreaza in stiva
k - elementul curent din stiva (din varful stivei)
as - are succesor (se mai poate adauga un element pe
nivelul curent k)
ev - este valid (se indeplinesc cerintele problemei)
n - numarul de elemente care se prelucreaza in stiva
k - elementul curent din stiva (din varful stivei)
as - are succesor (se mai poate adauga un element pe
nivelul curent k)
ev - este valid (se indeplinesc cerintele problemei)
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
24
Fișierul ‘back.cpp’ conține clasa bkt: class bkt { public: int st[10],n,k; virtual void init() {}
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
25
virtual int am_succesor(){ return 0; } virtual int e_valid() { return 0; } virtual int solutie() { return 0; } virtual void tipar() {} void bkt::run(); };
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
26
void bkt::run() { int as; k=1; init(); while(k>0) { do{ }while( (as=am_succesor()) && !e_valid() ); if(as) if(solutie()) tipar(); else { k++; init(); } else k--; } }
O aplicaţie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
27
Exemple de probleme care pot fi rezolvate acum prin utilizarea clasei bkt, prin polimorfism:
1. Generarea permutărilor Se cere să se genereze toate permutările
mulțimii {1,2,…,n}.
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
28
Pentru a folosi clasa bkt vom defini o alta clasă, care o moștenește pe aceasta și care va avea funcțiile clasei inițiale, dar redefinite.
Vom folosi un constructor care va avea
rolul de a citi valoarea lui n.
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
29
Fișierul ‘perm.cpp’ va defini clasa permut care va fi derivată din clasa bkt:
#include<iostream.h> #include "back.cpp" class permut : public bkt { public: permut (int v) { n=v; }
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
30
virtual void init(); virtual int am_succesor(); virtual int e_valid(); virtual int solutie(); virtual void tipar(); };
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
31
void permut::init() { st[k]=0; } int permut::am_succesor() { if(st[k]<n){ st[k]++; return 1; } else return 0; }
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
32
int permut::e_valid() { for(int i=1; i<k; i++) if( st[i] == st[k] ) return 0; return 1; }
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
33
int permut::solutie() { return (k==n); } void permut::tipar() { for(int i=1;i<=k;i++) cout<<st[i]<<" "; cout<<"\n"; }
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
34
Se observă că acest fișier – la fel ca și cel anterior – nu are funcție main(), deoarece poate fi folosit în orice alt program care rezolvă probleme de generarea permutărilor.
Și anume poate fi folosit în următorul fișier care afișează rezultatul generării permutărilor mulțimii {1,2,…,n}:
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
35
#include<iostream.h> #include "perm.cpp" int main() { permut x(3); x.run(); }
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
36
Rezultatul execuției este:
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
37
2. Problema celor n regine(dame) Se cere să se genereze toate posibilitățile
de așezare a n dame pe o tablă de șah de dimensiune n*n, astfel în cât să nu se ‘atace’ reciproc.
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
38
După cum știm, rezolvarea problemei diferă de generarea permutărilor doar printr-o singură metodă: e_valid().
Atunci, vom redefini această metodă din clasa permut, pentru a putea obține soluția dorită:
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
39
Fișierul ‘regine.cpp’ va conține clasa dame care va fi derivată din clasa permut:
#include<math.h> #include "perm.cpp" class dame : public permut{ public: dame(int v) : permut(v) {}; virtual int dame::e_valid(); };
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
40
int dame::e_valid() { for(int i=1; i<k; i++) if( ( st[i] == st[k] ) || abs( st[k] -
st[i] ) == abs(k - i) ) return 0; return 1; }
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
41
Iar acum pentru scrierea programului care rezolva problema celor n regine vom construi fișierul ‘dame.cpp’ în care vom include fișierul ‘regine.cpp’:
Codul sursă al programului este:
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
42
#include<iostream.h> #include "regine.cpp" int main() { dame x(5); x.run(); }
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
43
Rezultatul execuției este:
O aplicatie a polimorfismului
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
44
Probleme propuse spre rezolvare:
1. Pornind de la clasa de bază bkt (din fișierul
“back.cpp”), să se implementeze, prin polimorfism
clasa virtuală ture pentru a rezolva problema turelor:
Se cere să se genereze toate posibilitățile de așezare a
n ture pe o tablă de șah de dimensiune n*n, astfel în
cât să nu se ‘”atace” reciproc.
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
45
Probleme propuse spre rezolvare:
2. Pornind de la clasa de bază bkt (din fișierul
“back.cpp”), și clasa derivată permut (din fișierul
“perm.cpp”), să se implementeze, prin polimorfism clasa
virtuală cuvinte pentru a rezolva următoarea problemă:
Se dă o mulțime alcătuită din n litere distincte. Se cer
toate cuvintele care se pot forma cu ele, astfel încât
fiecare cuvânt să conțină n litere distincte.
Exemplu: Dacă avem mulțimea {a,b,c}, atunci vom avea
cuvintele: abc, acb, bac, bca, cab, cba.
Polimorfism
13.11.2013 Curs - Programare orientată pe obiecte C++/Java
46
Întrebări?