Programare: Tema 4

Prelucrări de texte

Problema T1 Scrieţi un program care citeşte de la intrare un text, presupus a reprezenta un program C, şi îl afişează, mai puţin comentariile (scrise după regulile limbajului C).

Problema T2 În sistemul de preparare a documentelor LaTeX, documentele (exemplu) pot conţine pe lângă text obişnuit şi comenzi \numecomandă care încep cu caracterul \ şi pot avea opţional argumente: \numecomandă{arg1}{arg2} etc.

Scrieţi un program care citeşte de la intrare un text, presupus a reprezenta un document LaTeX, şi îl afişează din el doar textul obişnuit şi argumentele comenzilor, dar nu şi comenzile. Opţional, filtraţi din text şi comentariile, care încep cu caracterul % şi se termină la sfârşit de linie.

Problema T3 Scrieţi un program care citeşte de la intrare un text şi verifică dacă parantezele ( ) [ ] { } care apar în el sunt bine împerecheate (pot fi încuibate dar nu intercalate).
Soluţie

Recursivitate şi arbori

Un arbore binar e fie arborele vid, fie un nod rădăcină, cu un subarbore stâng şi un subarbore drept. Un arbore binar ordonat e un arbore în care fiecare nod conţine o valoare (de exemplu întreagă), iar subarborii sunt de asemenea arbori binari ordonaţi: toate valorile din subarborele stâng sunt mai mici decât cea din rădăcină, şi toate valorile din subarborele drept sunt mai mari.

Rezolvaţi următoarele probleme, în pseudocod, într-un limbaj de nivel înalt care permite definirea facilă de arbori, sau în C (se dau biblioteca inttree.c şi antetul inttree.h cu funcţiile necesare).

Problema A1 Scrieţi o funcţie care ia ca parametru un arbore binar ordonat şi un număr x şi returnează cea mai mare valoare din arbore care nu depăşeşte pe x (sau raportează o eroare dacă nu există).

Problema A2 Scrieţi o funcţie care ia ca parametru un arbore binar ordonat şi un număr nenegativ n şi returnează a n-a valoare (în ordine crescătoare) din arbore (sau raportează o eroare dacă nu există).
O soluţie posibilă: se creează un şir parcurgând arborele în inordine şi se ia elementul al n-lea din şir. Altă soluţie: se calculează dimensiunile subarborilor pentru a determina în care se află valoarea căutată. Ambele soluţii au elemente utile, dar pot face prelucrări inutile. Găsiţi o soluţîe mai bună.

Logică: condiţii complexe şi testarea programelor

Când testăm programe cu decizii complexe, dorim să evidenţiem faptul că fiecare condiţie individuală poate afecta rezultatul deciziei, pentru anumite valori (păstrate constante) ale celorlalte condiţii. (Acest criteriu de testare se numeşte multiple condition/decision coverage.)
De exemplu, pentru condiţia a || b, alegând a = F şi modificând b de la F la T, rezultatul se modifică de la F la T, şi simetric, alegând pe b=F, modificarea lui a schimbă rezultatul. Pe ansamblu, alegând cele 3 teste (1) a = F, b = F, (2) a = F, b = T, (3) a = T, b = F arătăm că rezultatul poate fi influenţat modificând doar pe b (perechea (1, 2)), şi doar pe b (perechea (1,3)).
De exemplu, pentru expresia a && (b || c) && (d || e) un astfel de set de teste e:

   a b c d e Rez
   -------------
1  F F T F T  F		a: (1, 3)
2  T F F F T  F		b: (2, 3)
3  T F T F T  T		c: (2, 4)
4  T T F F T  T
5  T F T F F  F         d: (3, 5)
6  T F T T F  T         e: (5, 6)

Concepeţi un algoritm care, pornind de la o expresie booleană complexă cu operatorii AND şi OR, şi variabile presupuse distincte, produce o multime de teste care arată (printr-o pereche de teste din mulţime) că fiecare variabilă poate influenţa independent rezultatul expresiei. Încercaţi să găsiţi o soluţie cu număr minim de teste.

Marius Minea

Last modified: Fri Oct 29 11:15:00 EET 2010