Programarea Calculatoarelor: Laborator 2

Exemplul 1: să se determine partea întreagă a unui număr real x aflat în intervalul [0, 1000).

Pornim de la definiţia părţii întregi: [x] = n (cu n întreg) dacă n <= x < n+1. Observăm că relaţia are aceeaşi structură ca şi problema dată: cunoaştem că x se află în intervalul [n, n+1) şi putem da direct răspunsul: partea întreagă este n (intervalul e suficient de mic pentru a avea o singură variantă posibilă).

Folosim descompunerea în subprobleme mai mici prin tehnica înjumătăţirii: comparăm x cu mijlocul intervalului iniţial [a, b) şi în funcţie de rezultat, aflăm dacă se află în prima sau a doua jumătate. Rămânem astfel cu o problemă de acelasi tip (aflarea părţii întregi a unui număr dintr-un interval), dar cu un interval mai mic, ceea ce ne apropie de cazul de bază (interval de lungime 1).

Pentru a scrie cele de mai sus precis, matematic, rezumăm în felul următor:
Rezultatul problemei pentru numărul x şi intervalul [a, b) este:
-- dacă b - a = 1, intregul a
-- altfel, daca x < (a+b)2, rezultatul este dat de aceeasi problema cu numarul x si primul interval [a, (a+b)/2)
-- altfel rezultatul este dat de aceeasi problema, cu numarul x si al doilea interval [(a+b)/2, b)

Formularea "problema pentru numarul ...", si faptul ca problema trebuie sa dea un rezultat indica faptul ca putem inlocui formularea "problema" cu "functie", si "pentru numerele ..." cu "parametri". Deci:
f(x, a, b) =
-- daca b - a = 1, atunci a
-- altfel, daca x < (a+b)/2, atunci f(x, a, (a+b)/2)
-- altfel, f(x, (a+b)/2, b)

int partint(double x, int lo, int hi)
{
  return hi - lo <= 1 ? lo :
    x < (lo+hi)/2 ? partint(x, lo, (lo+hi)/2) : partint(x, (lo+hi)/2, hi);
}

Combinand aceasta tehnica de injumatatire cu cea din exemplele de la curs pentru a ne opri la o precizie data, putem sa gasim (cu o anumita precizie) si radacina unei functii monotone pe un interval [a, b], daca stim ca functia schimba semnul pe acest interval.

Exemplul 2. Calculul restului modulo 9 (cu suma cifrelor):

Să se scrie o funcţie care determină restul unui număr dat ca parametru la împărţirea cu 9. Se permit doar operaţii numerice de comparare, împărţire modulo 10 şi adunare.
Ştim că restul la împărţirea cu 9 este acelaşi pentru număr şi suma cifrelor lui (care va fi în general mai mică). Deci scriem recursiv o funcţie care calculează suma cifrelor numărului (vezi pentru comparaţie funcţia de inversare a cifrelor din notiţele de curs. Suma cifrelor ar putea să fie tot un număr pe mai multe cifre, deci aplicăm procedura până când obţinem un număr de o singură cifră pentru care returnăm restul cerut.