TURBO PASCAL

Elementele de baza ale limbajului PASCAL

Evolutia limbajelor de programare cunoaste trei mari perioade distincte de timp si anume: anii 1950-1959, 1960-1969, dupa 1970.

Anii '50 reprezinta etapa de pionierat in domeniul programarii calculatoarelor. În aceasta perioada s-a cristalizat notiunea de program. Initial, programele erau scrise 14514g616o in cod masina (instructiunile, datele intrare - iesire formate din succesiuni de 0 si 1, asa cum, de fapt, le prelucreaza orice calculator din lume). Datorita acestui fapt, scrierea programelor, introducerea datelor erau activitati deosebit de migaloase si foarte putin productive. Un pas important in evolutie este dat de aparitia limbajelor de asamblare. Acestea folosesc pentru fiecare instructiune in cod masina, o abreviere in limba engleza ce sintetizeaza efectul instructiunii respective. Desi mult usurata , activitatea de programare într-un limbaj de programare ramâne destul de dificila. Cu toate acestea, si astazi limbajele de asamblare sunt folosite cu succes datorita unor avantaje cum ar fi posibilitatea scrierii unor programe specifice calculatorului pe care se ruleaza un anumit program (deci cu mare viteza de executie); posibilitatea scrierii unor secvente de program care nu pot fi scrise într-un limbaj evoluat din cauza lipsei de instructiuni specifice; etc.

In aceasta perioada apar si limbajele de nivel înalt cum ar fi FORTRAN si COBOL. De aceasta data scrierea programelor se face cu ajutorul unei expresii din limba engleza (desi extrem de restrictive). De asemenea, formulele prin care se solicita calculul unor expresii sunt asemanatoare expresiilor matematice. Un mare avantaj al limbajelor de nivel înalt îl constituie portabilitatea programelor scrise cu ajutorul lor (posibilitatea ca un program sa poata fi rulat pe diferite tipuri calculatoare).

In anii '60 se dezvolta cu precadere aparatul matematic necesar creari si utilizarii limbajelor de programare. Astfel, regulile de scriere a programelor în limbajele respective sunt formalizate matematic. De asemenea, apare conceptul de recursivitate in programare (acest concept era utilizat de mult timp in matematica). Pentru prima oara apare notiunea de utilizare dinamica a memoriei (alocarea spatiului de memorie pentru diverse variabile se face in timpul executiei programului, atunci când este cazul si tot in acest timp se poate sterge un spatiu alocat, când nu mai este necesar). Toate acestea apar pentru prima data în limbajul ALGOL. Acest limbaj, mai putin utilizat de practicanti, a avut un rol esential in dezvoltarea ulterioara a informaticii. Tot in aceasta perioada au aparut si alte limbaje evoluate care s-au raspândit în întreaga lume.

Dupa 1970 La începutul anilor 1970 a aparut programarea structurata (initiatorii ei fiind E.W.Dijkstra si C.A.Hoare). Pentru prima data apar metode standardizate de elaborare a programelor, activitatea de programare depasind stadiul artizanal. Redactarea oricarui program se poate face folosind câteva structuri simple (secventiala, alternativa, repetitiva). O problema complexa se descompune în subprobleme, care apoi la rândul lor se descompun din nou, pâna sunt suficient de simple pentru a fi transpuse în programe (programare descendenta).

La sfârsitul anilor '80 apare un nou concept, si anume programarea pe obiecte (în care datele si rutinele pentru ele sunt unificate în obiecte care se pot utiliza ca atare sau dezvolta ulterior fara a fi nevoie de a lua munca de la capat sau de a le cunoaste mecanismul lor intim). Timpul va decide daca acestea vor deveni sau nu indispensabile in activitatea de programare

