LIMBAJUL TURBO PASCAL

LIMBAJUL TURBO PASCAL

Notiuni introductive.

Limbajul Turbo Pascal a aparut la inceputul anilor '70 si a fost elaborat de matematicianul N. Wirth.

Initial limbajul a fost conceput pentru predarea sistematica a disciplinei de programare a calculatoarelor (structuirile clasice din programarea structurala au fost transformate in instructiuni).

Cu timpul limbajul a inceput sa fie folosit si in activitatea practica de programare a calculatoarelor. Un rol fundamental pentru acestea l-a avut firma americana Borland, care pe langa 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 ale limbajului permit si realizarea programarii pe obiecte.

Observatii :

F         Orice cuvant poate fi scris cu litere mici sau mari deoarece limbajul Turbo Pascal nu face diferente ;

F         In versiunea Turbo prima linie a programului poate lipsi (desi nu este recomandabil acest lucru, din ratiuni de ordine) ;

F         Plasarea cuvintelor pe linie si numarul de spatiu dintre ele sunt la alegerea programatorului (putem sa scriem intreg programul pe o singura linie insa este bine ca programul sa fie scris in asa fel incat sa fie usor de inteles).

Orice limbaj de programare se caracterizeaza prin sintaxa si semantica.

Sintaxa limbajului este data de totalitatea regurilor de scriere corecta (in sensul acceptarii sale de programul traducator, compilator, care are rol de a converti programul in cod masina pentru a fi executat).

Prin semantica unui limbaj intelegem ce anume realizeaza fiecare instructiune a sa. Sintaxa formalizata perfect din punct de vedere matematic dar nu acelasi lucru se intampla cu semantica. Sintaxa poate fi deschisa cu ajutorul diagramelor de sintaxa, in esenta intr-o diagrama de sintaxa putem inlocui urmatoarele simboluri grafice .

Exemplu : In program trebuie realizata atribuirea y :=2*x+1. 2 si 1 sunt constante.

Elementele care constituie vocabularul acestor limbaje sunt: setul de caractere , identificatori , operatori , separatori , comentarii .

Setul de caractere

Limbajul Pascal nu face distinctia intre literele majuscule si cele minuscule (de exemplu:Da,da,dA,DA reprezinta aceeasi informatie in limbajul Pascal).

Identificatori

Prin identificatori intelegem o succesiune de litere,cifre si caracterul '_' (underscore).

Exemple :

a aha vali t SORin

xYb InDex auxil tlt2t3 sTeLiAN

x_1  numitor Andr eMil Ion_sOfIA

Operatori,separatori,comentarii

Cu ajutorul simbolurilor speciale se definesc: operator de atribuire, operator de indici, comentariu.

Tipuri de date standard

Datele vehiculate in dialogul om-calculator, fie ca sunt constante, fie ca sunt variabile, pot fi de urmatoarele cinci tipuri de baza: tipul intreg (numere intregi), tipul real (numere reale), tipul alfanumeric (sir de caractere), tipul boolean (logic), tipul pointer si tipul enumerare. Aceste categorii de date sunt numite tipuri simple , in opozitie cu tipurile structurate.

a)Tipul INTEGER

In PASCAL, tipul integer, permite reprezentarea, memorarea si prelucrarea numerelor intregi. Teoretic, acestea pot avea valori absolute, oricat de mari, dar reprezentarea datelor in cadrul calculatorului nu permite existenta seturilor de numere infinite.

Limbajul Pascal, implementeaza aceasta restrictie furnizand in mod automat un identificator de constanta, Masant, a carui valoare reprezinta cel mai mare numar ce poate fi continut de o variabila de tip integer.

Operatiile aritmetice efectuate asupra valorilor de tip integer vor fi executate corect de catre calculator numai daca toti operanzii si toate rezultatele intermediare sunt cuprinse in intervalul "-Masant" pana la "+Masant". Numerele de tip integer sunt scrise la o secventa de cifre zecimale, precedate de semnul '-', pentru a indica un numar negativ, de nici un semn sau de semnul '+', pentru a indica un numar pozitiv.

Operatori aritmetici - ce se pot aplica asupra valorilor de tip integer :

-(*) - cu semnificatia de ' inmultire' ;

-(div) - cu semnificatia de 'impartire si trunchiere' ;

-(mod) - cu semnificatia de 'modulo' ;

- cu semnificatia de 'adunare' ;

- cu semnificatia de 'scadere' ;

Operatorul 'dire' realizeaza operatia de impartire a unui numar intreg prin alt numar intreg si indeparteaza partea fractionara a rezultatului,astfel incat operatia ne furnizeaza tot un numar intreg.

a)      -cu inteles de 'egal cu';

b)      '< >' -cu inteles de 'diferit';

c)      '< ' -cu inteles de 'mai mic decat';

d)      '<=' -cu inteles de 'mai mic sau egal cu';

e)      ' >=' -cu inteles de 'mai mare sau egal cu';

f) ' > ' -cu inteles de ' mai mare decat';

O expresie este, fie o expresie simpla, fie o comparatie, dupa cum se arata si in diagramele de sinteza.

Aceasta reprezentare genereaza doua consecinte :

1)in Pascal, operatorii de comparatie, au cel mai scazut nivel de prioritate in raport cu toti ceilalti operatori ;

2)comparatiile duble, cum ar fi x<=y<=z, nu sunt permise ca atare si trebuie implementate in alt mod.

Expresii logice care contin mai multe operatii

Operatorii cu ajutorul carora putem scrie astfel de expresii se numesc operatori logici si sunt cuvinte-cheie :

-ond -cu inteles de 'si logic' ;

-or -cu inteles de 'sau logic' ;

- not -cu inteles de 'negare logica'.

Operatorul 'mod', asigura obtinerea ca rezultat a restului impartirii unui numar intreg prin alt numar intreg. Incercarea de a calcula restul in cazu l impartirii unui numar intreg la zero genereaza mesaj de eroare.

Functiile standard care lucreaza cu valori de tip integer si genereaza rezultate de acest tip sunt :

