ALGORITMI

1.1. Notiunea de algoritm, caracteristici.

 Def. Prin algoritm se întelege o metoda de solutionare a unei clase de probleme, reprezentata de o succesiune finita de operatii bine definite, numite instructiuni .

 Caracteristicile unui algoritm :

este descris clar, fara ambiguitati în privinta ordinii de executie a instructiunilor ;

este corect, deci este o metoda care rezolva problema pe orice caz (rezolva o clasa de probleme);

este finit, deci se termina dupa un numar finit de pasi, indiferent  cât de multi ;

este realizabil cu resursele disponibile .

Date, variabile, expresii, operatii

 1.2.1. Date

 Orice algoritm porneste de la anumite date de intrare, le prelucreaza, iar în final obtine date de iesire .

  Datele pot fi clasificate dupa tipul lor :

Întregi ;  ex. 120, -120

Reale ;  ex. 3.12, 12.3 (pentru despartirea zecimalei în loc de virgula se foloseste punctul )

Logice;  ex. TRUE(adevarat), FALSE(fals)

sir de caractere;  ex. 'un text' .

Datele din primele doua tipuri se numesc date numerice .

 1.2.2 Variabile

Tipurile de variabile coincid cu tipurile de date. Printr-o variabila întelegem un ansamblu de patru elemente:

Numele variabilei ;

Tipul ei ;

Valoarea ei la un moment dat ;

Locul în memoria calculatorului unde poate fi gasita variabila (adresa ei ).

1.2.3 Expresii

Cu ajutorul constantelor, variabilelor si operatorilor se pot construi diverse expresii. În scrierea 19119k109t expresiilor este permisa folosirea parantezelor.

Expresiile sunt de mai multe tipuri :

Întregi ;

Reale ;

Logice ;

De tip sir de caractere .

1.2.3.1 Expresii întregi

Folosesc operatorii +, -, * (pentru înmultire), DIV (pentru câtul împartirii întregi), MOD (pentru restul împartirii întregi) s.a.

Rezultatul evaluarii lor este un numar întreg .

Exemple :

3*x+7, unde x este variabila întreaga ;

a*(b+c), unde a, b, c sunt variabile întregi .

 1.2.3.2 Expresii reale

Operanzii care le alcatuiesc sunt constante si variabile întregi sau reale.Pe lânga operatorii utilizati în cadrul expresiilor întregi putem utiliza si altii cum ar fi de exemplu : '/' (pentru împartirea cu zecimale ). Rezultatul evaluarii lor este întotdeauna un numar real .

 1.2.3.3 Expresii logice

Rezultatul lor poate avea numai doua valori :TRUE sau FALSE .

Operatorii sunt cei din logica matematica : OR, AND, NOT .De asemenea este permis sa folosim si operatorii <, >, >= (mai mare sau egal), <= (mai mic sau egal), <> (diferit).

Exemple

a OR b, unde a si b sunt variabile logice ;

(a>=b) AND (c<d) .

 1.2.3.4 Expresii de tip sir de caractere

Se folosesc constante si variabile de tip sir de caractere .Singurul operator permis este operatorul + având semnificatia de concatenare (scrierea a celor doua siruri unul dupa altul ).

Exemplu :

a + 'text', unde a este o variabila de tip sir de caractere având continutul 'acest ' are ca rezultat sirul 'acest text' .

 1.2.4 Operatii

 Clasificare operatii :

Operatii de intrare si iesire ;

Operatii de atribuire ;

Operatii de decizie ;

 1.2.4.1 Operatii de intrare si iesire

Prin operatia de intrare ( de citire) se întelege preluarea unei datede la un dispozitiv de intrare (tastatura, unitatea de discheta, unitatea de disc) catre memoria interna a caculatorului, în spatiul rezervat pentru aceasta (spatiul rezervat pentru variabila care primeste ca valoare acea data ).

Prin operatia de iesire (scriere ) se întelege trecerea unei date din memoria interna catre un dispozitiv de iesire ( monitorul, unitatea de discheta, unitatea de disc) .

 1.2.4.2 Operatii de atribuire

