Cuprins

Gndirea algoritmic .............................................................. 1 Problema cutrii ............................................................................................................. 1 Problema intrrii ntr-un cabinet medical ..................................................................... 2 Tipuri de date .................................................................................................................. 3 Identificatori ................................................................................................................... 4 Constante ........................................................................................................................ 4 Variabil .......................................................................................................................... 4 Tipul Integer.................................................................................................................... 5 Tipul Real ........................................................................................................................ 5 Tipul Char........................................................................................................................ 5 Tipul Boolean .................................................................................................................. 6 Tipul String ..................................................................................................................... 6 Vectorul ............................................................................................................................ 7 Matricea (tablou bidimensional) .................................................................................... 9 nregistrarea (record) ..................................................................................................... 9 Fiierul text ....................................................................................................................10 Structuri de date de tip liste .......................................................................................... 11

Proceduri ...............................................................................13 Media aritmetic ............................................................................................................ 13 Ariile unor figuri geometrice ......................................................................................... 14 ir de numere n fiier ................................................................................................... 16 Laturi n triunghi ........................................................................................................... 16 Interschimbarea a dou linii ntr-o matrice .................................................................. 17

Funcii .................................................................................. 19 Media aritmetic al perechii de numere ...................................................................... 20 Suma cifrelor unui numr ............................................................................................ 20 Numr prim ................................................................................................................... 21 Elementele prime ale unui ir ....................................................................................... 22 Ordonarea a trei numere .............................................................................................. 23 Unghiuri n grade i radiani.......................................................................................... 23 Perechi de numere ........................................................................................................ 25 Frecvenele caracterelor ntr-un ir .............................................................................. 26 Platouri de lungime maxim ntr-un ir....................................................................... 27 Cel mai mare divizor comun ......................................................................................... 29

Recursivitate ......................................................................... 31 Conceptul de recursivitate ............................................................................................ 31 Inversarea unui cuvnt ................................................................................................. 31 irul Fibonacci ............................................................................................................... 32 Cel mai mare divizor comun ......................................................................................... 32 Funcia Ackermann ....................................................................................................... 33 Numrare ...................................................................................................................... 34 Anagrame ...................................................................................................................... 35 Generare ........................................................................................................................ 36 Conversie ....................................................................................................................... 37 Codul Gray ..................................................................................................................... 37 irul mediilor aritmetico-geometrice al lui Gauss ....................................................... 39 Evaluarea unei expresii aritmetice ............................................................................... 40

Metoda Divide Et Impera .................................................... 43 Cel mai mare divizor comun ......................................................................................... 43 Problema turnurilor din Hanoi ..................................................................................... 45 Problema tieturilor ...................................................................................................... 45 Algoritmi de cutare. Cutarea binar ......................................................................... 47 Merge Sort sortare prin inreclasare .......................................................................... 49 QuickSort - Sortare Rapid ............................................................................................ 51

Metoda BackTracking .......................................................... 53 Descrierea general a metodei ...................................................................................... 53 Probleme reginelor ........................................................................................................ 53 Generarea elementelor combinatorice ......................................................................... 55 Partiiile unei mulimi ................................................................................................... 58 Partiiile unui numr natural ........................................................................................ 60 Plata unei sume cu monede de valori date ................................................................... 61 Paranteze ....................................................................................................................... 63 Comis-voiajor ................................................................................................................ 64 Backtracking n plan ..................................................................................................... 67 Labirint .......................................................................................................................... 67 Fotografie ...................................................................................................................... 70 Cel mai lung prefix ......................................................................................................... 71

1