Limbajul Pascal - a aparut la începutul anilor '70 si a fost elaborat de matematicianul N.Wirth. Initial, limbajul a fost conceput pentru predarea sistematica a disciplinei de programare a calculatoarelor (structurile clasice din programarea structurala au fost transformate in instructiuni). Cu timpul limbajul a început sa fie folosit si în programarea calculatoarelor. Un rol fundamental pentru aceasta la avut firma americana Borland, care a implementat o noua varianta numita Turbo Pascal, care, pe lânga instructiunile clasice ale limbajului contine si multe altele. Un mare avantaj al acestui limbaj este acela ca utilizatorul are posibilitatea sa-si declare propriile tipuri de date. Ultimele versiuni permit programarea pe obiecte.

Structura unui program Pascal

Structura unui program pascl este urmatoarea:

Program <nume dat de utilizator> antetul programului

zona de declaratii a programului

begin

"corpul programului" (zona operativa)

Vocabularul limbajului Pascal este format din:

¤ setul de caractere;

¤ identificatori;

¤ separatori;

¤ comentarii.

Printr-un identificator intelegem un nume asociat unei constante, variabile, proceduri sau functii. Un identificator poate contine numai litere, cifre, caracterul special "_" si trebuie sa inceapa obligatoriu cu o litera.

Exemplu:

A2, B, VAL_MEDIE

O categorie speciala de identificatori este reprezentata de cuvintele cheie al limbajului:

Exemplu:

PROGRAM, BEGIN, UNTIL, TO, DOWNTO, PROCEDURE, etc.