Sa presupunem ca un algoritm foloseste o variabila notata arbitrar z si o alta notata y  .Dorim ca z sa ia o anumita valoare ( de ex. 2) .Spunem ca am atribuit variabilei z valoarea 2 si pentru moment vom nota acest lucru astfel : z:=2.Atât timp cât asupra variabilei z nu efectuam nici o alta operatie de atribuire si nu efectuam nici o operatie de citire, aceasta îsi pastreaza valoarea 2.Presupunem ca scriem valoarea variabilei z pe monitor .Dupa scriere variabila z va avea în continuare valoarea 2.Presupunem ca atribuim variabilei y valoarea variabilei z (y:=z).În urma atribuirii, valoarea variabilei y va fi 2 si valoarea variabilei z va ramâne 2. Daca atribuim variabile z valoarea z+z+7 (z:=z+z+7) atunci z va avea valoarea 11 .

Operatia de atribuire se efectueaza astfel :

Se evalueaza expresia din partea dreapta a operatiei de atribuire ;

Valoarea care se obtine astfel este preluata de variabila din partea stânga, iar valoarea avuta de aceasta se pierde .

 1.2.4.3 Operatii de decizie

În general, în functie de anumite conditii, trebuie facute anumite operatii sau altele. Operatia prin care testam acele conditii se numeste operatia de decizie. În functie de rezultatul testului, algoritmul executa anumite operatii. 