Gndirea algoritmic Problema cutrii Exist i cazul care, pentru o aceeai problem putem prezenta dou soluii, n care una este mai rapid ca alta. De pild, fie un ir de numere natural oarecare, de exemplu 4,2,10,1,8,15,7. Vream s testm dac un numr dat (s zivem numrul 8) se afl n aceast secven sau nu. O astfel de cutare, prin parcurgerea de a stnga la dreapta a ntregii secvene de numere, pn se gsete numrul dorit sau se epuieaz toate elementele din secven, se numete cutarea secvenial. Dac avem un ir S de n elemente (notat S[1..n]), atunci cutarea secvenial a lui x n S se descrie prin: Cutare_secvential(x,S[1..n]) nseamn nceput Fie elemental_curent = primul_element; Att timp ct (elemental_curent x) si (pozitia elementului current

2

Procedeul anterior se numete cutare binar, deoarece, de fiecare dat, o secven de numere este divizat n dou jumti. Putem descrie cutarea binar a unui numr x ntr-o secven S[1..n] astfel. Cutarea_binar(x, S[1..n]) nseamn nceput Stabileste elemental_curent ca fiind elemental din mijlocul secventei; Dac n=1 atunci Dac x = elemental_curent atunci mesaj(gsit) Altfel mesaj(negsit) Altfel nceput mparte secventa n cele dou jumtti (S[1..mijloc] si S[mijloc+1..n]); Dac elemental_curent = x atunci mesaj(gsit) Altfel Dac elemental_curent < x atunci Cutare_binar(x,S[mijloc+1..n]) Altfel cutarea_binar(x.S[1..mijloc]) Sfrit Sfrit.

Problema intrrii ntr-un cabinet medical Dac un om vrea s intre pentru consult la un medic, atunci, mai nti va bate la u: dac medicul rspunde prin poftim!, atunci va intra, atlfel va atepta pn cnd pacientul dinuntru va iei; abia dup ce cabinetul va fi liber, va intra. Intrare_la_medic nseamn nceput Bate la_u; Dac rspunsul = poftim! atunci ntr_n_cabinet; Altfel nceput Att timp ct cabinetul_este_ocupat_de_alt_pacient execut Citeste_un_ziar; Sfrit Sfrit. O intruciune compus este format dintr-o secven de intruciuni, ncadrate de cuvinte nceput i sfrit, care pot conine, la rndul lor, blocuri de alternativ i repetiie.

3

Programarea este tehnica realizrii de algoritmi descrii prin proceduri i programe. Ea devine o art, atunci cnd se folosesc cele trei elemente de structurate i se numete programare structurat. Pentru a vedea ce ar nsemna programare nestructurat, s reconsiderm procedura de intrare n cabinetul medical: Intare_la_medic nseamn nceput Bate_la_u; Dac rspunsul = poftim! atunci intr_n_cabinet; Altfel nceput Att timp ct cabinetul_este_ocupat_de_alt_pacient execut Citeste_un_ziar; ntr_n_cabinet Sfrit Sfrit.

Tipuri de date

ntr-o declaraie de forma procedure ordonare(n), n reprezint argumentul procedurii; adic procedura ordonare ordoneaz n elevi, unde s se va preciza ulterior. Noi convenim ca n s fie numr natural, chiar dac declaraia de mai sus nu rezult acest lucru. n limbajele evoluate de programare, fiecare argument, fiecare variabil are un anumit tip bine definit, adic poate lua valori dintr-o mulime precizat de valori.

n algoritmii simpli, putem folosi urmtoarele tipuri de date: Integer = mulimea numerelor ntregi Real = mulimea numerelor reale Char = caracter String = ir de caractere Boolean = logic

Byte 0 255 1 Byte

Word 0 65 535 2 Byte

Shortint 128 127 1 Byte

Integer 32 768 32 767 2 Byte

Longint 2 147 483 648 2 147 483 647 4 Byte

13

Proceduri

Media aritmetic Realizai un program care calculeaz i afieaz media aritmetic a dou numere reale x i y. Program Media_aritmetica; Var media,x,y:Real; Begin Write(Dati numerele:); ReadLn(x,y); Media:=(x+y)/2; WriteLn(Media=Media:8:2); ReadLn; End.

Cu Procedure...

Program Media_aritmetica; Var media,x,y:Real; Procedure media_calcul; Begin Media:=(x+y)/2; WriteLn(Media=,Media:8:2); End; Begin Write(Dati numerele:); ReadLn(x,y); media_calcul; ReadLn; End.

Procedura Media_calcul conine toate aciunile algoritmului: citirea numerelor, calcul i afiarea mediei aritmetice.

14

Program Media_aritmetica; Var media,x,y:Real; Procedure media_calcul; Begin Write(Dati numerele:); ReadLn(x,y); Media:=(x+y)/2; WriteLn(Media=,Media:8:2); End; Begin media_calcul; ReadLn; End.

Ariile unor figuri geometrice

Scriei un program care, n funcie de dorina utilizatorului, calculeaz i afieaz: aria unui ptrat de latur L, sau aria unui cerc de raz r, sau aria unui triunghi cu baza b i nlimea h. Pentru calcul i afiarea fiecreia din cele trei arii, se va folosi cte o procedur. Program aria; Const pi=3,14159; Var opt:Integer; Procedure aria_patrat; Var L:Integer; Begin Write(Latura L=); ReadLn(L); If L>0 Then WriteLn(Aria =,(L+L):6) Else WriteLn(Date incorecte!); End;

15

Procedure aria_cerc; Var r:Integer; Begin Write(Raza r=); ReadLn(r); If r>0 Then WriteLn(Aria =,(pi*r*r)) Else WriteLn(Date incorecte!); End; Procedure aria_triunghi; Var b,h:Integer; Begin Write(baza b si inalt h= ); ReadLn(b,h); If (b>0) and (h>0) Then WriteLn(Aria -, (b*h)/2) Else WriteLn(Date incorecte!); End; Begin WriteLn(Dati iptiunea dvs. ); WriteLn([1:patrat, 2:cerc , 3:triunghi] ); ReadLn(opt); Case opt Of 1:aria_patrat; 2:aria_cerc; 3:aria_triunghi; Else WriteLn(Date incorecte!); End; ReadLn; End.

19

Funcii La fel ca i procedurile, funciile efectueaz anumite operaii, dar n plus a foncie ntoarce o anumit valoare. Tipul valorii returnate se precizeaz la sfritul antetului finiei, fiind precedat de caracterul dou puncte. Valoarea pe care o returneaz o funcie poate fi folosit apoi n modul apelant i n celelalte module componente.

Sintaxa:

Function (:; :; ...; :): ; ... {declaraii de variabile locale} Begin ... {corpul funciei} End;

- identificatorul

,,..., - sunt liste de paramateri

,,..., - tipurile parametrilor

- tipul valorii returnate

Exemplu:

Program Media; Var x,y:Real; Function calcul(a,b:Real):real; Begin Calcul:=(a+b)/2; End; Begin Write(x,y=); ReadLn(x,y) ReadLn(Media=,calcul(x,y)); ReadLn; End.

20

Media aritmetic al perechii de numere Realizai un program care citete de la tastatur dou perechi de numere (x1,x2) i (y1,y2), calculeaz media aritmetic a numerelor fiecrei perechi, apoi determin cea mai mare dintre mediile obinute. Progam media_2; Var m1,m2,x1,x2,y1,y2:Real; Function calcul(x,y:Real):Real; Begin Calcul:=(x+y)/2; End; Begin Write(x1,x2=); ReadLn(x1,x2); M1:=calcul(x1,x2); Write(y1,y2=); ReadLn(y1,y2); M1:=calcul(y1,y2); If M1>M2 Then WriteLn(M1) Else WriteLn(M2); ReadLn; End.

Suma cifrelor unui numr Scriei o funcie care returneaz suma cifrelor unui numr natural x dat ca paramaetru.

Program suma; Var x:LongInt; Function suma(x:LongInt):Integer; Var d,s:Integer; Begin D:=x;

21

S:=0; Repeat S:=S+d mod 10; D:=d div 10; Until d=0; Suma:=S; End; Begin Write(Numrul:); ReadLn(x); WriteLn(Suma cifrelor lui ,x, este : ,suma(x)); ReadLn; End.

Numr prim Scriei un program care testeaz dac un numr natural x dat ca parametru este prim sau nu, returnnd true sau false.

Program Prim; Var x:Integer; Function test(x:Integer):Boolean; Var i:Integer; Begin Test:=True; For i:=2 To x div 2 Do If x mod i = 0 Then Test:=False; End; Begin Write(x=); ReadLn(x); If test(x) Then WriteLn(Numarul este prim!) Else WriteLn(Numarul nu este prim!); End.