Programare orientata pe obiecte - curs - runceanu.ro2013).… · Polimorfism Curs - Programare...

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


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


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


5

Exemplu: Considerăm următorul mod care

evidențiază situația precedentă: metoda care() apelează metoda tipar(), redefinită.

Polimorfism


6

#include<iostream.h> class unu{ public: void care() { tipar() ; } void tipar() { cout<<"unu\n"; } };

Polimorfism


7

class doi : public unu { void tipar() { cout<<"doi\n"; } };

Polimorfism


8

int main() { unu x; doi y; x.care(); y.care(); }

Rezultatul executiei este:

Polimorfism


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


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


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


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

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


14

#include<iostream.h> class unu{ public : void care() { tipar() ; } virtual void tipar() { cout<<"unu\n"; } };

Polimorfism


15

class doi : public unu { virtual void tipar() { cout<<"doi\n"; } };

Polimorfism


16

int main() { unu x; doi y; x.care(); y.care(); }

Rezultatul execuției este:

Polimorfism


17

O aplicație implementată a

polimorfismului

O aplicatie a polimorfismului


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.



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.



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.



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.



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



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)



24

Fișierul ‘back.cpp’ conține clasa bkt: class bkt { public: int st[10],n,k; virtual void init() {}



25

virtual int am_succesor(){ return 0; } virtual int e_valid() { return 0; } virtual int solutie() { return 0; } virtual void tipar() {} void bkt::run(); };


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


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}.



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.



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; }



30

virtual void init(); virtual int am_succesor(); virtual int e_valid(); virtual int solutie(); virtual void tipar(); };



31

void permut::init() { st[k]=0; } int permut::am_succesor() { if(st[k]<n){ st[k]++; return 1; } else return 0; }



32

int permut::e_valid() { for(int i=1; i<k; i++) if( st[i] == st[k] ) return 0; return 1; }



33

int permut::solutie() { return (k==n); } void permut::tipar() { for(int i=1;i<=k;i++) cout<<st[i]<<" "; cout<<"\n"; }



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}:



35

#include<iostream.h> #include "perm.cpp" int main() { permut x(3); x.run(); }



36




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.



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ă:



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(); };



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; }



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:



42

#include<iostream.h> #include "regine.cpp" int main() { dame x(5); x.run(); }


43




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


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


46

Întrebări?

Programare orientata pe obiecte - curs - runceanu.ro2013).… · Polimorfism Curs - Programare...

Documents

Transcript of Programare orientata pe obiecte - curs - runceanu.ro2013).… · Polimorfism Curs - Programare...