Programarea Calculatoarelor: Laborator 3

În această lucrare vom rezolva probleme ajutăndu-ne de structura lor recursivă. Pentru scrierea funcțiilor recursive vom folosi tot expresia condițională.

Exerciții pregătitoare

Scrieți funcții recursive pentru câteva șiruri recurente cunoscute: progresia aritmetică, progresia geometrică, șirul lui Fibonacci, combinări. De exemplu:

Scrieți o funcție recursivă pentru termenul n din progresia aritmetică: x0=2, xn=xn-1+3, pentru n>0.

Scrieți o funcție recursivă pentru termenul n dintr-o progresie geometrică cu rația 1/2, primul termen fiind dat și el ca parametru. Efectuați calculele înainte de apelul recursiv, acumulând un rezultat parțial.

Scrieți o funcție care să calculeze pe e (baza logaritmilor naturali) cu o precizie de 10-6, folosind dezvoltarea în serie.

Probleme propuse

1. Rădăcina unei funcții. Găsiți, cu o aproximație dată, rădăcina unică a unei funcții continue și monotone f pe un interval [a, b] pe care funcția schimbă semnul. (Rezolvați pentru un caz concret al valorilor a, b și a funcției f).
Problema se rezolvă înjumătățind la fiecare pas intervalul de căutare, până când acesta devine mai mic decât precizia cerută. Se calculează valoarea funcției în mijlocul intervalului. Indiferent de semnul ei, cum în funcția are semne diferite în capetele intervalului, ea schimbă semnul pe una din cele două jumătăți de interval. Ajungem astfel la aceeași problemă, dar cu intervalul redus la jumătate. Cazul de bază e când lungimea intervalului e sub precizia cerută: orice valoare din interval e o aproximație suficientă.
Se poate eventual testa suplimentar dacă funcția e nulă în mijlocul intervalului, și returna direct rădăcina în acest caz.

2. Serii de puteri. Calculați, cu o precizie dată, valorile unor serii de puteri. De exemplu:
sin(x) = x - x3/3! + x5/5! - ... sau cos(x)= 1 - x2/2! + x4/4! - ...

3. Numere în format hexazecimal. Scrieți o funcție care returnează valoarea unui număr citit de la intrare caracter cu caracter, în format hexazecimal (cifrele 0-9, A-F sau a-f). (Adaptați funcția readnat scrisă la curs).

4. Limita unor termeni infiniți. Scrieți o funcție care calculează prin aproximări succesive expresia 1/(x + 1/(x + 1/(... + 1/x))) cu o precizie dată (de exemplu 10-6). Calculați și tipăriți o aproximație a expresiei pentru x = 4.
În problemă se dă un termen cu un număr infinit de apariții ale lui x. El are o structură recursivă, fiind de forma 1/(x + ...) unde în loc de ... apare termenul însuși. Putem scrie tn=1/(x+tn-1), pentru n > 0, cu t0 = 0. Rezolvăm problema similar cu cele de la curs, calculând în fiecare pas din termenul curent termenul următor, pânâ când diferența lor nu depășește precizia cerută.
Puteți verifica, comparând valoarea găsită cu cea a ecuației lim = 1/(x + lim) (de gradul 2 în variabila lim).

5. Fractali. Sunt figuri geometrice definite recursiv, în care un fragment e similar cu întreaga figură.
Desenați o figură recursivă, care conține un număr de copii mai mici, până la un anumit nivel. De exemplu, un triunghi echilateral (numit și triunghiul lui Sierpiński în care se leagă printr-un alt triunghi mijloacele laturilor, iar pentru cele 3 triunghiuri din colț se repetă recursiv procedura.
Aveți dat fișierul turtlegraph.c (nu trebuie studiat) care conține programul principal și definește un set de primitive grafice simple, inspirate din facilitățile TurtleGraphics introduse de limbajul LOGO. Sistemul menține implicit poziția cursorului și orientarea acestuia. Funcțiile void line(double len) și void skip(double len) avansează cursorul cu distanța dată, în direcția curentă, desenând o linie și respectiv, "sărind" înainte. Funcțiile left() și right() schimbă orientarea curentă prin rotire la stânga și la dreapta, cu un unghi fix, care pentru problema noastra definit la 120 de grade (se poate modifica pentru alte probleme). Programul apelează de asemenea funcția void draw(void), care face desenarea propriu-zisă, și care nu este încă definită. Urmează să implementaț, n fișierul triunghi.c această funcție care să deseneze cu primitivele de mai sus fractalul cu triunghiuri. Cele două fișiere le veți compila împreună în fișierul executabi triunghi folosind fișierul Makefile dat, cu comanda make triunghi
Putem exprima problema recursiv în felul următor: figura de bază (de ordin 0) e un triunghi de dimensiune unitară. Figura de ordin n e compusă din trei figuri de ordinul n-1, dispuse încât să formeze un triunghi echilateral mai mare.
Când desenați figura, e util să păstrați o convenție privind poziția și orientarea cursorului. Scrieți funcția de desenare a unei figuri elementare (triunghi) în așa fel încât la sfârșit, cursorul să revină la aceeași poziție și orientare. Apoi desenați cele 3 sub-figuri recursive, cu dimensiuni mai mici, poziționând între ele cursorul în mod corespunzător pentru fiecare, și apoi revenind cu el în punctul de plecare.


Marius Minea
Last modified: Thu Mar 12 08:08:58 EET 2009