-abs(x) rezultatul reprezinta valoarea absoluta a lui x ;

-sqr(x) rezultatul reprezinta valoarea lui x la puterea a-II-a ;

Alte functii standard care genereaza rezultate de tip integer :

-trunc(x) rezultatul reprezinta partea intreaga a numarului real x,partea fractionara fiind indepartata ;

-round(x) rezultatul reprezinta valoarea numarului real x rotunjita pana la urmatorul intreg.

b)Tipul Boolean

Are valoarea true (adevarat), daca conditia este indeplinita, altfel, conditia are valoarea false (fals).

Tipul Boolean este format din multimea valorilor logice false si true.

Valorile unuei variabile booleane rezulta in urma unei operatii de comparatii.Valorile comparate pot fi de orice tip darn u este permisa compararea valorilor de tipuri diferite.

In Pascal exista o gama larga de operatori de comparative, dar deoarece unele dintre simbolurile matematiceconventionale nu figureaza in setul de caractere al celor mai multe dintre sistemele de calcul,se folosesc conventii de notatii.In Pascal se inched intre paranteze toate comparatiile folosite ca operanzi ai operatiilor logice:and, or, not.

In limbajul Pascal valorile de tip logic nu pot fi citite.In limbajul Pascal,exista relatii de ordonare pentru toate tipurile de variabile inclusive pentru tipul logic.Se considera ca false<true.

Prioritatea operatiilor logice este urmatoarea:

-a) not;

-b) and;

-c) or ;

Functiile standard care furnizeaza rezultate de tip logic sunt:

-add(x) rezultatul este true(adevarat), daca x este un intreg impar; astfel este false;

-eolu(h) rezultatul este true(adevarat), daca s-a ajuns la sfarsitul linii a fisierului;

-eof(f) rezultatul este true(adevarat), daca s-a ajuns la sfarsitul fisierului f.

Ultimele doua functii noi pot fi explicate mai detaliat intr-unul dintre capitolele urmatoare.

c)Tipul REAL;

Numarul de cifre zecimale ale unui numar real ce poate fi memorate in calculator este limitat. Exista o limita a marimii numerelor reale si o limita a preciziei de reprezentare a acestora.

In Pascal numerele reale pot fi exprimate fie cu ajutorul notatiei conventionale a fractiilor zecimale, fie cu ajutorul notatiei stiintifice, care permite scrierea unor numere foarte mari sau foarte mici.

Operatorii ce pot fi folositi sunt urmatorii:

a)"+" -cu inteles de "adunare";

b)"-" - cu inteles de "scadere";

c)"*" - cu inteles de "inmultire";

d)"/" - cu inteles de "impartire de tip real".

Functiile standard care accepta un parametru de tip real si furnizeaza rezultatele de tip intreg:

-round(x) calculeaza valoarea lui x rotunjit la cel mai apropiat intreg;

-trunc(x) calculeaza valoarea lui x, trunchita la partea intreaga.

Reguli ce se aplica in cazul tipului Pascal

a)Deoarece fiecare numar intreg are un numar real, expresiile de tip real contin operanzi de tip intreg;

b)Este permisa atribuirea de valori intregi variabilelor de tip real;

c)Operanzii de tip real, nu pot fi folositi in expresii de tip intreg.

d)Tipul CHAR(character)

Este cel mai obisnuit mod de comunicare. Cele mai uzate seturi de caractere sunt:

-ASCII (ISO) contine 128 caractere;

-EBCDIC  contine 256 caractere (dublul setului ASCII).

Un caracter cuprins intre apostrofuri reprezinta o constanta de tip char. Penrtu a reprezenta caracterul apostrof, acesta se scrie de doua ori.

Conventia de a inchide caracterele intre apostrofuri se foloseste numai in cadrul textului unui progrtam Pascal, fiind necesara pentru a se putea farce distinctia intre valoarea caracter si simbolurile folosite in program. EA nu se foloseste insa in timpul executiei programului la introducerea datelor de tip caracter. Diferitele seturi de caractere au diferite moduri de ordonare.

In cazul setului ASCII cifrelor zecimale apar inaintea literelor, in timp ce in cazul setului EBCDIC, ordinea este inversata. In cadrul acestei ordonari, fiecarui caracter ii corespunde un numar intreg, numit numar de ordine.

Functiile standard care permit vizualizarea se mai numesc si functii de transfer.

-ord( e ) furnizeaza ca rezultat numarul de ordine al caracterului in cadrul setului de caractere.

-chr(i ) furnizeaza ca rezultat valoarea caracterului cu numar de ordine e;

Alte functii standard ce pot avea argumente de tip char:

-pred(e) functia predecesor; furnizeaza ca rezultat caracterul ce preceda caracterul 'e' in setul dat;

-succ (e) functia successor; furnizeaza ca rezultat caracterul ce succede caracterul 'e', in setul dat.

Constante

Asa cum am afirmat, constantele sunt informatii care se autodefinesc, spatiul de memorie necesar pastrarii lor fiind rezervat si gestionat de mediul de programare.

Definirea constantelor

Cind o anume valoare apare in mod repetat este recomandabil a o 'boteza', mai ales in cazul in care ea are o scriere 'lunga'. De pilda, in loc sa folosim in mod repetat constanta 312.054973 o definim sub un nume iar la fiecare aparitie a acestei valori vom scrie numele ce i l-am dat. Definirea constantelor se face conform sintaxei :

const nume_variabila=valoare ;

Constante numerice de tip intreg sunt numere intergi in sensul matematic cunoscut.

Exemple:

-0

3 +3 -3

950 -4567 +43

Limbajul Pascal standard accepta numere intregi din intervalul

Constante numerice de tip real

Numerele reale se scriu apeland la exponenti ai bazei (asa numita scriere stintifica a numerelor reale). De pilda, putem reprezenta constanta reala 19.55 in nenumarate moduri:

0.1955E2 0.01955E3 1955E-2