Structuri de baza(liniara,alternativa,repetitiva

Structurile : liniara, alternativa si repetitiva ;

Descrierea algoritmilor cu ajutorul schemelor logice si în pseudocod ;

Programarea structurata este o metoda independenta de limbajul de programare, ea actionând la nivelul stilului de lucru. Programarea structurata reprezinta o maniera de concepere a programelor potrivit unor reguli bine stabilite, utilizând un anumit set, redus, de tipuri de structuri de control .

Programarea structurata poate fi reprezentata ca o combinatie a trei structuri de control :

Secventa (succesiunea de doua sau mai multe operatii) ;

Decizia (alegerea unei operatii dintre doua alternative posibile );

Ciclul cu test initial (repetarea unei operatii atâta timp cât o anumita conditie este îndeplinita) .

Programarea structurata admite si utilizarea altor structuri de control, cum sunt :

Selectia (permite o alegere între mai mult de doua alternative ) ;

Ciclul cu test final ;

Ciclul cu contor .

Ultimele doua structuri de control reprezinta variante ale structurii referita în general ca 'iteratie'.

ELEMENTE DE BAZĂ

ALE LIMBAJULUI PASCAL

2.1 Vocabularul limbajului

Vocabularul oricarui limbaj este format din:

setul de caractere;

identificatori;

separatori;

comentarii;

 2.1.1 Setul de caractere

Reprezinta un ansamblu de caractere cu ajutorul caruia se poate realiza un program Pascal.

Acesta este alcatuit din:

litere mari si mici ale alfabetului englez(A-Z, a-z);

cifrele sistemului de numeratie în baza 10(0-9);

caractere speciale :+, - , * , / , = , ^ ,< ,>, ( , ) ,[ , ] , , ., , , : , ; , # , $ , @ , _ , si blanc(spatiu).

 2.1.2 Separatori si comentarii

Cele mai simple elemente alcatuite din caractere cu semnificatie lingvistica poarta denumirea de unitati lexicale. Acestea se separa între ele, dupa caz prin blanc, sfârsit de linie sau caracterul';'.

Pentru ca un program sa fie usor de înteles se folosesc comentariile. Acestea se plaseaza oriunde în program. Un comentariu poate fi scris în doua feluri în program:

între acolade; exemplu:;

între paranteze rotunde urmate de * ,exemplu: (*un comentariu*).

 
2.2 Constante. Identificatori

 2.2.1 Constante

 Constantele Pascal reprezinta valori care pot fi continute de un program scris în acest limbaj(nu sunt citite de program).Ele se folosesc în cadrul diverselor expresii (numerice, logice, siruri de caractere)sau pentru scrierea unor mesaje.

Exemplu: În program trebuie realizata atribuirea y:=2*x+1. În acest caz 2 si 1 sunt constante.

Constantele limbajului Pascal se împart în 4 categorii:

constante întregi;

constante reale;

constante sir de caractere;

constante simbolice;

 2.2.1.1 Constante întregi

Sunt alcatuite dintr-o submultime a numerelor întregi care pot fi reprezentate în memoria calculatorului.

Observatie: Nu se pot reprezenta în calculator numere oricât de mari sau oricât de mici (orice numar ocupa un spatiu în memoria interna a calculatorului).Prin utilizarea limbajului Turbo Pascal se pot reprezenta numere întregi cuprinse în intervalul [-2.147.483.648, 2.147.483.648]. Numerele se pot reprezenta în baza 10 sau în baza 16 (mai rar utilizata). Pentru baza 16, numarul este precedat de caracterul special '$'.

Exemple: 32,-164,+31,$a1.

2.2.1.2 Constante reale

Sunt alcatuite dintr-o submultime a numerelor reale(mai precis a numerelor rationale), care pot fi reprezentate în calculator. Numerele se gasesc în intervalul[3.4*10^-4352 ,1.1*10⁴⁹³²] . În locul virgulei se pune punct.

Exemple:2.34, -45.26, 512E+23, -45.1E-3.

Ultimele doua numere folosesc o scriere neîntâlnita în matematica. Ele reprezinta numerele 512*10²³si -45.1*10^-3.

 2.2.1.3 Constante sir de caractere

Dupa cum reiese si din denumire, cu ajutorul lor se reprezinta siruri de caractere. sirurile de caractere se pot reprezenta în doua forme.

În prima forma se scrie sirul cuprins între apostrofuri.

Exemplu: ' acesta este un text'.

În forma a doua se scrie în cod ASCII(fiecarui caracter i se ataseaza un cod cuprins între 0 si 255 si este precedat de caracterul '#').

Exemplu:#1#2 sau, echivalent(în baza 16), #$#$2.

 2.2.1.4 Constante simbolice

Acestea sunt constante care au în program un anumit nume. Numele dat acestor constante poate fi cunoscut de limbaj(de ex. : false, true, maxint )sau dat de utilizator atunci când defineste constantele.

 2.2.2 Identificatori

Prin identificatori întelegem o succesiune de litere sau cifre sau caracterul special' _' din care prima trebuie sa fie în mod obligatoriu litera. Cu ajutorul identificatorilor se asociaza nume constantelor, variabilelor, procedurilor etc.

Exemple de identificatori: a1, tasta, un_numar.

Contraexemple :1ar, mt&, (primul începe cu o cifra, al doilea contine un caracter special).

O categorie speciala de identificatori este data de cuvintele cheie ale limbajului(au un înteles bine definit si nu pot fi folosite în alt context).

Acestea sunt: AND, ARRAY, BEGIN, CASE, CONST, DIV, DO, DOWNTO, ELSE, END, FILE, FOR, FUNCTION, GOTO, IF, IN, LABEL, MOD, NIL, NOT, PROCEDURE, PROGRAM, RECORD, REPEAT, SET, OF, OR, ORIGIN, OTHERWISE, PACKED, THEN, TO, TYPE, UNTIL, VAR, WHILE, WITH.

2.3 Notiunea de tip de data. Operatori aritmetici, logici,relationali

Prin tip de data vom întelege o multime de valori. Pe tipurile de data se introduc anumite operatii.

Exemplu de tip de data. integer .

Avem trei categorii de tipuri :

simple

structurate

reper .

Tipurile simple de date se pot clasifica din doua puncte de vedere .

Un tip ordinal reprezinta o multime finita de valori între care exista o relatie de ordine. Conform acestui criteriu, tipurile simple se clasifica în :

tipuri ordinale ;

tipuri reale (chiar daca se ia o submultime a numerelor reale situata într-un anumit interval, acesta nu are un numar finit de elemente) .

Din punct de vedere al modului de definire a tipului, tipurile simple se clasifica în:

tipuri standard( este cunoscut, nu este necesar sa fie cunoscut de programator);

tipuri definite de utilizator.

2.3.1. Tipuri simple standard

Acestea se clasifica în :

tip boolean:

tip char;

tipuri întregi;

tipuri reale;

Dintre acestea primele trei sunt tipuri ordinale.

2.3.1.1 Tipul boolean

Are numai doua valori: true si false. Operatorii care lucreaza cu acest tip sunt: AND ,OR , NOT. În versiune Turbo a limbajului s-a introdus si operatorul XOR. Fiind date doua valori oarecare ale acestui tip, a si b, avem a XOR b = true daca si numai daca ele sunt diferite.

 2.3.1.2 Tipul char

Multimea valorilor acestui tip este formata de toate caracterele reprezentate în codul ASCII extins. Fiecare din aceste caractere se reprezinta pe un octet. Relatia de ordine între aceste caractere este data de relatia de ordine dintre codurile prin care se reprezinta (cuprinse între 0 si 255 ).Limbajul contine anumite functii care se pot aplica tipului char. Acestea sunt:

SUCC(caracter)- returneaza caracterul care are codul ASCII cu o unitate mai mare (succ('c')='d');

PRED(caracter)- returneaza caracterul care are codul ASCII cu o unitate mai mica (pred('d')='c' );

ORD(caracter)- returneaza codul ASCII a caracterului;

CHR(cod)- returneaza caracterul care are codul specificat.

2.3.1.3 Tipuri întregi

În functie de submultimea considerata a numerelor întregi ,avem urmatoarea clasificare :

tipul SHORTINT - numere din intervalul[-128,127] care se reprezinta în memoria interna pe un octet;

tipul INTEGER - numere din intervalul [-32768, 32767],se reprezinta pe doi octeti;

tipul LOGINT - numere din intervalul [-2.147.483.648, 2,147.483.648],se reprezinta pe 4 octeti;

tipul BYTE - numere din intervalul[0, 255],se reprezinta pe un octet;

tipul WORD - numere din intervalul [0, 65535],se reprezinta pe doi octeti.

Variabilelor de tip întreg li se pot aplica urmatorii operatori aritmetici: + ( adunare, operator binar), - (scadere ,operator binar), *(înmultire ,operator binar),DIV si MOD (operatori binari). În cazul a doua valori naturale (deci întregi pozitive),operatorii MOD si DIV furnizeaza restul si câtul împartirii întregi.

Exemple  14 DIV 5 =2;

 14 MOD 5 =4;

Daca cel putin un operand este negativ, lucrurile se complica.

Exemple -13 DIV 4 = -3;

 -13 MOD 4= -1.

stim din matematica faptul ca restul împartirii a doua numere întregi este pozitiv. În acest caz ,cei doi operatori nu furnizeaza rezultatul corect.

Pentru operatorul DIV rezultatul se obtine astfel:

se împart cele doua numere în valoare absoluta(pentru exemplu dat câtul este 3);

semnul câtului se stabileste dupa regula semnelor (+ cu + rezultat +, - cu + rezultat -, etc.).

Pentru MOD rezultatul se obtine din scaderea din deîmpartit a produsului dintre împartitor si cât (pentru exemplificare se calculeaza -13 - -4*3= -1).

Operanzilor de tip întreg li se pot aplica si operatorii pe biti (lucreaza asupra bitilor di reprezentarea interna a numarului).Acestia vor fi reprezentate în continuare.

Operatorul NOT ( operatorul unar)

Bitii care au valoarea 0 vor avea valoarea 1 si invers .

Exemplu: NOT 7= -8.

Presupunem numarul 7 reprezentat ca octet. El va arata astfel: 00000111. Aplicând operatorul NOT obtinem:11111000.Acesta reprezinta un numar negativ. Dupa cum stim pentru a obtine valoarea lui se transforma bitii cu 1 în biti cu 0,bitii cu 0 în biti cu 1. Rezulta:00000111+1=00001000.Ultimul rezultat este numarul 8,iar daca tinem seama ca era negativ,obtinem-8.

Operatorul AND(operator binar )

Fie continutul a doi biti, b1 si b2. Definim operatia de conjunctie asupra continutului lor, astfel:

  1,daca b1=1, b2=1 

 b1 and b2=. 

 0, în orice alt caz

Cu ajutorul lui AND se face conjunctia bit cu bit a celor doi operanzi.

Exemplu: 3 AND 7=3.

3 se reprezinta astfel: 00000011;

 7 se reprezinta astfel: 00000111;

 în final,rezulta:00000011, adica numarul 3.

Tema 1

Structura liniara

1. Sa se scrie un program care calculeaza media aritmetica a trei numere.

2. Ionel pleaca cu trenul la mare si doreste sa afle cât timp va dura calatoria. Pentru aceasta el îsi noteaza ora, minutul, secunda plecarii trenului precum si a sosirii. El nefiind prea bun la matematica va roaga pe voi sa-i calculati timpul ( în ore, minute si secunde) cât a durat calatoria.

3. Badea Ghe. are un petec triunghiular de pamânt pentru care trebuie sa plateasca impozit. El a masurat laturile gradinii sale si va roaga sa îi scrieti un program cu ajutorul caruia sa-si calculeze suprafata gradinii.

4. Sa se scrie un program care calculeaza valoarea unui polinom de gradul al doilea pentru o valoare data.

5. Scrieti într-o singura instructiune de atribuire urmatoarele doua instructiuni, astfel încât efectul sa fie acelasi: a:=a+b+c;

a:=a*c+b

6. Într-o încapere trebuie asezate mai multe cutii cubice una peste alta. Scrieti un program care cunoscând înaltimea încaperii precum si latura unei cutii determina câte cutii se pot aseza una peste alta.

Sa se scrie un program care citind un numar întreg, de cel putin doua cifre, afiseaza penultima cifra a acestuia.

Tema 2

Structuri alternative

1. Sa se scrie un program care determina daca un numar este par sau nu.

2. Ionel a primit ca tema sa scrie o lista cu toate numerele mai mici decât 100 care sunt pare, dar nu sunt divizibile prin 6. Pentru a-i usura munca va roaga sa-i scrieti un program care testeaza daca un numar dat respecta regula sau nu.

3. Sa se scrie un program care afiseaza maximul dintre trei numere.

4. Fie a, b, c salariile a trei persoane. Sa se scrie un program care precizeaza daca acestea sunt distincte sau nu.

5. Sa se scrie un program care citind trei numere le afiseaza în ordine crescatoare.

6. Scrieti un program care citind numele si salariile a 5 persoane ( salariile sunt distincte) afiseaza numele persoanei cu salariul cel mai mare.

7. Scrieti un program care rezolva ecuatia de gradul I.

8. Ionel are de rezolvat mai multe ecuatii de gradul doi. Pentru a termina mai repede tema el are nevoie de un program. Deoarece el nu stie decât sa utilizeze un calculator, va roaga pe voi sa scrieti acest program.

9. Sa se scrie un program care citind trei valori determina:

1. daca cele trei valori pot reprezenta laturile unui triunghi
2. daca cele trei valori reprezinta laturile unui triunghi, sa se determine natura triunghiului (echilateral, isoscel, dreptunghic, oarecare)

10. Sa se scrie un program care citind un numar n (0 =< n =< 9) afiseaza textual valoarea acestuia.

11. Sa se scrie un program care pentru un x dat calculeaza valoarea functiei:

            2X+5 , pentru X < -2

        f(x)=      3X-2 , pentru X >-2

             2X²+6 , pentru X < -5

f(x)=      7X , pentru -5 <X < 5

     X³-6 , pentru X >= 5

Structura repetitiva

Ciclul cu test initial (while - do)

Sintaxa:

While <expresie> do <secventa >

· <expresie> este o conditie (expresie logica), iar < secventa> este o secventa formata dintr-una sau mai multe instructiuni numite corpul ciclului;

Principiul de functionare al structurii

Cât timp este îndeplinita conditia data de <expresie> se executa corpul ciclului <secventa >

se evalueaza expresia logica < expresie >

- daca aceasta este adevarata atunci se executa secven ta <secven ta > , apoi se revine la 1. (între timp este posibil ca valoarea expresiei < expresie > sa fi suferit modificari)

- daca conditia impusa nu este adevarata, se trece la prima instructiune de dupa ciclu.

Observatie:

1. În cazul în care corpul ciclului contine mai multe instructiuni, acesta trebuie cuprins între "begin" si "end"
2. Testarea conditiei are loc la început, deci corpul ciclului poate sa nu se execute niciodata.

Ex de program care foloseste structura repetitiva cu test initial:

program suma;

var i,n,s,x:integer;

begin

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

s:=0; i:=1;

while i<=n do

begin

     write('x=');      readln(x);

     s:=s+x;

     i:=i+1;

end

writeln('s=',s);

readln

end

Program calculeaza suma a "n" numere naturale care se citesc pe rând de la tastatura. Numarul de numere, "n", se citeste de la tastatura. La fiecare executie a ciclului se citeste un numar "x" care se adauga la suma "s", apoi se incrementeaza contorul "i" care ne spune la a câta executie ne aflam. Variabila "i" se initializeaza cu 1, iar ciclul se executa cât timp i <= n. (se citesc n numere)

Structura repetitiva cu test final

Sintaxa:

Repeat <secventa > until <expresie>

· <expr> este o conditie (expresie logica), iar < secv > este o secventa formata dintr-una sau mai multe instructiuni, numita corpul ciclului

Principiul de functionare al structurii:

Repeta executia secventei de instructiuni < secventa > pâna când conditia logica data de <expresie> ia valoarea true.

1) se executa secventa de instructiuni <secv>

