Note de curs, probleme algoritmică, clasa IX/X, 12 decembrie 2014

From Algopedia
Jump to navigationJump to search

Î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;
}