De aici ideea de scriere in virgula mobila a numerelor reale. Din infinitatea manierelor de scriere, cea evidentiata se numeste forma normala, unica pentru orice constanta. Ea este caracterizata de faptul ca se reprezinta printr-un numar sub unitar (0.1955) cu cifra zecilor (prima dupa marca zecimala) diferita de zero. Reprezentarea in calculator a constantelor reale se face pornind de la formula normala:

mantisa E exponent

iar la tiparire, in lipsa informatiilor pentru formatare este utilizata forma normala.

Constante logice(booleene)

Acestea sunt, de fapt, constante simbolice, fiind desemnate prin cuvintele :

false - corespunzatoare valorii logice fals (desemnata prin F in capitolul doi)

true - corespunzatoare valorii logice adevar (marcata cu A in acelasi capitol).

Reperezentarea in memoria calculatorului se face prin completarea cu valoarea 1 a zonei de memorie rezervate in cazul valorii logice adevar si, respectiv, cu 0 in cazul valorii logice fals (de aici relatia false <true).

Constante de tip alfanumeric

Aceasta categorie de constante reprezinta succesiuni de caractere ale limbajului (elemente din setul de caractere) avand sintaxa :

'succesiune de caractere'

Pentru a introduce caracterul apostrof (intr-o constanta alfanumerica Pascal), se procedeaza ca in exemplul de mai jos:

'Emilia este ' serioasa' '

echivalent cu sirul

Emilia este 'serioasa'

Variabile

Ca si constantele, variabilele pot fi de tipurile amintite in paragraful anterior. Ele sunt desemnate prin identificatori alesi de programator, fiind recomandabil a fi sugestivi. In programe, orice variabila are un domeniu in care ia valori si pentru o utilizare corecta trebuie sa primeasca valori din domeniul respectiv.

Definirea variabilelor

Variabilele se declara utilizind sintaxa :

Var nume_variabila :tip_variabila ;

Variabilele numerice

Definitia acestora se face apeland in simbolurile integer, byte, shortint, word, longint pentru tipul intreg si real, single, double, extended pe tipul real, prin care sunt evidentiate domeniile de valori standard posibile pentru variabile. Tipurile single, double, extende necesita coprocesor matematic.

Variabilele alfanumerice

Variabilele alfanumerice pot fi de tip caracter (evidentiate prin terminalul char si reprezentate pe un octet) sau de tip sir de caractere (marcate prin terminalul string), in Pascal fiind reprezentate prin numarul de caractere necesare stocari sirului la care se adauga un caracter de control. In Pascal acest caracter se adauga in fata si reprezinta numarul de caractere.

Exemplu :

Daca avem secventele:

P :string ;

P:='Emi';

Atunci rezulta:

P[1]='E' p[2]='m' p[3]='i'

P[0]=3;

Variabile logice

Aceasta categorie de variabile este pusa in evidenta prin simbolul boolean.

Exemplu:

Var B: boolean.

Structura generala a unui program PASCAL

Doua sectiuni principale ale unui program scris cu ajutorul limbajului Pascal sunt sectiunea declarativa si sectiunea de instructiuni.

Sectiunea declarative  Sectiunea instructiunilor

Program Ariecerc ; begin

Const  Readln(Raza);

P_c=3,141596;  Aria:=P_i *sar(Raza);

Var Writeln(Aria);

Raza,aria:real; end;

1).Sectiunea declarative- poate cuprinde maximum sase alte sectiuni ,grupate astfel:

a)antetul programului -precedat de cuvantul cheie 'program';

b)sectiunea de declarare a antetului - definite cu ajutorul cuvantului cheie 'label' grupeaza declaratiile de etichete folosite pentru controlarea stricta a salturilor neconditionate generate in program de instructiunile 'geto';

c)sectiunea de declarare a constantelor, definite cu ajutorul cuvantului cheie 'const';

d)sectiunea de declarare a tipurilor,definite cu ajutorul cuvantului cheie 'type', grupeaza declaratiile de noi tipuri de variabile specifice utilizatorului;

e)sectiunea de declarare a variabilelor -definita cu ajutorul cuvantului cheie 'var', care grupeaza declaratiile de variabile;

f)sectiunea de declaratie de variabile si proceduri, care grupeaza toate declaratiile de functii si proceduri, precedate de cuvantul cheie 'function', respectiv 'procedure'.

2).Sectiunea instructiunilor- este delimitata de cuvintele cheie'begin' si 'end', care cuprinde toate instructiunile.

Subprogramele unui program Pascal au ele insele aceeasi structura.

Declararea fiecarui program este precedat de cuvantul cheie corespunzator.

ELEMENTE GENERALE

Nu se poate concepe un program care sa se bucure de atributul de "generalitate", in absenta asa numitelor "operatii de intrare/iesire" (citire/scriere).

Exemplele de mai jos vin in sprijinul afirmatiei precedente.

Sa consideram programul urmator :

exemplul 1

program juriu ;

var sigma,r,ro,g,h : real ;

begin

sigma :=0.0002 ;

r :=0.0005 ;

g :=9.81 ;

ro :=1000.0 ;

h:=(2*sigma)/(r*ro*g);

end.

Cea de-a cincea instructiune are un caracter general, insa daca dorim repetarea calculelor pentru o alta valoare de timp (alte valori sigma,r,ro,g,h) trebuie practic sa rescriem primele patru instructiuni. Programul scris astfel este extrem de rigid.

In fapt problema centrala a programului rezida in a scrie programul o singura data, insa astfel incat sa poata fi utilizabil (fara modificari ) pentru o gama cat mai larga de setari de date, de intrare astfel, in "programul" de mai sus trebuie sa asiguram o modalitate de introducere a datelor (sigma,r,ro,g) la fiecare rulare a programului. Procedurile read si readln nu vor permite acest lucru. Programul de mai sus pe langa lipsa generalitatii mai prezinta inca o deficienta : valoarea calculata ramane pur si simplu invizibila utilizatorului.

Pentru a rezolva acest tip de problema in pascal sunt prevazute procedurile write si writeln. Intr-o forma mai generala programul poate fi scris astfel :