În cadrul unui program, o succesiune de caractere luate împreuna au o semnificatie bine definita numita unitate lexicala. Unitatile lexicale pot fi diferentiate între ele prin separatori. Separatorii pot fi dupa caz: blanc (spatiu caracterul de sfârsit de linie (EOL), caracterul " ", etc.

Constante în Pascal.

Constantele sunt valori care nu se modifica în cadrul programului. Constantele în limbajul Pascal sunt de 6 tipuri:

constante întregi;

constante reale;

constante caracter;

constante sir de caractere;

constante simbolice;

constante logice.

Constantele întregi sunt numere întregi ce pot fi reprezentate în baza 10 sau 16;

Constantele reale sunt numere reale cuprinse între 3.4*10^-4352 si 1.1*10⁴⁹³²;

Constantele caracter: orice limbaj de programare contine un set de caractere propriu. Setul de caractere folosit de limbajul Pascal se numeste setul ASCII si contine litere, cifre si caractere speciale;

Constantele sir de caracter sunt sirurile de caractere de orice fel din setul ASCII, care se pot scrie în 2 forme;

Constantele simbolice sunt numele care se pot atribui unor valoriconstante de orice tip;

Constantele logice:- TRUE reprezinta valoarea de adevar  ADEVĂRAT;

FALSE reprezinta valoarea de adevar FALS.

Variabile. Declararea variabilelor.

Spre deosebire de constante, o variabila este o data ale carei valori se pot modifica la fiecare noua executie a programului sau chiar în timpul unei executii. Orice variabila are asociat un anumit tip.

Tipuri de baza (standard):

tipuri întregi - BYTE;

WORD;

SHORTINT;

INTEGER;

LONGINT.

tipuri reale - SINGLE;

REAL;

DOUBLE;

EXTENDED.

tipul carcater - CHAR;

tipul logic - BOOLEAN.

Tipuri ordinale definite de utilizator:

tipul enumerat;

tipul subdomeniu.

Tipuri structurate:

tipul tablou (ARRAY);

tipul multime (SET);

tipul sir de caractere (STRING);

tipul înregistrare (RECORD);

Tipul unei date variabile defineste multimea variabilelor pe care le poate lua valoarea respectiva.

Operatorii limbajului Pascal.

operatori aritmetici:

(+), (-), (*), (/), (DIV), (MOD).

operatori relationali

(=), (<=), (=>), (<), (>).

operatori logici

AND (si logic), OR (sau logic), XOR (sau exclusiv), NOT (nu logic).

operatorul de atribuire:

Expresii în Pascal.

În timpul executiei unui program, la întâlnirea unei expresii, calculatorul evalueaza expresia respectiva, adica în acel moment variabilele din componenta expresiei au niste valori, calculatorul va înlocui în expresie variabilele cu valorile lor si se va obtine valoarea expresiei. Într-un program Pascal putem folosi 2 tipuri de expresii:

expresii aritmetice care contin operatori aritmetici si în urma evaluarii valoarea lor este un numar;

expresii logice (BOOLEENE):

o expresie booleana contine operatori de orice fel: operatori logici, aritmetici, relationali si poate fi privita ca o conditie, adevarata sau falsa; valoarea unei expresii logice este true daca conditia pe care o defineste este adevarata sau false în caz contrar.

Proceduri si functii predefinite ale limbajului.

Anumite actiuni într-un program se pot realiza cu ajutorul unor proceduri si functii predefinite ale limbajului. Procedurile si functiile predefinite sunt de fapt secvente de instructiuni care au fost scrise de autorii limbajului. O procedura poate avea unul sau mai multi parametri

Parametrii sunt niste valori (constante, valori ale unor variabile sau valori ale unor expresii) de care procedura (functia) are nevoie pentru a se executa si pe care le transmitem când o apelam.

Cele mai folosite proceduri predefinite ale limbajului Pascal sunt:

pentru stergerea ecranului folosim CLRSCR fara nici un parametru;

pentru afisarea unor date pe ecran se foloseste WRITE sau WRITELN

Cu ajutorul procedurilor WRITE sau WRITELN se pot afisa constante de orice fel, valori ale unor variabile, valori ale unor expresii sau valori returnate de catre functii.

Subprograme.

În anumite situatii este necesarca o secventa de instructiuni sa se execute de mai multe ori în cadrul unui program, eventual cu alte date. O astfel de secventa poate fi cuprinsa în cadrul unui modul de program numit subprogram. Deci un program va contine cel putin un modul numit modulul principal pe lânga care pot exista alte module. Pentru a se executa instructiunile cuprinse într-un subprogram, acesta trebuie apelat din modulul principal sau din interiorul altui subprogram. Modulul din care se face apelul se numeste modul apelant. Modulul apelant poate sa transmita subprogramului pe care il apeleaza date numite parametrii. Subprogramul apelat receptioneaza acesti parametrii si îi foloseste atunci când se executa..

Orice subprogram are un identificator si, eventual, un set de parametrii.

Subprogramele pot fi de doua tipuri:

proceduri;

functii.

Proceduri.

Scriem o procedura care, primind ca parametrii din partea modulului apelant informatiile respective testeaza daca acestea sunt pozitive si:

în caz afirmativ afiseaza;

în caz contrar afiseaza mesajul de eroare.

Modulul principal stabileste valori concrete si apoi apeleaza procedura careia îi transmite ca parametrii respectivele valori.

Când se apeleaza procedura modulul apelant este abandonat temporar si se executa procedura. În timpul executiei procedurii, parametrii formali (simboluri, identificatori) sunt înlocuiti în tot corpul procedurii cu parametrii actuali (valori concrete). Dupa încheierea executiei procedurii se revine automat în modulul apelant, la linia imediat urmatoare celei care a facut apelul.

Domeniul de vizibilitate al variabilelor (constantelor).

Prin domeniul de vizibilitate al unei variabile se întelege zona din program în care este "vazuta" declaratia acesteia; adica zona de program în care este cunoscuta valoarea sa.

Daca o variabila a fost declarata într-un subprogram atunci valoarea sa este cunoscuta numai în interiorul subprogramului respectiv. O astfel de variabila se numeste locala.

Daca o variabila a fost declarata la începutul programului (în zona de declaratii a acestuia) atunci aceasta este "vazuta" în tot programul si se numeste globala.

Declaratia anticipata a unei proceduri.

O procedura trebuie plasata în cadrul programului inaintea modulului care o apleleaza. Pentru a putea scrie procedura dupa modulul apelant, trebui sa facem o asa numita declaratie anticipata a procedurii, cu directiv FORWRARD în zona de declaratii a programului.

Rolul stivei în executia subprogramelor.

Orice subprogram (procedura sau functie) foloseste o structura interna de date gestionata de catre limbaj numita stiva. În Pascal, functionarea stivei se bazeaza pe mecanismul LIFO (ultimul intrat, primul iesit). Cu alte cuvinte, extragerea valorilor din stiva se face în ordine inversa introducerii lor.

Consideram ca un program (subprogram) p apeleaza un subprogram s p se numeste modul apelant, iar s se numeste modul apelat). La apel se salveaza automat pe stiva contextul modului apelant p si adresa de revenire:

- contextul modulului apelant p cuprinde totalitatea variabilelor locale si a parametrilor transmisi prin valoare;

- adresa de revenire indica instructiunea (linia de program) din modulul apelant p la care se revine dupa executia subprogramului apelant s

Functii.

Ca si procedurile efectueaza anumite operatii, dar în plus o functie intoarce (returneaza) o anumita valoare. Tipul valorii returnate se precizeaza la declararea functiei, dupa enumerarea parametrilor. Valoarea returnata de functie poate fi folosita apoi în modulul apelant.

Vectorii

Notiunea de vector.

Limbajul Pascal permite memorarea tuturor elementelor unui sir într-o singura variabila indexata, în care fiecare element ocupa o anumita pozitie. Un sir de elemente de acelasi tip se numeste tablou unidimensional sau vector.

Vectorul astfel denumit apartine unui tip de date nou numit tipul array. Un element al unui vector se mai numeste si componenta a vectorului, iar pozitia unui element se mai numeste si indicele sau rangul elementului..

Declararea unui vector.

Un vector trebui declarat la fel ca orice variabila, în sectiunea de declaratii a programului. În declaratia trebuie sa apara: identificatorul vectorului (numele variabilei vector);

tipul de date din care fac parte indicii (pozitiile) elementelor;

tipul elementelor.

Din tipul de date al indicilor trebuie sa reiasa numarul maxim de elemente, adica cel mai mare numar de elemente care s-ar putea memora în vectorul respectiv.

Sintaxa declararii unui vector ca o variabila este:

[var]<id>:array[<ind> of <tip>;

<id> identificatorul (numele) variabilei vector;

<ind> tipul de date permis pentru indici;

<tip> tipul de date în care se incadreaza elementle vectorului.

Tipul de date pentru indici trebuie sa fie un tip ordinal (enumerat, subdomeniu, etc.) cu un numar finit de valori si poate fi anonim. În definirea acestuia pot fi folosite constante simbolice, dar nu pot fi folosite variabile.

Tipul elementelor poate fi orice tip predefinit sau definit de utilizator.

Tipul de date array este anonim (nu are nume), dar el poate fi denumit ca orice tip de date, cu ajutorul cuvântului cheie type:

Type vector=array [1..50] of integer;

Var v:vector;

Fisiere de date

Fisiere text

Notiunea de fisier data.

In timpul executiei unui program, datele cu care lucreaza acesta (constante sau valori ale variabilelor), sunt stocate în memoria intrena RAM si se pierd la închiderea executiei programului. Pentru a pastra permanent respectivele date, astfel încât sa le folosim la fiecare noua executie a programului, trebuie sa le memoram pe un suport extern (hard+disk, floppy, etc.), într-un asa numit fisier de date.

Din punctul de vedere al continutului, fisierele de date în Pascal se împart în trei categorii:

fisiere cu tip: componentele sunt toate de acelasi tip (predefint, sau definit de utilizator);

fisiere text: datele sunt memorate ca o succesiune de caractere;

fisiere fara tip: informatiile sunt stocate sub forma unor blocuri de octeti de dimensiune fixa;

cu acces secvential: pentru a accesa o anumita componenta trebuie parcurse toate componentele dinaintea acesteia;

cu acces direct: orice componenta poate fi accesata imediat prin intermediul numarului ei de ordine în fisier.

Notiunea de fisier text. Caracteristici.

Un fisier text contine una sau mai multe linii de caractere de lungime variabila. Fiecare linie mai putin ultima, se încheie printr-un "marcaj de sfârsit de linie" alcatuit din caracterele CR("Carriadge Return") si LF("Line Feed"). Sfârsitul fisierului este marcat prin caracterul EOF("End Of File").

Caracterele dintr-un fisier text pot fi atât caractere tiparibile (litere mari si mici, cifre, caractere speciale), cât si caractere netiparibile. Acestea din urma se mai numesc si caractere albe (CR, LF, spatiu, BACKSPACE, TAB, etc.).

Pentru a putea prelucra datele dintr-un fisier text acesta trebuie deschis, iar dupa încheierea prelucrarii fisierul trebui închis la loc. Accesul într-un fisier text se face secvential. Orice fisier text se caracterizeaza printr-o variabila speciala numita pointer de fisier care indica în orice moment primul caracter ce poate fi prelucrat.

Un fisier text poate fi scris atât cu ajutorul unui program, cât si manual (folosind un editor de texte, se editeaza fisierul ca si o sursa de program).

Creeare, deschiderea si închiderea fisierelor text.

Orice fisier, deci si un fisier text se caracterizeaza printr-un nume sub care este identificat de catre sistemul de operare (de obicei acesta este alcatuit din trei parti: numele propriu-zis dat de utilizator, caracterul punct si extensia care indica tipul fisierului). Pe de alta parte, într-un program un fisier text se declara ca o variabila de un tip predefinit numit tipul de date text: o astfel de variabila se mai numeste descriptor de fisier.

Exemplu: var f,g: text;

Pentru a putea folosi efectiv un fisier text într-un program, trebuie facta legatura între descriptorul de fisier (fisierul logic) si numele sub care este recunoscut de catre sistemul de operare (fisierul fizic). Aceasta legatura se numeste asignarea fisierului si se realizeaza cu ajutorul procedurii predefinite.

assign (<descriptor>, <nume_fisier>);

Parametrul <nume_fisier> este un sir de caractere care reprezinta calea de acces împreuna cu numele complet al fisierului.

Exemple:

assign(f, 'numere.txt'); asigneaza descriptorul f fisierului numere.txt, aflat în directorul curent;

assign(g, 'C:\bp\bin\numere.text'); asigneaza descriptorul g fisierului numere.txt, aflat pe partitia C, în directorul bp, în subdirectorul bin.

Dupa asignarea fisierului, pentru a putea fi prelucrat, acesta trebuie deschis. În urma deschiderii, pointerul de fisier se pozitioneaza la începutul fisierului, pe primul caracter. În functie de tipul operatiei efectuate asupra sa, un fisier text poate fi deschis în trei moduri:

pentru citire: folosim procedura

Exemplu: reset(f);

pentru scriere folosim procedura

Exemplu: rewrite(f);

pentru adaugare la sfârsit folosim procedura

Exemplu: append(f);

Dupa încheierea prelucrarilor asupra unui fisier, acesta trebuie închis. Închiderea unui fisier text se realizeaza cu procedura

Exemplu: close(f);

Citirea dintr-un fisier text.

Dintr-un fisier text putem citi valori ale unor variabile de tip caracter, sir de caractere si numeric.

Citirea dintr-un fisier text se face cu una din procedurile read sau readln, ca si citirea de la tastatura, numai ca apare un parametru în plus: descriptorul de fisier.

Sintaxa:

read(<descriptor>,<v1>,<v2>,.);

readln(<descriptor>,<v1>,<v2>,.);

<descriptor> descriptorul fisierului din care citim;

<v1>,<v2>,. identificatorii variabilelor care se citesc.

Citirea începe de la pozitia la care se afla pointerul de fisier. Dupa citirea tuturor parametrilor cu readln, pointerul va sari la începutul rândului urmator în fisier, iar dupa citirea cu read va ramâne acolo unde a ajuns.

Similitudinea cu citirea de la tastatura are o explicatie foarte simpla: la citirea de la tastatura sa asigneaza automat un asa numit "fisier standard de intrare", INPUT. Deci, daca la apelul procedurii read sau readln lipseste parametrul <descriptor>, acesta se considera implicit INPUT.

Citirea variabilelor de tip caracter.

În fiecare parametru de tip char se citeste caracterul la care se afla pointerul de fisier. Dupa citirea unui caracter, pointerul avanseaza la caracterul urmator.

Exemplu:

Fie fisierul f:  si apelurile

&$  readln(f,c1,c2);

readln(f,c3);

unde c1,c2 si c3 sunt variabile de tipul char.

Vor fi citite valorile: c1='&', c2='$', c3='#'.

Citirea variabilelor de tip caractere.

Într-o variabia de tip string se potea citi o succesiune de caractere din fisier. Citirea începe cu caracterul la care se afla pinterul si functioneaza astfel:

daca la declararea variabilei de tip string s-a precizat lungimea maxima, atunci în variabila respectiva se vor citi atâtea caractere cât este valoarea maxima;

daca nu s-a precizat lungimea maxima, atunci în variabila respectiva se vor citi toate caracterele pâna la sfârsitul rândului din fisier.

Exemplu:

Fie fisierul f: si apelul

'Limbajul Pascal' read(f,s);

unde s este o variabila de tip string.

Daca declaram , atunci va citi s='Limbajul';

Daca declaram , atunci va citi s='Limbajul Pascal'.

Citirea variabilelor de tip numeric.

O succesiune de caractere dintr-un fisier text poate fi citita într-o variabila de tip numeric, astfel: va citi sirul de caractere cuprins între doua caractere albes daca sirul contine numai caractere permise pentru un numar (cifre, caracterele '+','-' si punctul zecimal), atunci va transforma sirul în numar si va memora în variabila numarul obtinut; în caz contrar tentativa de citire esueaza. La citirea variabilelor de tip numeric , pointerul de fisier "sare" automat peste toate caracterele albe intâlnite.

Exemplu:

Fie fisierul f: si apelurile

-3.5 7 readln(f, x, a, b);

5M.6 readln(f, y, z);

unde a, b sunt de tipul integer, iar x, y, z de tipul real.

În urma primului apel se vor citi a=2, x=-3.5, b=7. În urma celui de-al doilea apel se va citi corect y=28.9, dar citirea valorii 5M.6 în z esueaza, deoarece aceasta valoare contine caractere nepermise unui numar.

Citirea variabilelor de tipuri diferite.

Printr-un singur apel al procedurii read sau readln se pot citi mai multe variabile de tipuri diferite, cu conditia respectarii cerintelor descrise mai sus.

Exemplu: consideram declaratiile var x:real; a,b:integer; ch:char; s:string[3]

Fie fisierul f:  si apelurile

-3 readln(f, x, s, a, ch, b);

Se vor citi: x=2.75, s='@#$', a=8, ch='*', b=-3.

Tehnici de programare

Metoda backtracking

Notiunea de stiva.

În timpul executiei unui program, limbajul Pascal gestioneaza si foloseste o strucutra de date interna numita stiva. Aceasta este organizata dupa principiul LIFO si are un rol bine definit: la apelul unui subprogram (procedura sau functie) se salveaza pe stiva contextul modulului apelant (alcatuit din variabile locale si parametri transmisi prin valoare) si adresa de revenire (linia din program la care se revine dupa executia apelului).

Adr în cadrul unui program, utilizatorul îsi poate defini propriile stive. Cel mai simplu mode de a implementa o stiva este cu ajutorul unui vector st. pentru a simula caracterul de stiva, privim vectorul st ca si cum elementele sale ar fi asezate "pe verticala", unul peste altul. Daca la un moment dat stiva contine elementele st[1], st[2], st[3],.,st[p], atunci pozitia p a elementului cel mai de sus, se numeste vârful stivei. În general, pozitia unui element în vectorul stiva este numita nivel al stivei.

Adaugarea si extragerea de elemente în din stiva, se poate fece numai pe la capatul de sus al acesteia:

adaugarea unui nou element în stiva înseamna cresterea cu o unitate a vârfului stivei (p:=p+1) si memorarea unui element st[p]pe noua pozitie p;

eliminarea (extragerea) unui element din stiva înseamna renuntarea la elementul aflat în vârful stivei, adica vârful stivei scade cu o unitate (p: p-1)

st[p]   P

St[2]

St[1]

Algoritmul backtracking, prezentare generala.

Metoda backtracking este o tehnica de programare, aplicabila algoritmilor care ofera mai multe solutii. Fiecare solutie se memoreaza într-o structura de date de tip stiva, implementata cu ajutorul unui vector.

Notam st vectorul sitva, nr numarul valorilor care alcatuiesco o solutie. În acest caz, o solutie a problemei va fi formata din elementele st[1],st[2],.,st[nr]

Într-un algoritm backtracking ne intereseaza toate solutiile posibile. Pentru a obtine fiecare solutie finala, vom completa vectorul stiva pas cu pas, nivel cu nivel, trecând astfel prin niste solutii partiale. În plus, atât solutiile partiale cât si cele finale, pentru a fi luate în considerare trebuie sa îndeplineasca anumite conditii, numite conditii de validare. O solutie care îndeplineste aceste conditii devine astfel solutie valida.

De retinut ca toate configuratiile stivei (st[1], st[2],.,st[p]) ce reprezinta solutii finale, sunt alcatuite din elementele aceleiasi multimi bine-definite pe care o vom denumi în continuare multimea solutiilor.

Fiecare noua solutie partiala, se obtine prin completarea solutiei partiale precedente cu înca un nivel pe stiva. La fiecare nivel, vom încerca sa punem pe nivelul respectiv valori din multimea solutiilor care nu au fos încercate înca, pâna când obtinem o solutie valida; în acest moment, "urcam" cu înca un nivel în stiva, pentru a completa mai departe solutia, dupa care reluam încercarile pe noul nivel.

Va aparea însa si urmatoarea situatie: la un moment dat, pe un anumit nivel, nu mai exista nici o valoare neîncercata din multimea solutiilor. În acest caz, vom face un pas înapoi, la nivelul anterior, si reluam cautarea cu valorile ramase neîncercate pe acces nivel anterior. Respectivul nivel a mai fost vizitat, dar l-am abandonat dupa ce am pus o valoare care a generat o solutie valida, deci se poate sa fi ramas aici valori neîncercate. Daca nici pe acest nivel nu mai avem valori neîncercate mai facem un pas înapoi, s.a.m.d. Mecanismul revenirilor a determinat denumirea "metoda backtracking".

Plecând de la nivelul 1 si repetând algoritmul pâna când pe toate nivelele au fost încercate toate valorile din multimea solutiilor, vom obtine solutii finale care evident se tiparesc.

Datorita faptului ca fiecare noua configuratie a stivei se obtine pornind de la precedenta, algoritmii backtracking se pot implementa foarte elegant într-o maniera recursiva. Putem scrie si programe nerecursive, dar acestea sunt mai laborioase, de aceea am ales varianta recursiva a metodei backtracking.

Procedura recursiva backtracking .

Prezentam structura unui program backtracking, cu exemplificare pentru problema generarii permutarilor de n elemente.

Vom nota vectorul sitva cu st. folosim urmatoarele subprograme:

Procedura citeste datele si initializeaza stiva.

În problema permutarilor:vom citi numarul de elemente n:

Write ('n=');

Readln(n);

Se initializeaza cu 0 toate elelmentele stivei, atâtea câte au fost declarate:

For i:=1 to 50 do st[i]:=0;

Functia va returna true daca solutia (st[1], st[2],..., st[p]) este valida, respectiv false în caz contrar.

În problema permutarilor: pentru ca noul element st[p] sa genereze solutia valida st[1], st[2],..., st[p]), este necesar ca valoarea st[p] sa nu se mai gaseasca pe nici unul din nivelele anterioare (1, 2,..., p-1). Folosim o vriabila booleana posibil pe care o va returna functia; intializam (presupunem initial ca solutia este valida, cautând apoi proba contrarie). Parcurgem într-un ciclu nivelele anterioare lui p, adica i=1, 2,..., p-1: daca gasim un element st[i] egal cu st[p], înseamna ca valoarea st[p] mai exista cel putin pe unul din nivelele anterioare, deci solutia obtinuta dupa adaugarea lui st[p] nu este valida.

