Exemplul 1 (sugerat la curs): să se determine partea întreagă a unui număr real x aflat în intervalul [0, 1000).
Sugestia de soluție a fost să 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ă).
S-a sugerat de asemenea 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 sumei unor serii. Cursul contine doua exemple, unul pentru numar fix de termeni, unde calculul corespunde exact relatiei recursive din matematica, s_n = s_n-1 + t_n, si un exemplu pentru calculul cu o anumita precizie.
Pentru acest din urma caz, structura recursiva a problemei contine o
aproximatie curenta, dupa schema:
suma aproximata (o functie), tinand cont de aproximarea curenta (un parametru), este:
-- daca aproximarea curenta e suficient de buna, chiar aceasta
-- daca nu, atunci e suma aproximata (aceeasi functie), tinand cont de
aproximarea curenta actualizata cu ultimul termen
In functie de problema, putem da ca parametri suplimentari indicele termenilor (n), folosit pentru calcularea termenului curent, si uneori chiar si acesta (exemplul de la curs), pentru a exprima termenul urmator in functie de n.
Incercati sa scrieti astfel de functii pentru alte serii numerice sau serii Taylor cunoscute.