read(sigma) ;

read(r) ;

read(ro) ;

read(g);

b:=(2*sigma)/(r*ro*g);

write(h);

Ilustrandu-se totodata faptul ca procedura poate accepta mai multi parametrii de intrare (in exemplul de mai sus sigma,r,ro,g). Toti acesti parametri ai procedurii read sunt variabile si fiecaruia i se atribuie prin citire o unica valoare. In mod similar, procedura write admite la randul sau mai multi parametrii putandu-se scrie de exemplu :

write(sigma,r,ro,g,h)

Insa spre deosebire de parametrii read, acestia pot fii expresii, nu doar simple variabile, tiparindu-se valorile acestor expresii.

Observatii :

Din punct de vedere al intrarilor si iesirilor exista doua modalitati de procesare a datelor :

Modul de lucru "batch" in care datele de intrare sunt pregatite in avans (de exemplu: perforatoarele de cartele) iar rezultatele sunt tiparite la imprimanta, acestea fiind returnate utilizatorului dupa ce programul si-a terminat executia ;

Modul de lucru interactiv in care datele de intrare sunt introduse pe terminalul de intrare in timpul executiei programului, iar rezultatele sunt accesibile utilizatorului imediat dupa producerea lor (prin afisarea pe display sau listarea la imprimanta) pe parcursul acestei executii.

REPREZENTAREA OPERATIILOR DE CITIRE/SCRIERE CU AJUTORUL FISIERELOR DE INTRARE/IESIRE.

Operatiile de intrare/iesire nu sunt altceva dacat transferul de date intre unitatile de intrare/iesire ale sistemului de calcul si memoria interna a calculatorului.

Fisier de intrare Memoria interna Fisier de iesire

Setul de date furnizat programului.

Setul de rezultate obtinute prin executarea programului.

Precizare :daca ne imaginam datele unui fisier amplasate intr-o anumita ordine si daca operatiile asupra datelor din fisier se efectueaza ordinea amplasarii, atunci spunem ca fisierul este secvential.

Limbajul Pascal asociaza identificatorii IMPUT, respectiv OUTPUT pentru fisierele standard de intrare, respectiv de iesire (de obicei intrarea se efectueaza de la tastatura, iar prntru iesirea standard se asociaza fie afisajul catodic-diplay-ul - fie imprimanta).

Un fisier de intrare/iesire este alcatuit din una sau mai multe linii, fiecare linie continand cel putin un caracter. O linie este subdivizata in computer si se termina printr-un caracter special, numit terminator de linie.

Reprezentarea unui fisier de acest tip (numit si fisier text) poate fi  :

|174 293|///|-50 22 29|///|-39|///|

in care s-au marcat prin hasurare terminatorii de linie, caractere prin fapt invizibile operatorului. Precizam ca acesti terminatori de linie sunt introdusi in fisierul de intrare la apasarea tastei RETURN (CT+LF). Dincolo de reprezentarea de mai sus (cu un anumit grad de abstractizare), reprezentarea pe care o vom folosi in cele ce urmeaza, putem sa ne imaginam si reprezentari mai complete pentru fisierele de intrare/iesire, dupa cum urmeaza :

v     in cazul perforarii de cartele, ca in figura ;

-50 22 29

174 293

v     la afisarea pe display sau la tiparirea pe hartie;

174 293

-59 22 29

Considerand prima dintre aceste trei reprezentari, putem discuta in detaliu despre procedurile standard I/O (iesire/intrare) ale Limbajului Pascal.

Prin procedura intelegem un program scris intr-o forma speciala astfel incat sa poata fi apelat dintr-un alt program, acesta din urma furnizand procedurii un set de parametrii de intrare.

Procedura read

Procedura read are ca forma generala:

Read ([f]var1[var2,,varN]);

In care s-au inclus intre paranteze drepte parametrii optionali ai procedurii. Imaginam si reprezentari mai concrete pentru fisierele intrare/iesire dupa cum urmeaza :

• in cazul perforarii de cartele;

Se observa ca numarul de parameti de apel pentru aceasta procedura nu este fix.

Prin f s-a notat numele fisierului de intrare. In cazul in care nu este precizat la apel, se considera implicit fisierul standard de intrare (IMPUT)(maniera de lucru cea mai utilizata).

STRUCTURI DE CONTROL

Instructiunile limbajului Turbo Pascal transcriu aceste structuri de control, transformand programarea structurata intr-o activitate care decurge natural,firesc.

Instructiunile Turbo Pascal sunt urmatoarele:

• Instructiunea de atribuire;
• Instructiunea compusa;
• Instructiunea IF;
• Instructiunea CASE;
• Instructiunea WHILE;
• Instructiunea REPEAT;
• Instructiunea FOR;
• Instructiunea GO TO;
• Instructiunea WITH;

• Instructiunea procedurala (de apel procedura).

Structura liniara

Structura liniara cuprinde operatii care se executa secvential.

Aceasta structura este generata de instructiunile de atribuire, procedurale sau compuse.

Instructiunile de atribuire

Executia acestei instructiuni consta in :

se evalueaza expresia;

variabila primeste valoarea expresiei;daca tipul expresiei nu coincide cu cel al variabilei, valoarea expresiei se converteste inainte de atribuire in tipul identificatorului.

In Pascal Standard, cu exceptia cazului c), nu se fac conversii de tip in timpul executiei atribuirii.

Exemple :

a) Var i,j :integer ;

b :boolean ;

b :=i+j=7 ;  b primeste valoarea TRUE daca i+j este 7

si FALSE in caz contrar.

b) Var i :integer ;

a :real;

i:=a;  Atribuirea este gresita:variabilei de tip

intreg nu i se poate atribui  o valoare

reala; atribuirea corecta este:

i:=TRUNC(A) SAU I:=ROUND(A).

c) Var i,j,k:integer;

i:=j/k;  Operatorul / furnizeaza rezultat de tip

real, chiar daca operanzii sai sunt