Posibile:=true;

For i:=1 to p-1 do

If st[p]=st[i] then

Posibil:=false;

Procedura afiseaza solutia cu p nivele st[1], st[2],..., st[p]).

Parcurgem nivelele i=1, 2,..., p, afisând fiecare element st[i].

Algoritmul descris mai sus poate fi implemntat într-o singura procedura recursiva , care încearca sa completeze nivelul p al stivei.

Trecerea la nivelul urmator (când am obtinut o solutie partiala valida), se realizeaza prin auto-apelul recursiv bktr(p+1). În programul principal, facem primul ape bktr(1), deoarece plecam de la primul nivel al stivei. Astfel vom trece prin toate nivelele din interiorul bktr(1) se apeleaza bktr(2), din bktr(2) se apeleaza bktr(3), etc.

Procedure bktr (p:integer);

Var val:integer;

Begin

For val:=<v­_i> to <v_n> do (*1)

Begin

St[p]:=val;  (*2)

If valid(p) then (*3)

If <solutia este finala> then  (*4)

Tipar(p) (*5)

Else

Bktr(p+1); (*6)

End;

End;

într-un ciclu prin variabila val vor trece pe r\nd toate valorile care ar putea fi încercate pe nivelul p al stivei. Pentru fiecare din aceste valori:

maemoram valoarea respectiva val pe nivelul p al stivei, obtinând astfel solutia (st[1], st[2],..., st[p]);

verificam daca solutia generata este valida, testând valoarea returnata de functia valid(p).

daca aceasta solutie este valida (functia a returnat true), atunci trebuie sa verificam daca este si finala:

în caz afirmativ afisam solutia, apelând procedura tipar(p).

în caz contrar, fiind solutie partiala , trebuie sa trecem la nivelul urmator pentru a o completa, deci se auto-apeleaza recursiv back(p astfel, p+1 va deveni noul p la executia acestui apel).

Elementele de baza ale limbajului Pascal

Dezvoltarea limbajului pe anumite perioade:

Dezvoltarea între anii 1950 - 1960;

Dezvoltarea între anii 1960 - 1969;

1.1.3 Dezvoltarea dupa 1970;

Limbajul Pascal;

Structura unui limbaj Pascal:

Constante în Pascal;

Variabile. Declararea variabilelor;

Operatorii limbajului Pascal;

Expresii în Pascal;

Proceduri si functii predefinite ale limbajului;

Subprograme;

Proceduri;

Domeniul de vizibilitate al variabilelor (constantelor);

Declaratia anticipata a unei proceduri;

Rolul stivei în executia subprogramelor;

Functii;

1.3.1 Vectorii;

1.3.1.1 Notiunea de vector;

1.3.1.2 Declararea unui vector.

Fisiere de date

Fisiere de tip text:

Notiunea de fisier data;

Notiunea de fisier text. Caracteristici;

Creeare, deschiderea si închiderea fisierelor text;

Citirea dintr-un fisier text;

Citirea variabilelor de tip caracter;

Citirea variabilelor de tip caractere;

Citirea variabilelor de tip numeric;

Citirea variabilelor de tipuri diferite;

Tehnici de programare

Metoda backtracking

Notiunea de stiva;

Algoritmul backtracking, prezentare generala;

Procedura recursiva backtracking;

Exemplificare a procedurii backtracking.