Programarea Calculatoarelor: Laborator 3

Exemplul 1 Citirea de numere reale
Adaptăm funcţia readnat scrisă la curs pentru a citi un număr real nenegativ, în format cu punct zecimal. Pentru aceasta trebuie să
-- scriem cod pentru a citi secvenţa de cifre de după punctul zecimal, şi a calcula partea zecimală
-- combinăm acest cod cu cel care dă valoarea părţii întregi
Pentru partea fracţională scriem o relaţie de recurenţă similară cu cea pentru partea întreagă. Remarcăm însă că fiecare cifră c_n nou citită se înmulţeşte cu o altă putere (negativă) a lui 10:

  f0 = 0  (partea fracţionară), p1 = 0.1 (puterea lui 10)
  fn = fn-1 + cn * pn (adaugă ultima cifră cn)
  pn+1 = 0.1*pn (puterea lui 10: 10-n)

double readfrac(double r, double p10, int c)
{
  return isdigit(c) ? readfrac(r+(c-'0')*p10, .1*p10, getchar()) : c
}

double readreal_rc(double r, int c)
{
  return isdigit(c) ? readreal_rc(10*r + (c-'0'), getchar())
    : c == '.' ? readfrac(r, .1, getchar()) // adauga partea fractionala
    : r;	// alt caracter decat punct, ramane doar partea intreaga
}
// scriem si o functie fara parametri care o foloseste pe cea ajutatoare
double readreal(void) { return readreal_rc(0, getchar()); }