intregi,deci atribuirea este gresita,Se

corecteaza: i:=j div k.

d) const caracter='a';

valoare:real=0.125;

caracter:='b'; Atribuire incorecta, deoarece caracter nu este identificator de variabila, ci de constanta.

Valoare :=valoare+1 ; Atribuirea este corecta, deoarece valoarea este o variabila initializata in Const (o constanta cu tip);

Valoarea devine 1.125.

INSTRUCTIUNEA COMPUSA

Executia instructiunii compuse consta in executia instructiunilor cuprinse intre delimitatori BEGIN si END, in ordinea in care acestea apar.

Instructiunea compusa permite utilizarea mai multor instructiuni in instructiunile structurate a caror sintaxa impune prezenta unei singure instructiuni.

Sectiunea de program a blocului are forma instructiunii compuse.Orice program Pascal cuprinde cel putin o instructiune compusa.

Instructiunea compusa poate cuprinde alte instructiuni compuse incluse in ea,delimitate si ele de cuvintele cheie BEGIN si END,a caror grupare respecta regula parantezelor din matematica.

Caracterul ";" separa instructiunile, deci nu le termina si nu face parte din instructiuni. Din diagrama, se observa ca inainte de END un exista " ; ", dar daca totusi se pune, nu se semnaleaza eroare, intrucat se considera ca s-a introdus o instructiune vida, care nu implica nici o actiune.

Instructiunea while

Descrierea generala a instructiunii while este urmatoarea:

while conditie

do instructiune;

Prin exemplele ce urmeaza incercam sa va facem sa scrieti programele Pascal corect sintactic, dar nu numai. Caci este o mare bucurie pentru programatorul caruia ii merg aplicatiile de la prima rulare.

Exemplu

Se considera n numere intregi.Memorand numai cate unul, sa se determine suma algebrica a celor ce preced pe primul zero furnizat.

Facand o mica analiza a problemei observam ca exista posibilitatea ca prima valoare ce odan sa fie zero. In aceasta eventualitate trebuie spus ca ''Primul element este zero'' si, ca atare, nu se pune problema unei sume. O alta situatie ar fi aceea cand nu exista o valoare nula. Deci aici necesitatea precizarii ''Toate elementele date au fost nenule''.

Asadar, algoritmul ce rezolva aceasta problema are trei iesiri (raspunsuri posibile):

mesajul ''Primul element este zero'';

mesajul ''Toate elementele date au fost nenule''

mesajul sumei elementelor ce preced primul zero furnizat.

program problema_1;

var

n,x,suma,i:integer;

begin

write('numar de valori:');

readln(n) ;

i:=1;

readln(x) ;

if x=0

then

writeln('primul elem zero')

else

begin

suma:=x;

while (i<n)and(x<>0)do

begin

readln(x);

suma:=suma+x;

inc(i);

end;

if x=0

then

writeln('suma celor',i-1,'valorieste',suma)

else

writeln('toate elementele nenule');

end;

end.

Instructiunile repeat/until

Sintaxa acestor instructiuni este :

PASCAL : repeat/until

repeat

instructiune1;

instructiune2;

instructiunen;

until conditie;

Instructiunea repeat/until, implementeaza in limbajul Pascal, permite executia unei multimi de instructiuni pana la indeplinirea unei conditii.

Instructiunea do/while, specifica limbajului C, permite executia unei instructiuni simple sau a unei instructiuni compuse atata timp cat o anumita conditie este indeplinita.

Exemplu

Sa se spuna cati dintre termenii sirului 0, 1, 1, 2, 3, 5, 8, 13, sunt cuprinsi intr-un interval [a,b], cu a, b numere naturale date.

Observam ca sirul are proprietatea ca a1=0, a2=1 si ca an=an-2 + an-1, cu n=3,4,5,

Acest sir este cunoscut ca fiind sirul lui Fibonacci de ordinul doi (se dau primii doi termeni, iar ceilalti sunt generati asa cum am precizat).

Cu aceste consideratii credem ca putem sa va propunem programul numit Fibonacci pentru solutionarea acestei prime probleme.

program fibonacci;

var

a, b, nr, x1, x2, x3:integer ;

begin

write('a=');

readln(a);

write('b=');

readln(b);

x1:=0;

x2:=1;

if a <= x1

then nr:=2

else if a=x2

then nr:=1

else nr:=0;

repeat

x3:=x1+x2;

x1:=x2;

x2:=x3;

if(x3>=a)and(x3<=b)

then inc(nr);

until x3>b;

writeln('numarul de termeni este:',nr);

end.

Instructiunea for

In cazul instructiunilor while cu numarul de reluari predeterminabil se poate apela la o variabila de tip intreg numita, variabila de control a ciclului, cu evolutia de la o valoare initiala vi la una finala vf. Evolutia poate fi crescatoare (vi,vi+1,vi+2,,vf ; ramura cu to in diagrama sintactica ) sau descrescatoare (vi,vi-1,vi-2,,vf ; ramura cudownto a diagramei). In acest mod s-a ajuns la o noua structura repetitiva, numita for, a carei descriere este :

For variabila :=valoare_initiala_mica to valoare_finala_mare do instructiune;

sau

for variabila := valoare_initiala_mare downto val_finala_mica do instructiune;

Exemplu

Se considera sirul de numere naturale:

Sa se calculeze suma primilor n termeni , cu n dat de la tastatura.

program problema_1;

var

s, suma :word ;

n, i:integer;

begin

suma:=1;

s:=1;

write('n=');

readln(n);

for i:=1 to n do

begin

s:=.s+3;

suma:=suma+s;

end;

writeln('suma este:',suma)

end

Accesarea fiecarei intrari a listei se face pornind de la intrarea ce o precede. Apare insa o problema : in ce mod se pot marca si in ce mod pot fi accesate prima si respectiv ultima intrare ?

Adresa sau indicatorul asociat primei intrari poate fi memorat intr-o variabila declarata astfel :

Antet : Referinta ;

