Note de curs, probleme algoritmică, clasa IX/X, 12 decembrie 2014
În acest curs am prezentat restricțiile impuse de programarea funcțională și am implementat câteva operații și câțiva algoritmi pe liste simplu înlănțuite.
Restricții
Este permisă inițializarea de variable:
const int a = 7; const int* const p = &a;
Nu este permisă atribuirea de variabile:
a = 9; // eroare p = new int; // eroare
Nu este permisă modificarea datelor adresate de un pointer:
*p = 9; // eroare
Nu este permisă atribuirea de variabile prin alți operatori:
a++; // eroare a--; // eroare a += 2; // eroare
Ca o consecință, structurile repetitive nu pot fi folosite:
for (int i = 0; i < 10; ++i); // eroare int i = 0; while (i < 10) { ++i; // eroare }
Pentru a transforma limbajele C și C++ în limbaje funcționale vom declara toate variabilele constante. Singura excepție tolerabilă fiind atunci când citim datele cu ajutorul funcțiilor din familia scanf.
Definirea unui element al unei liste simplu înlănțuite de întregi
#include <cstdio> #include <cstdlib> #include <cassert> class Nod { public: const int head; const Nod *const tail; Nod(const int val, const Nod *const tail) : head(val), tail(tail) {} };
Operații elementare
1. Să se scrie o funcție care creează o listă (de întregi) goală.
const Nod* const emptyList() { return NULL; }
2. Să se scrie o funcție care verifică dacă o listă dată este vidă.
bool isEmpty(const Nod* const lista) { return lista == NULL; }
3. Să se scrie o funcție care adaugă un element (un întreg) la începutul unei liste existente, creând o listă nouă.
const Nod* const prepend(const int valoare, const Nod* const lista) { return new Nod(valoare, lista); }
4. Să se afișeze pe ecran elementele unei liste date.
void print(const Nod *const lista) { if (!isEmpty(lista)) { printf("%d ", lista->head); print(lista->tail); } }
Alte operații
5. Să se adauge un element la sfârșitul unei liste date.
const Nod* const append(const int valoare, const Nod* const lista) { if (isEmpty(lista)) { return prepend(valoare, emptyList()); } else { return prepend(lista->head, append(valoare, lista->tail)); } }
6. Dându-se o listă nouă, să se creeze o listă nouă cu elementele primeia în ordine inversă.
const Nod* const reverse(const Nod* const lista, const Nod* const result = emptyList()) { if (isEmpty(lista)) return result; else return reverse(lista->tail, prepend(lista->head, result)); }
7. Să se creeze o listă nouă, cu elementele de pe poziții impare ale unei liste date.
const Nod* const evenElements(const Nod* const lista); const Nod* const oddElements(const Nod* const lista) { if(isEmpty(lista)) return emptyList(); else return prepend(lista->head, evenElements(lista->tail)); }
8. Să se creeze o listă nouă, cu elementele de pe poziții pare ale unei liste date.
const Nod* const evenElements(const Nod* const lista) { if (isEmpty(lista)) return emptyList(); else return oddElements(lista->tail); }
Algoritmi pe liste
9. Să se aleagă aleator, echiprobabil, un element dintr-o listă.
int rand(int max) { return rand() % max; } const int pivot(const Nod* const lista, int lung = 1) { if (isEmpty(lista)) return 0x80000000; else{ int chosen = pivot(lista->tail, lung + 1); if (chosen != (int)0x80000000) return chosen; else if (rand(lung) == 0) return lista->head; else return 0x80000000; } }
10. Să se interclaseze două liste sortate, într-una singură.
const Nod* const interleave(const Nod* const lista1, const Nod* const lista2) { if (isEmpty(lista1)) return lista2; else if (isEmpty(lista2)) return lista1; else if (lista1->head < lista2->head) return prepend(lista1->head, interleave(lista1->tail, lista2)); else return prepend(lista2->head, interleave(lista1, lista2->tail)); }
11. Dându-se o listă și o valoare, să se separe în trei liste, una cu elementele mai mici, una cu elementele egale și una cu valoarea dată.
template<class Type> class Tuple3 { public: Type first; Type second; Type third; Tuple3(Type first, Type second, Type third) : first(first), second(second), third(third) { ; } }; Tuple3<const Nod* const> split(const int valoare, const Nod* const lista) { if (isEmpty(lista)) return Tuple3<const Nod* const>( emptyList(), emptyList(), emptyList()); else { Tuple3<const Nod* const> impart = split(valoare, lista->tail); if (lista->head < valoare) return Tuple3<const Nod* const>( prepend(lista->head, impart.first), impart.second, impart.third); else if (lista->head == valoare) return Tuple3<const Nod* const>( impart.first, prepend(lista->head, impart.second), impart.third); else return Tuple3<const Nod* const>( impart.first, impart.second, prepend(lista->head, impart.third)); } }
12. Dându-se două liste, să se obțină o listă nouă, cu elementele primeia înalintea elementelor celei de-a doua.
const Nod* const concat(const Nod* const lista1, const Nod* const lista2) { if (isEmpty(lista1)) return lista2; else return prepend(lista1->head, concat(lista1->tail, lista2)); }
13. Dându-se o listă, să se obțină o nouă listă cu elementele primeia sortate folosind algoritmul Merge Sort.
const Nod* const mergeSort(const Nod* const lista) { if (isEmpty(lista) || isEmpty(lista->tail)) return lista; else return interleave( mergeSort(oddElements(lista)), mergeSort(evenElements(lista))); }
14. Dându-se o listă, să se obțină o nouă listă cu elementele primeia sortate folosind algoritmul Quick Sort.
const Nod* const quickSort(const Nod* const lista) { if(isEmpty(lista)) return emptyList(); else { Tuple3<const Nod* const> imp = split(pivot(lista), lista); if (isEmpty(imp.first) && isEmpty(imp.third)) return imp.second; else return concat( concat( quickSort(imp.first), quickSort(imp.second)), quickSort(imp.third)); } }
15. Să se testeze funcțiile implementate anterior.
int main() { print(quickSort(prepend(4, prepend(6, prepend(7, prepend(5, prepend(1, prepend(8, emptyList())))))))); printf("\n"); print(mergeSort(prepend(4, prepend(6, prepend(7, prepend(5, prepend(1, prepend(8, emptyList())))))))); return 0; }