Tehnici de programare structurata: Recursivitatea, Backtracking

Tehnici de programare structurata

Cele mai utilizate tehnici de programare structurata sunt :

Recursivitatea ;

Metoda Backtracking;

Metoda Divide et impera;

Metoda Greedy;

Metoda Branch and Bound;

Metode euristice;

Metoda programarii liniare;

Metoda programarii dinamice.

Recursivitatea

Este o tehnica de programare utilizata frecvent , in implementarea functiilor si procedurilor . La baza recursivitatii sta stiva, care este gestionata in mod implicit, in aceasta zona de memorie salvandu-se automat, la fiecare la fiecare apel de functieurmatoarele informatii :

Valorile parametrilor de tip valoare;

Adresele parametrilor de tip variabila;

Variabilele locale ale subprogramului;

Adresa de intoarcere la instructiunea aflata dupa instructiunea de apel.

Tehnica "Backtracking"

Aceasta tehnica se foloseste in rezolvarea unor probleme cum ar fi :

Generarea permutarilor de n elemente;

Generarea aranjamentelor;

Generarea combinarilor;

Generarea partitiilor unei multimi;

Problema celor N dame;

Produsul cartezian a N multimi;

Problema Comis-voiajorului;

Problema platii unei sume S utilizand N tipuri de monede;

Metoda " Divide et Impera"

Exemple de probleme rezolvate cu aceasta metoda : cautare binara.

Metoda Greedy

Caracteristicile acestei metode sunt :

La intrare avem o multime A cu N elemente

Se cere selectarea unei submultimi B a lui A sau o ordine de prelucrare a elementelor lui A care sa optimizeze o functie obiectiv data . Se cere deci o singura solutie.

Elementele multimii A se parcurg pe rand, dupa o eventuala rearanjare a lor, in vederea testarii lor pentru adaugarea acestora la B.