Pentru a marca ultima intrare a unei liste inlantuite (deci pentru a arata ca dupa aceasta nu mai urmeaza nici o alta intrare), limbajul PASCAL furnizeaza o valoare indicator aparte, NIL(cuvant cheie) care nu face referire la nici o locatie. In cazul exemplului prezentat anterior, marcarea ultimei intrari a listei inlantuite asociata grafului se face prin memorarea valorii NIL in campul Urmator corespunzator.

Observatie :prin memorerarea valorii NIL in variabila Antet se poate reprezenta o lista inlantuita vida,adica o lista care nu contine nici o intrare.

In limbajul PASCAL ,valorile de tip indicator pot fi atribuite sau pot fi comparate cu ajutorul operatorilor relationali = si <>. Ele pot fi folosite ca parametri ai subprogramelor si pot constitui rezultate ale functiilor.

De multe ori, in aplicatii apar probleme in care se cere gǎsirea unor solutii de forma x=x₁x₂ x_n unde x_i A, i = 1,.,n in care x₁.x_n trebuie sǎ indeplineascǎ anumite conditii.

Am putea sǎ generǎm toate combinatiile posibile de valori si apoi sǎ le alegem doar pe cele convenabile. Considerand multimile A = , aceste combinatii s-ar putea construi astfel: pentru fiecare valoare posibilǎ fixatǎ pentru componenta x_i, vom alege toate valorile posibile pentru componenta x_i+1 si pentru fiecare astfel de valoare fixatǎ pentru x_i+1 vom alege toate valorile posibile pentru componenta x_i+2, etc.

Rezolvand problema in acest mod, deci generind tote elementele produsului cartezian si verificand abia apoi dacǎ fiecare combinatie este o solutie, eficientǎ este scǎzutǎ.

Astfel, dacǎ de exemplu ne propunem sǎ generǎm toate cuvintele formate cu litere a,b,c, asa incat fiecare literǎ sǎ aparǎ o singurǎ datǎ, combinatiile posibile sunt in numǎr de 27, dintre care convin doar 6.

Tehnica Backtracking propune generarea solutiei prin completarea vectorului x in ordine x₁x₂ x_n si are la bazǎ un principiu "de bun simt": dacǎ se constatǎ cǎ avand o combinatie partialǎ de formǎ v₁v₂v _k-1 (unde v_i,.,v_k-1 sunt valori deja fixate), dacǎ alegem pentru x_k o valoare v_k si combinatia rezultatǎ nu ne permite sǎ ajungem la o solutie, se renuntǎ la aceastǎ valoare si se incearcǎ o alta (dintre cele netestate in aceastǎ etapǎ). Intr-adevǎr, oricum am alega celelalte valori, dacǎ una nu corespunde nu putem avea o solutie.

Pentru exemplu ales anterior se observǎ cǎ dacǎ notǎm cuvantul cu x₁x₂x₃, combinatia aax₃ nu ne poate conduce la o solutie (literele trebuie sǎ fie distincte) si deci nu are sens sǎ mai incercǎm sǎ stabilim valori pentru x₃.

Altgoritmul general

al metodei Backtracking

Pentru evitarea generǎrii combinatiilor neconvenabile se procedeazǎ astfel:

Presupunem cǎ s-au gǎsit valorile v₁v₂.v_k-1 pentru componentele x₁x₂ x_k-1 (au rǎmas de determinat valorile pentru x_k.x_n). ne ocupǎm in continuare de componenta x_k. Pasii urmati sunt:

Pentru inceput, pentru x_k nu s-a testat incǎ nici o valoare.

Se verificǎ dacǎ existǎ valori netestate pentru x_k

a)      In caz afirmativ, se trece la pasul 3.

b)      Altfel, se revine la componenta anterioarǎ, x_k-1; se reia pasul 2 pentru k=k-1.

Se alege prima valoare v dintre cele netestate incǎ pentru x_k.

Se verificǎ dacǎ acestǎ combinatie partialǎ v₁v₂.v_k-1v ne poate conduce la un rezultat (dacǎ sunt indeplinite anumite conditii de continuare).

a)      Dacǎ valoarea aleasǎ este bunǎ se trece la pasul 5.

b)      Altfel, se rǎmane pe aceeasi pozitie k si se reia cazul 2.

Se verificǎ dacǎ s-a obtinut o solutie .

a)      In caz afirmativ, se tipǎreste aceastǎ solutie si se rǎmane la aceeasi componentǎ x_k, reluandu-se pasul 2.

b)      Altfel se reia altgoritmul pentru urmǎtoarea componentǎ (se trece la pasul 1 pentru k=k+1).

Altgoritmul incepe prin stabilirea unei valori pentru componenta x₁(k=1) si se incheie cand pentru aceasta am testat toate valorile posibile si conform pasului 2b) ar trebui sǎ revenim la componenta anterioarǎ, care in aceast caz nu existǎ.

Rezumand, metoda Backtracking se foloseste in rezolvarea problemelor care indeplinesc conditiile:

solutia poate fi pusǎ sub forma unui vector S=x₁x₂.x_n, unde x_i

multimile A_i sunt finite si ordonate (pentru a lua in considerare toate valorile posibile).

Inainte de a scrie programul care ne va obtine solutiile, trebuie sǎ stabilim unele detalii cu privire la:

vectorul solutie - cate componente are, ce mentine fiecare componentǎ.

multimea de valori posibile pentru fiecare componentǎ (sunt foarte importante limitele acestei multimi).

conditiile de continuare (conditiile ca o valoare x[k]sǎ fie acceptatǎ).

conditia ca ansamblul de valori generat sǎ fie solutie.

Pe baza acestor date vom scrie apoi procedurile si functiile pe care le vom apela in altgoritmul general al metodei, dat mai jos, care se poate aplica tuturor problemelor ce respectǎ conditiile mentionate anterior. Aceste proceduri si functii au o semnificatie comunǎ, prezentand insǎ particularitǎti in functie de fiecare problemǎ in parte.

