Note de curs, programare orientată pe obiecte, 20 aprilie 2013

From Algopedia
Jump to navigationJump to search

Primul curs a fost o trecerere treptată de la programarea procedurală la programarea orientată pe obiecte. Ca exemplu, am ales un subiect de interes pentru pregătirea pentru concursuri și olimpiadă: calculul modular.

Cerința 1

Să se definească o structură Vector3, care să modeleze un vector în spațiu. Să se implementeze și testeze funcții care:

  • calculează suma a doi vectori;
  • testează egalitatea a doi vectori;
  • calculează opusul unui vector;
  • calculează diferența a doi vectori, folosind funcția de calcul al opusului;
  • calculează înmulțirea cu scalar a unui vector.
struct Vector3 {
	int x;
	int y;
	int z;
};

Vector3 add(const Vector3 a, const Vector3 b);

Vector3 equalTo(const Vector3 a, const Vector3 b);

Vector3 inverse(const Vector3 a);

Vector3 subtract(const Vector3 a, const Vector3 b);

Vector3 scalarMultiplication(const Vector3 a, const Vector3 b);

main() {
	Vector3 a, b;
	Vector3 s, d, m;
	
	a.x = 1;
	a.y = 2;
	a.z = 3;
	
	b.x = 7;
	b.y = 8;
	b.z = 9;
	
	s.x = 8;
	s.y = 10;
	s.z = 12;
	assert(equalTo(s, add(a, b)));
	
	d.x = -6;
	d.y = -6;
	d.z = -6;
	assert(equalTo(d, subtract(a, b)));
	
	m.x = 3;
	m.y = 6;
	m.z = 9;
	assert(equalTo(m, scalarMultiplication(a, 3)));
}

Cerința 2

Să se transforme structura în clasă și să se includă funcțiile definite anterior ca metode ale acesteia.

Primul parametru al fiecărei metode va dispărea din prototipul funcției, și va fi înlocuit de parametrul implicit this, care este pointer. Calificativul const al primului parametru va apărea la sfârșitul prototipului metodei. Instrucțiunile de test se rescriu ca apeluri de metode.

class Vector3 {
public:
	int x;
	int y;
	int z;
	
	Vector3 add(const Vector3 arg) const;
	
	Vector3 equalTo(const Vector3 arg) const;
	
	Vector3 inverse() const;
	
	Vector3 subtract(const Vector3 arg) const;
	
	Vector3 scalarMultiplication(const Vector3 arg) const;
};

assert(s.equalTo(a.add(b)));
assert(d.equalTo(a.subtract(b)));
assert(m.equalTo(a.scalarMultiplication(3)));

Cerința 3

Să se modifice metodele clasei, astfel încât să corespundă operatorilor +, ==, - unar, - și *.

Ca o consecință, codul de testare va deveni mult mai lizibil.

class Vector3 {
public:
	int x;
	int y;
	int z;
	
	Vector3 operator +(const Vector3 arg) const;
	
	Vector3 operator ==(const Vector3 arg) const;
	
	Vector3 operator -() const;
	
	Vector3 operator -(const Vector3 arg) const;
	
	Vector3 operator *(const Vector3 arg) const;
};

assert(s == a + b);
assert(d == a - b);
assert(m == a * 3);

Cerința 4

Să se implementeze funcția de minim a doi întregi.

int min(const int arg1, const int arg2) {
	return arg1 < arg2 ? arg1 : arg2;
}

int intA, intB, intM;
intM = min(intA, intB);

Ne punem problema să calculăm minimul dintre două variabile de același tip, oricare ar fi acel tip. Soluția este folosirea template-urilor:

template<class T>
T min(const T arg1, const T arg2) {
	return arg1 < arg2 ? arg1 : arg2;
}

int intA, intB, intM;
intM = min(intA, intB);
double doubleA, doubleB, doubleM;
doubleM = min(doubleA, doubleB);

T este un tip de date sau chiar o clasă (fapt indicat de cuvântul cheie class).

Putem aplica funcția min și pentru obiecte de tip Vector3, dar va trebui să implementăm operatorul < în clasă.

Dacă ne propunem să folosim vectori în spațiu cu coordonate care nu sunt obligatoriu întregi, ar trebui să modificăm clasa Vector3, astfel încât variabilele x, y și z să fie de tip double. Mai simplu este să scriem o implementare mai generală, cu template-uri pentru clase.

template<class T>
class Vector3 {
public:
	T x;
	T y;
	T z;
	
	...
};

Cerința 5

Să se implementeze clasa ModInteger, de calcul modular. Să se implementeze operatorii +, - unar, -, * și /.

Pentru specificarea numărului modulo se vor folosi template-uri. De asemenea, pentru specificarea tipului de date folosit pentru stocarea internă a valorii, se vor folosi tot template-uri:

template<unsigned int MOD, class T = unsigned long long>
class ModInteger {
	...
};

Astfel, pentru declararea obiectelor de tip ModInteger se poate folosi următoarea sintaxă:

ModInteger<666013> modA, modB; /* calculele se vor efectua modulo 666013,
    iar tipul de date folosit pentru stocare și calcul va fi cel implicit,
    unsigned long long. */

ModInteger<7, unsigned short int> mod7a, mod7b, mod7s; /* calculele se vor
    efectua modulo 7, iar tipul de date folosit pentru stocare și calcul
    va fi cel specificat explicit, unsigned short int. */

ModInteger var; /* va da eroare de compilare, deoarece primul parametru
    (modulo) este obligatoriu. */

Constructorul implicit (fără parametri) și constructorul cu parametri:

template<unsigned int MOD, class T = unsigned long long>
class ModInteger {
public:
	T value;

	/* Constructorul fără parametri se apelează de fiecare dată când se declară
         * un obiect de tip ModInteger, fără să i se și atribuie o valoare.
         *
         * Exemplu:
         *     ModIntever var;
         */
	ModInteger() {
		this->value = 0;
	}

	/* Constructorul cu parametru se apelează de fiecare dată când se declară
         * un obiect de tip ModInteger și, concomitent, i se atribuie o valoare sau
         * de fiecare dată când se efecturează o conversie implicită sau explicită
         * la ModInteger.
         *
         * Exemple:
         *     ModIntever var = 45;
         *     ModInteger var(45);
         *     var = (ModInteger)45;
         *     var = ModInteger(45);
         *     var = 45;
         */
	ModInteger(const T arg) {
		this->value = arg % MOD;
	}
	...
};

Minusul unar (sau inversul față de adunare) se calculează astfel:

	ModInteger operator -() const {
		return MOD - this->value;
	}

Împărțirea a două numere se calculează ca produsul dintre primul și inversul față de înmulțire al celui de-al doilea:

	ModInteger operator / (const ModInteger arg) const {
		return (ModInteger)(*this * arg.multiplicationInverse());
	}

Inversul față de înmulțire se calculează, pentru MOD număr prim, astfel:

	ModInteger multiplicationInverse() const {
		return this->pow(MOD - 2);
	}
	//this->pow(MOD - 1) == 1;
	//*this * this->pow(MOD - 2) == 1;
	//*this * answer == 1;
	//answer = this->pow(MOD - 2)

Ridicarea la puterea a unui număr se calculează, în timp logaritmic, prin divide et impera.