La laborator se vor rezolva alte probleme similare, cum ar fi: citirea unui număr scris in baza 8 sau 16; adăugarea semnului şi/sau părţii cu exponent la citirea unui real, numărări şi transformări de cuvinte cu litere mari sau mici (cu funcţiile islower(), isupper(), tolower(), toupper() din <ctype.h>, etc.

Exemplul 2 Prelucrarea de texte
Cunoscând funcţiile de citire şi tipărire de caractere, putem efectua deja prelucrări simple asupra textelor citite, de exemplu: numărarea cuvintelor, determinarea celui mai lung cuvânt, rescrierea cuvintelor din text cu prima literă majusculă, toate majuscule sau toate literele mici, eliminarea spaţiilor multiple dintre cuvinte, filtrarea (eliminarea) anumitor părţi din text, etc.

Deşi simple, aceste programe trebuie să combine adesea mai multe prelucrări. Pentru a le scrie cât mai uşor, e util să ne stabilim câteva principii. În primul rând, vom structura programele în funcţii simple cu un scop bine definit. Aceste funcţii trebuie să ia decizii în funcţie de caracterele întâlnite. Ca şi la funcţiile de citire de numere vom face aşa încât ele să aibe ca parametru primul caracter ce trebuie prelucrat (el poate fi dat în momentul apelului cu funcţia getchar(). Tot din acelaşi motiv, e util să structurăm funcţiile astfel încât ele să returneze următorul caracter rămas neprelucrat (asemenea lui getchar). Aceastea va permite să exprimăm prelucrări succesive înlănţuind apelurile de funcţie: rezultatul fiecărui pas de prelucrare (primul caracter) e transmis ca argument următoarei prelucrări. De asemenea, nu cunoaştem când va apărea sfârşitul secvenţei de caractere prelucrate; fiecare caracter citit trebuie comparat cu EOF, iar la întâlnirea acestei valori, prelucrarea se încheie.

Scriem ca exemplu un program care numără cuvintele dintr-un text. Acestea pot fi separate prin oricâte spaţii, care pot apărea nu doar între cuvinte, ci şi la începutul sau sfârşitul textului. Scriem o funcţie care sare peste spaţiile (albe) întâlnite şi returnează primul caracter care nu e spaţiu:

int skipspace(int c)
{
  return isspace(c) ? skipspace(getchar()) : c;
}

int skipword(int c)
{
  return c == EOF ? c : isspace(c) ? c : skipword(getchar());
}

unsigned wordcount(unsigned cnt, int c)
{
  return c == EOF ? cnt : wordcount(cnt + 1, skipspace(skipword(c)));
}

int main(void)
{
  printf("%u\n", wordcount(0, skipspace(getchar())));
  return 0;
}

Exemplul 3 Fracţii continue
Orice număr real pozitiv poate fi scris sub următoarea formă de fracţie:
x = a_0 + 1 / (a_1 + (1 / (a_2 + .... + 1 / (a_n + ...)))).
unde numerele a0, a1, a2, ... sunt naturale.
Coeficienţii se pot calcula recursiv cu relaţia: a_n = [x_n], x_n+1 = 1 / (x_n - a_n) (cand x_n = a_n intreg, dezvoltarea se opreste). Fracţiile continue reprezintă o bună aproximare raţională a unui număr real.
Scrieţi o funcţie care tipăreşte reprezentarea unui număr real în fracţie continuă, ca mai sus (până la un termen de indice dat sau exact, în cazul numerelor raţionale). Observaţi că paranteza închisă trebuie tipărită după revenirea din apelul recursiv.

Exemplul 4 Fractali
Fractalii sunt figuri geometrice definite printr-o structură recursivă, în care un fragment e similar cu întreaga figură.
Un mare număr de curbe geometrice cu structură de fractali pot fi definite cu ajutorul unor reguli de substituţie simple.
Ideea este următoarea: cea mai simplă curbă (la nivel recursiv 0) e un segment de dreaptă. Curbele mai complicate se obştin înlocuind fiecare segment printr-o secvenţă de segmente mai mici şi rotaţii de direcţie, după anumite reguli.
Ca exemplu, aveţi dat un program care desenează triunghiul lui Sierpinski de un ordin dat. Fişierul gl_fractal.c (nu trebuie studiat) 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 line şi skip 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 unghiul stabilit anterior de funcţia angle (şi care de regulă rămăne constant pentru toată figura).

Fişierul sierp3.c implementează recursiv desenarea triunghiului: Iniţial (la nivelul 0), figura cea mai simplă e un segment, corespunzător cu apelul A(0). Apoi, la nivele de complexitate succesive, fiecare segment e înlocuit cu segmente şi rotaţii, reprezentate în definiţiile recursive ale funcţiilor A şi B, după regulile: A->B-A-B şi B->A+B+A unde + şi - înseamnă rotaţii cu un unghi fix (60 de grade) în sens trigonometric, şi respectiv antitrigonometric.

Remarcăm că pentru fiecare prelucrare (A, B) avem definite doua variante: funcţiile An şi Bn care conţin prelucrări compuse, apelând recursiv prelucrările de ordin inferior (n-1), şi funcţiile A şi B, care efectuează decizia, realizând în funcţie de n fie prelucrările compuse, fie cazul de bază.

Puteţi încerca după acest model să

• desenaţi alte figuri recursive
• scrieţi un program C care pornind de la reguli de transformare date în formatul mai sus genereaă definiţiile recursive de funcţii ca în exemplul dat cu triunghiul

Pentru prima variantă puteţi încerca să definiti alte figuri recursive, în care fiecare conţine un număr de copii mai mici, până la un anumit nivel. De exemplu, un triunghi echilateral în care se leagă printr-un alt triunghi mijloacele laturilor, iar pentru cele 3 triunghiuri din colţ se repetă recursiv procedura.

în scrierea unui astfel de program e util să păstrăm o convenţie privind poziţia şi orientarea cursorului. Astfel, concepem funcţia de desenare a unei figuri elementare în aşa fel încât la sfârşit, cursorul să revină la aceeaşi poziţie şi orientare. Apoi desenăm cele 3 sub-figuri recursive, păstrând aceeaşi convenţie privind revenirea cursorului.

Puteţi desena şi alte astfel de figuri, pornind de la pătrat, hexagon, etc.