Astfel, se va nota cu x vectorul care contine solutia; x[k] = v va avea ca semnificatie faptul cǎ elementul al-v-lea din multimea de valori ppsibile A_k a fost selectat pentru componenta x_k. dacǎ multimea A_k are m elemente, a₁a₂.a_m,pentru usurintǎ ne vom referii la indicii lor 1,2,.,m. Deci valorile posibile pentru o componentǎ vor fi 1,2,.,m in aceastǎ ordine.

Initial, cand pentru o componentǎ nu am testat incǎ nimic, aceasta va avea valoarea 0 (un indice care nu existǎ). Aceastǎ operatie se va realiza in procedura INIT care va avea ce parametru pozitia k.

Functia EXISTA(k) verificǎ dacǎ ultima valoare aleasǎ pentru componenta x_k nu a atins limita maximǎ admisǎ (indicele de valoare maximǎ). Intrucat elementele sunt testate in ordine, acest lucru este echivalent cu a verifica dacǎ mai avem valori netestate incǎ pentru aceastǎ componentǎ.

Functia CONT(k) verificǎ dacǎ valoarea aleasǎ pentru x[k] indeplineste conditiile de continuare, deci dacǎ aceastǎ combinatie partialǎ v₁v₂.v_k poate sǎ conducǎ la o solutie.

Functia SOLUTIE(k) verificǎ dacǎ s-a ajuns la o solutie finalǎ.

Procedura TIPAR(k) tipǎreste o solutie.

Altgoritmul propus este:

procedure BKT;

var k:integer;

begin

k:=1;

INIT(k);

while k>0 do

if EXISTA(k) then

begin

x[k]:=x[k]+1;

VALPOS(k);

if CONT(k) then

if SOLUTIE(k) then

TIPAR(k)

else

begin

k:=k+1;

INIT(k);

end;

end

else

k:=k-1;

end;

De asemenea, trebuie sǎ avem in vedere cǎ altgoritmul general se poate modifica si adapta in functie de problema rezolvatǎ.

Metoda Backtracking generalizat are urmǎtoarea deosebire fatǎ de metoda obisnuitǎ de Backtracking: in metoda obisnuitǎ vectorul solutie este un tablou unidimensional, x₁,x₂.x_n, fiecare componentǎ avand o anumitǎ valoare la un moment dat, dar dacǎ componenta x_k are mai multe caracteristici atunci este nevoie folosirea metodei generalizate.

In acest caz vectorul x trebuie sǎ descrie aceste caracteristici. Valorile posibile ale unei componente trebuie generate in ordine, dar pentru cǎ o valoare are mai multe caracteristici vom utiliza o variabilǎ auxiliarǎ cu ajutorul cǎreia vom nota (si vom obtine) in ordine toate aceste valori posibile.

Astfel, pentru a genera toate valorile posibile pentru o componentǎ k este suficient sǎ generǎm toate valorile posibile pentru aceastǎ variabilǎ auxiliarǎ si pe baza lor sǎ aflǎm valorile lui x[k].

De exemplu dacǎ x este vectorul solutie, iar d vectorul auxiliar, putem descrie un tip de bazǎ pentru o componentǎ astfel:

const nmax=20 ;

type component=record

caract1: tip1;

caract2: tip2;

end;

var x:array[1..nmax] of component;

d:array[1..nmax] of integer;

Un altgoritm general ar putea fi:

procedure BKTG;

var k:integer;

begin

k:=1;

INIT(k);

while k>0 do

if EXISTA(k) then

begin

d[k]:=d[k]+1;

VALPOS(k);

if CONT(k) then

if SOLUTIE(k) then

TIPAR(k)

else

begin

k:=k+1;

INIT(k);

end;

end

else

k:=k-1;

end;

Procedura INIT va initializa datele referitoare la componenta k-practic va initializa componenta corespunzǎtoare din vectorul auxiliar, d[k].

Functia EXISTA verificǎ dacǎ mai existǎ valori netestate incǎ pentru componenta k (practic dacǎ mai existǎ valori posibile pentru componenta corespunzatoare din vectorul auxiliar).

Procedura VALPOS va completa pentru componenta k in vectorul solutie valoarea caracteristicilor sale, in functie de valoarea lui d[k].

CONT, SOLUTIE, TIPAR au aceeasi semnificatie ca si in cazul metodei simple.

Se considera multimea . Se cer toate partitiile acestei multimi. Amintim ca submultimile A1,A2,,An ale uni multimi A constitue o partitie a acesteia, daca sunt disjuncte intre ele (nu au elemente comune) si multimea rezulta in urma reuniunii lor este A.

O partitie a multimii se poate reprezenta sub forma unui vector ST cu n componente. ST(i)=k are semnificatia ca elementul i al multimii considerate apartine submultimii k a partitiei.

Exemplu: A=, St= reprezinta partitia: , . O partitie a unei multimi cu nelemente este unic formata din cel mult n multimi distincte, caz in care fiecre element al multimii este unic in submultimea sa. Rezulta, de aici, ca St(i) apartine multimii. In realitate, pentru a evita repetitia partitiilor, facem conventia:

St(1)- ia numai valoarea 1;

St(2)- ia valorile 1,2;

St(n)- ia valorile 1,2,,n.

Aceasta inseamna ca elementul 1 va apartine numai submultimii 1 a partitiei, elementul 2 va apartine submultimii 1 sau 2 a partitiei, etc. O alta cerinta este aceea ca oricare ar fi i ce apartine multimii , sa existe j apartinand aceleiasi multimi, astfel incat modulul diferentei dintre St[i] si St[j] sa fie cel mult egal cu 1. Aceasta corespunde faptului ca submultimile unei partitii se numeroteaza cu numere consecutive.

Contraexemplu: A=, St= ar avea semnificatia ca prima multime a partitiei este , iar a treia multime este , in acest caz neexistand multimea a doua.

Demonstram ca intre multimea vectorilor St generati in acest mod si multimea partitiilor multimii exista o corespondenta biunivoca.

1) Fie o partitie oarecare a multimii considerate. Construim vectorul St astfel:

pentru toate elementele i care se gasesc in aceeasi multime cu elementul 1, St(i) capata valoarea 1;

pornind de la elementul 2 si considerand elementele in ordine crescatoare , se cauta primul element care nu apartine submultimii unde se gaseste elementul 1;

pentru aceasta, ca si pentru toate elementele care sunt in submultime cu el, St(i) va lua valoarea 2;

incepand cu elementul 3 si considerand elementele in ordine crescatoare, se cauta primul element care nu apartine primelor doua submultimi;

Procedeul continua in acest mod, pana cand sunt analizate toate elementele multimii considerate. In acest mmod , am demonstrat ca aceasta corespondenta este surjectiva. Pe de alta parte , la doua valori diferite ale vectorului St corespund partitii diferite, deci corespondenta este injectiva.

Suntem asadar in masura sa generam toate partitiile multimii , generand toate valorile posibile vectorului St, in conditiile considerate. Pentru fiecare valoare a vectorului St, in procedura TIPAR se tiparesc succesiv partitiile obtinute.

Pentru generarea valorilor vectorului St, se foloseste metoda backtracking. Din acest motiv vectorul ST este privit ca stiva. Elementul aflat pe nivelul k al stivei se poate majora pana la maximul dintre precedentele, plus 1. Avem solutie cand am gasit succesorul pe nivelul n. Exemplificam functionarea lgoritmului pentru multimea :

Nivelul 1 capata valoarea 1 ;

Nivelul 2 ia valoarea 1;

Obtinem prima valoare ce corespunde unei solutii si o tiparim

Se obtine solutia , ;

Nivelul 3 nu are succesor ; se coboara in stiva si se gaseste

succesorul nivelului 2 ;

se obtine solutia , ;

se obtine solutia , ;

solutia : ,, .

Pe nici un nivel nu avem succesor, deci se va cobori la nivelul 0 al stivei.

Se citeste un numar natural n. Se cere sa se tipareasca toate modurile de descompunere a sa ca suma de numere naturale.

Exemplu : n=4. Avem : 1111, 112, 121, 13, 211, 22, 31, 4.

Observatie. Ordinea numerelor din suma este importanta, astfel se tipareste 112 dar si 211, 121.

Pentru rezolvare, vom observa ca nivelul 1 al stivei ia valori intre 1 si n, nivelul 2 ia valori intre 1 si n-1, in general, nivelul k ia valori intre 1 si n-k+1 (SUCCESOR). O solutie partiala este valida daca suma elementelor pe care le contine este mai mica sau egala cu n (VALID) si am obtinut o solutie atunci cand aceasta suma este egala cu n.

Listing - ul programului

partitii in limbajul Pascal

type stiva= array[1..100]of integer;

var st: stiva;

opt:char;

as,ev: boolean;

n,s,k,i,j:integer;

Procedure antet;

begin

writeln ('Proiect pentru atestare profesionala ');

writeln;

writeln ('Tema : Elemente de combinatorica ');

writeln;

writeln ('= generarea partitiilor unei multimi= ');

writeln;

writeln ('Elev : Neatu Stefan Mirel ');

writeln;

writeln ('Prof. indrumator: prof.Paraschiv Niculina ');

writeln;

end;

procedure init( var st: stiva;k: integer);

begin

st[k]:=0;

end;

procedure succesor(var as: boolean;var st: stiva; k: integer);

var s1:integer;

begin

if (st[k] < n-k+1 )then begin

st[k]:=st[k]+1;

as:=true;

end

else as:= false;

end;

procedure valid ( var ev: boolean; st: stiva; k: integer);

begin

s:=0;

for i:=1 to k do s:=s+st[i];

if s<=n then ev:=true

else ev:=false;

end;

function solutie( k: integer): boolean;

begin

solutie:= (s=n) ;

end;

procedure tipar;

var i: integer;

begin

writeln('solutia.');

for i:= 1 to k do write( st[i]) ;

writeln;

end;

procedure generare_submultimi;

type vector= array[ 1..10] of byte;

var k,n,i,j: byte;

ig: boolean;

v: vector;

procedure generare ( var v: vector; k: byte; var ig: boolean);

var j,i:byte;

begin

for j:= k downto 1 do

if v[j] < n-k+j then begin

v[j] := v[j]+1;

ig:=true;

for i:=j+1 to k do

v[i]:=v[i-1]+1;

exit;

end;

end;

procedure scrie ( v: vector;k: byte);

var I:byte;

begin

write ('');

end;

begin

write ('n='); readln (n);

writeln (' multimea partitiilor multimii #10#13 ');

for k:=1 to n do begin

for i:=1 to k do v[i]:=i;

scrie (v,k);

repeat

ig:=false;

generare(v,k,ig);

if ig then scrie (v,k);

until not ig;

end;

end;

begin

antet;

repeat

write ('optiunea dvs?'); readln (opt);

case opt of

'A','a': begin

writeln('n=');

readln(n);

writeln('partitiile numarului intreg ',n);

k:= 1;

init(st,k);

while k>0 do begin

repeat

succesor(as,st,k);

if as then valid(ev,st,k);

until (not as) or ( as and ev);

if as then if solutie (K) then tipar

else begin

k:=k+1;

init(st,k);

end

else k:=k-1;

end;end;

'B','b': begin

generare_submultimi ;

end;

end;

until (opt='T') or(opt='t');

end.

Rezultatul obtinut

in urma rularii programului

Borland Pascal Version 7.0 Copyright (c) 1983,92 Borland International

Proiect pentru atestare profesionala

Tema : Elemente de combinatorica

= generarea partitiilor unei multimi=

Elev : Neatu Stefan Mirel

Prof. indrumator: prof.Paraschiv Niculina

Generarea partitiei unei multimi - tastati A

Generarea partitiei numarului dat - tastati B

Pentru terminare  - tastati T

optiunea dvs?a

n=

partitiile numarului intreg 2

solutia.

solutia.

optiunea dvs?b

n=3

multimea partitiilor multimii

optiunea dvs?t