Tehnici de Programare

LIMBAJUL DE PROGRAMARE JAVA

Java este un limbaj de programare de nivel înalt, dezvoltat de JavaSoft, companie în cadrul firmei Sun Microsystems.

Dintre caracteristicile principale ale limbajului amintim:

- simplitate, elimina supraîncarcarea operatorilor, mostenirea multipla si toate "facilitatile" ce pot provoca scrierea unui cod confuz.

- robustete, elimina sursele frecvente de erori ce apar în programare prin eliminarea pointerilor, administrarea automata a memoriei si eliminarea fisurilor de memorie printr-o procedura de colectare a 'gunoiului' care ruleaza în fundal. Un program Java care a trecut de compilare are proprietatea ca la executia sa nu "crapa sistemul".

- complet orientat pe obiecte - elimina complet stilul de programare procedural .

- usurinta în ceea ce priveste programarea în retea

- securitate, este cel mai sigur limbaj de programare disponibil în acest moment, asigurând mecanisme stricte de securitate a programelor concretizate prin: verificarea dinamica a codului pentru detectarea secventelor periculoase, impunerea unor reguli stricte pentru rularea programelor lansate pe calculatoare aflate la distanta, etc

- este neutru din punct de vedere arhitectural

- portabilitate, cu alte cuvinte Java este un limbaj independent de platforma de lucru, aceeasi aplicatie rulând, fara nici o modificare, pe sisteme diferite cum ar fi Windows, UNIX sau Macintosh, lucru care aduce economii substantiale firmelor care dezvolta aplicatii pentru Internet.

- compilat si interpretat

- asigura o performanta ridicata a codului de octeti

- permite programarea cu fire de executie (multitheaded)

- dinamicitate

- este modelat dupa C si C++, trecerea de la C, C++ la Java facându-se foarte usor.

- permite creearea unor documente Web îmbunatatite cu animatie si multimedia.

METODA APLICATA

Prezentarea algoritmului backtracking recursiv

Metoda backtracking se poate aplica unui mare numãr de probleme enumerative sau de optimizare cu solutie vectorialã pentru cã asigurã obtinerea tuturor solutiilor posibile pentru problema datã.

Totusi, ea se recomandã numai problemelor pentru care nu se cunoaste un

algoritm mai eficient (polinomial) sau problemelor de dimensiuni mici, la care timpul de rezolvare este încã acceptabil.

Un algoritm backtracking este un algoritm de cãutare sistematicã si exhaustivã a tuturor solutiilor, dintre care se pot alege apoi solutiile acceptate.

Cãutarea exhaustivã în arborele de solutii este un proces de încercare si revenire (de cãutare cu revenire).

Metoda de cãutare cu revenire construieste progresiv un vector solutie, începând cu valori[0] si continuând cu valori[1], valori[2],... pânã la valori[n-1], astfel încât componentele valori[i] sunt numere naturale dintr-o multime finitã valori[i]={1,2,...,n-1} si suma componentelor vectorului solutie este egala cu n ,cu conditia de unicitate impusa (valori[i] >= valori[i-1]).

Pentru fiecare componentã a vectorului solutie se încearcã toate valorile posibile valori[i]={1,2...n-1} Functia 'bkt' se apeleazã în programul principal cu parametrul k=0, ceea ce corespunde faptului cã procesul de aflare a unei solutii începe cu cãutarea unei solutii pentru componenta valori[0].

Procedura recursivã este scrisã astfel încât sã înceapã prin a verifica dacã s-a obtinut o solutie completã. In acest caz functia bkt este apelatã si pentru valori ale lui k = n-1, dar se iese imediat dupã prima instructiune if.

Functia, bkt, poate fi exprimatã recursiv (mai compact), astfel :

private void bkt (int k) {

if (k = = n - 1 && sumaCurenta = = n)

afisareSolutie(k);

for (int alfa = n; alfa >= 0; alfa--)

if (posibil(alfa, k)) {

solutieB[k] = alfa;

sumaCurenta += alfa*valori[k]; //instructiunea include

bkt (k+1);

sumaCurenta -= alfa*valori[k]; // instructiunea exclude

}

}