2) se evalueaza conditia logica deta de < expr >

- daca aceasta (< expresie > ) este adevarata atunci se executa secventa <secven ta > , apoi se revine la 1.

-daca conditia impusa nu este adevarata, se trece la prima instructiune de dupa ciclu.

Observatie:

1. În cazul în care corpul ciclului contine mai multe instructiuni, acesta nu mai trebuie cuprins între "begin" si "end"
2. Testarea conditiei are loc la sfârsit, deci corpul ciclului se va executa cel putin o data.

Ex de program care foloseste structura repetitiva cu test final:

· Program care calculeaza produsul numerelor naturale pare mai mici sau egale cu o valoare data

program produs;

var i,n:integer;

p:longint

begin

readln(n);

P: =1;

i:=2;

repeat

      p:=p*i;

      i:=i+2;

until i>n;

write('p=',p);

end

Ciclu cu numar cunoscut de pasi "FOR"

Sintaxa:

1. for <contor>: =<v1> to <v2> do <secventa >
2. for <contor>:=<v2> downto <v1> do <secven ta >

Variabila contor trebuie sa fie de tip ordinal (întreg, caracter, logic).

<v1> si <v2> sun t valori extreme ale contorului, iar <secv> este o secventa de instructiuni care reprezinta corpul ciclului. Daca corpul ciclului contine mai mult de o instructiune acesta trebuie cuprins între begin si end.

Observatii:

1. Valorile extreme sau limita ale contorului pot sa fie constante,valori ale unor variabile, valori ale unor expresii, valori returnate de functii etc.

2. În corpul unui "ciclu for", nu se va modifica contorul prin citire de la tastatura si nici prin atribuire.

Principiul de functionare al ciclului

1. Variabila < contor > ia pe rând toate valorile de la <v1> la <v2> în ordine crescatoare, si pentru fiecare valoare a lui <contor> executa corpul ciclului constituit de < secventa >;

Variabila < contor > ia pe rând toate valorile de la <v1> la <v2> în ordine descrescatoare, si pentru fiecare valoare a lui <contor> executa corpul ciclului constituit de < secventa >;

Exemplu de program care utilizeaza ciclul cu contor:

program cu_ contor;

var i,n :integer;

begin

readln(n);

for i:=1 to n do

write(i);

end

Programul citeste un numar "n" si scrie toate valorile întregi cuprinse între 1 si "n".