presstern memorator informatica limbajul c

7/21/2019 Presstern Memorator Informatica Limbajul c

1/17


2/17

Cuprins

Gndirea algoritmic........................................... 1Problema cutrii ...................................................................... 1

Problema intrrii ntr-un cabinet medical ................................. 3

Structura unui program i a unei funcii C ......... 5

Reprezentarea numrului n binar ............................................ 7Transmiterea parametrilor n cadrul unei funcii ..................... 8

Construciile de bazale limbajului C ................. 9

Caracterele ................................................................................. 9

Identificatorii ............................................................................. 9Cuvinte cheie............................................................................ 10Tipuri de date ........................................................................... 10Tipuri aritmetice .......................................................................11Tipul ntreg ...............................................................................11Tipul flotant ............................................................................. 12Tipul caracter ........................................................................... 13Constante i variabile ............................................................... 13

Comentarii ............................................................................... 15

Operatori .................................................................................. 16Operatori aritmetici ................................................................. 16Operatorul de conversie explicit(cast) .................................. 17Operatorul dimensiune (sizeof) ............................................... 17Operatorul condiional ............................................................ 18

Structuri de date ................................................. 20

Lista liniarsimplu nlnuit................................................ 20Structura de tip stiv(LIFO Last In First Out) ........................ 26

Structura de tip coad............................................................. 30

Instruciuni C ..................................................... 33

Instruciunea vid.................................................................... 33Instruciunea de atribuire ........................................................ 33Instruciunea compus............................................................ 34Instruciunea if ........................................................................ 34


3/17

Instruciunea while ................................................................. 35Cel mai mare divizor comun ................................................ 36

Instruciunea do while ............................................................ 36Instruciunea for ..................................................................... 37

Programul C care calculeazn! ........................................... 37

Instruciunea return ................................................................ 38

O funcie care returneazmaximul a 2 numere .................. 38Numrul de elemente ale unei ir ........................................ 39

Comparaia celor 2 iruri ..................................................... 39Concateneare ....................................................................... 40

Instruciunea break ................................................................. 40Funcia exit ............................................................................... 41Instruciunea continue ............................................................ 42

Numerarea cifrelor existente ntr-un ir ............................. 42

Instruciunea goto ................................................................... 43

Instruciunea switch ................................................................ 44

Pointeri C ............................................................ 45

Operatori specifici pointerilor ................................................. 46Pointeri i tablouri ................................................................... 47Pointeri la funcii ..................................................................... 49Tipuri structurate de date ....................................................... 50

Structuri ............................................................................... 50

Cmpuri de bii ..................................................................... 51Uniuni .................................................................................. 52

Enumerri ............................................................................ 53

Funcii de bibliotec........................................... 55

Funcia printf .......................................................................... 55Funcia scanf ........................................................................... 57Funcii de conversie ................................................................ 59

Funcii generatoare de numere aleatoare ............................ 59

Funcii pentru operaii cu caractere i iruri de caractere ...... 59

Operaii cu fiiere ............................................... 62

Calcul Matriceal .................................................. 65

Produsul a doumatrici .......................................................... 65Inversa unei matrici ................................................................ 66

Metoda lui Gauss ..................................................................... 69


4/17

Metode de sortare .............................................. 72

Sortare ordinar....................................................................... 72Sortare prin selecie (Selection Sort) ....................................... 74Sortarea prin inserie direct(Direct Insertion Sort) .............. 77Sortare prin inserie binar(Binary Insertion Sort) ................ 79

Sortare prin inserie directfolosind o santinel.................... 81

Sortarea prin metoda bulelor (Bubble Sort) ........................... 83

Sortare rapid(Quick Sort) ..................................................... 85Sortare prin interclasare (Merge Sort) .................................... 87

Recursivitate ....................................................... 90

Calculul valorii n! .................................................................... 90Algoritmul lui Euclid recursiv ................................................. 90Sse genereze primele n numere din irul lui Fibonacci ........ 91

Metoda backtracking .......................................... 93

Permutrile .............................................................................. 93Problema aranjamentelor ........................................................ 95Problema combinrilor ............................................................ 95Problema reginelor .................................................................. 97Problema labirintului ...............................................................99Problema calului .................................................................... 102

Problema mingii .................................................................... 104Metoda Divide et Impera ................................. 108

Suma elementelor unui ir ..................................................... 108Problema Turnurilor din Hanoi .......................................... 109Elementul maxim ntr-un ir ................................................. 110Problema cutrii binare ........................................................ 111

Grafuri neorientate ........................................... 113

Implementarea parcurgerii n lime pentru un graf neorientat .... 113Implementarea parcurgerii n adncime pentru un graf neorientat ... 115

Drumuri ntr-un graf .............................................................. 117Grafuri ponderate .................................................................. 118Graful hamiltonian ................................................................ 120Grafuri euleriene .................................................................... 122Implementarea unui graf utiliznd matricea de adiacen.... 125Implementarea unui graf utiliznd pointeri .......................... 127

Drumul optim ntr-un graf .................................................... 128


5/17

1

Gndirea algoritmic

Problema cutrii

Existi cazul care, pentru o aceeai problem putem prezentadousoluii, n care una este mai rapidca alta. De pild, fie unir de numere natural oarecare, de exemplu 4,2,10,1,8,15,7.Vream s testm dacun numr dat (szivem numrul 8) seafln aceastsecvensau nu.

O astfel de cutare, prin parcurgerea de a stnga la dreapta antregii secvene de numere, pnse gsete numrul dorit sause epuieaztoate elementele din secven, se numete cutareasecvenial. Dacavem un ir S de n elemente (notat S[1..n]),atunci cutarea secveniala lui x n S se descrie prin:

Cutare_secvential(x,S[1..n]) nseamnnceputFie elemental_curent = primul_element;Att timp ct (elemental_curent x) si (pozitia elementuluicurrent


6/17

2

Dac numrul din mijloc este mai mic dect numrulcutat, atunci cutm a doua jumtate;

Dacnumrul din mijloc este mai mare ca numrul cutat,atunci cutm n prima jumtate;

Dac numrul din mijloc este egal cu numrul cutat,nseamncam gsit numrul n cauzi trebuie soprimcutarea.

Cutarea n jumtatea aleas se face tot la fel, deci se vanjumti i aceastzon

Procedeul anterior se numete cutare binar, deoarece, defiecare dat, o secven de numere este divizat n dou

jumti. Putem descrie cutarea binara unui numr x ntr-osecvenS[1..n] astfel.

Cutarea_binar(x, S[1..n]) nseamnnceputStabileste elemental_curent ca fiind elemental din mijlocul

secventei;Dacn=1 atunci

Dacx = elemental_curent atunci mesaj("gsit")Altfel mesaj("negsit")Altfel

nceputmparte secventa n cele doujumtti (S[1..mijloc] si

S[mijloc+1..n]);Dacelemental_curent = x atunci mesaj("gsit")Altfel

Dacelemental_curent < x atunciCutare_binar(x,S[mijloc+1..n])Altfel cutarea_binar(x.S[1..mijloc])

SfritSfrit.


7/17

3

Problema intrrii ntr-un cabinet medical

Dac un om vrea s intre pentru consult la un medic, atunci,mai nti va bate la u: dacmedicul rspunde prin poftim!,

atunci va intra, atlfel va atepta pncnd pacientul dinuntruva iei; abia dupce cabinetul va fi liber, va intra.

Intrare_la_medic nseamnnceputBate la_u;Dacrspunsul = "poftim!" atuncintr_n_cabinet;

AltfelnceputAtt timp ct cabinetul_este_ocupat_de_alt_pacient

executCiteste_un_ziar;

SfritSfrit.

O intruciune compus este format dintr-o secven deintruciuni, ncadrate de cuvinte nceput i sfrit, care potconine, la rndul lor, blocuri de alternativi repetiie.

Programarea este tehnica realizrii de algoritmi descrii prinproceduri i programe. Ea devine o art, atunci cnd sefolosesc cele trei elemente de structurate i se numeteprogramare structurat. Pentru a vedea ce ar nsemnaprogramare nestructurat, s reconsiderm procedura de

intrare n cabinetul medical:

Intare_la_medic nseamnnceputBate_la_u;Dacrspunsul = "poftim!" atunci intr_n_cabinet;Altfel nceputAtt timp ct cabinetul_este_ocupat_de_alt_pacient

execut


8/17

4

Citeste_un_ziar;ntr_n_cabinet

SfritSfrit.


9/17

33

Instruciuni C

Instruciunile C implementeaz structurile de baz aleprogramrii structurate:

structura secvenial(instruciunea compus) structura alternativ(instruciunea if) structura repetitiv condiionat anterior (instruciunea

while) i condiionatposterior (instruciunea do while)

Toate instruciunile limbajului C se termin cu ; excepiefcnd instruciunile care se termin cu } (instruciuneacompusi instruciunea switch) dupcare nu se pune ;.

Instruciunea vid

Instruciunea vid se reduce la caracterul ; i se folosete nacele construcii n care este necesar prezena uneiinstruciuni fra fi nevoie sse realizeze anumite operaii.

Instruciunea de atribuire

Instruciunea de atribuire se obine punnd ; dupo expresiede atribuire. Deci o expresie devine o instruciune dac esteurmatde ; (punct i virgul).


10/17

34

Instruciunea compus

Instruciunea compuseste o succesiune de declaraii urmatede instruciuni, succesiune care se include ntre acolade. Dac

existdeclaraii atunci ele definesc variabile care sunt valabilenumai n cadrul instruciunii compuse respective.

Instruciunea if

n limbajul C, instruciunea condiional de baz este

instruciunea if.Formatul general al instruciunii if este:

if (expresie) instruciune1;else instruciune2;

Efectul acestei instruciuni este urmtorul: se evalueazexpresia din paranteze. Dacvaloarea este adevrat (diferitde0) atunci se execut instruciune1 altfel se execut

instruciune2, apoi n ambele situaii se trece la instruciuneaurmtoare instruciunii if.

Deoarece instruciunea if testeaz valoarea numeric a uneiexpresii, urmtoarele construcii sunt echivalente:

if(expresie!=0)

if(expresie)

Exemplu:

if(x)if(y)printf("1");

elseprintf("2");


11/17

35

n acest caz, ramura else care tiprete valoarea 2 este legatdeinstruciunea if(y).

if(x){

if (y) printf("1");}elseprintf("2");

n acest caz, datorit instruciunii compuse, ramura else caretiprete valoarea 2 aparine instruciunii if(x).

Orice instruciune de atribuire nchis ntre parantezeleexpresiei din cadrul instruciunii if este de fapt o expresie, acrei valoare de adevr este egalcu valoarea atribuit.

Exemplul:

if(i=0) printf("Variabila i are valoarea 0");else printf("variabila i are o valoare diferitde 0");

este greit deoarece n loc s se foloseasc operatorul == sefolosete operatorul de atribuire iar n acest caz valoarea deadevr a expresiei de atribuire este 0 (fals), deci ntotdeauna seva afia mesajul variabila i are o valoare diferit de 0indiferent de valoarea iniiala lui i.

Instruciunea while

Instruciunea while implementeaz structura repetitivcondiionatanterior i are urmtorulformat general:

while(expresie) instruciune;

Efectul acestei instruciuni este urmtorul: Se evalueazvaloarea expresiei din parantez. Dacvaloarea expresiei estediferit de 0, atunci se execut instruciunea i se revine la


12/17

36

evaluarea expresiei. Dacvaloarea expresiei este fals (0) atuncise trece la instruciunea urmtoare instruciunii while.

Cel mai mare divizor comun

S se scrie programul C care implementeaz algoritmul luiEuclid de determinare a celui mai mare divizor comun a dounumere naturale.

#include

void main(void){

int a=18, b=12, r;while (r=a%b) a=b,b=r;//putem folosi operatorul virgul//n locul unei instruciuni compuseprintf("cmmdc este %d\n",b);

}

Instruciunea do while

Instruciunea do while implementeaz structura repetitivcondiionatposterior.Formatul generalal instruciunii este:

doinstruciune;

while(expresie);Efectul acestei instruciuni este urmtorul: Se executinstruciune dup care se evalueaz expresia. Dac expresiaeste evaluat ca adevrat, se execut se revine la execuiainstruciunii. Ciclarea continupncnd valoarea expresiei vafi fals (0), caz n care se trece la urmtoarea instruciune dedupinstruciunea do while.


13/17

72

Metode de sortare

Sortare ordinar

Cel mai simplu algoritm de sortare (dar i cel mai ineficient) sebazeaz pe urmtorul principiu: un ir este sortat dac prinparcurgerea lui de la nceput pnla sfrit, fiecare element estemai mic dect succesorul. Dacaceastcondiie nu este ndepli-nit, inversm cele 2 elemente. Sortarea se ncheie n momentuln care parcurgerea irului se face fr a fi necesar nici oinversare (fiecare element este mai mic dect succesorul su).

3 7 4 9 2 8

3 4 7 9 2 8

3 7 4 2 9 8

i=1; inversam a[1]=7 cu a[2]=4; k=1



3 7 4 2 8 9k0 deci pornim un nou ciclu;

i=1 inversam a[1]=7 cu a[2]=4; k=1

3 4 7 2 8 9 i=2; inversam a[2]=7 cu a[3]=2; k=1





2 3 4 7 8 9k ramane 0 (nu facem nici o inversare)

deci sirul este sortat


14/17

73

#include#include

void sortare_ordinara(int a[], int n){

int i,j,k,elem;do{for(i=0,k=0;ia[i+1])//dacelementul curent este mai mare dect succesorul este

necesarinversarea//lor; atenie: dacpunem mai mare sau egal i avem 2elemente egale, vom

//ajunge la ciclu infinit{elem=a[i];a[i]=a[i+1];a[i+1]=elem;k=1;//k diferit de 0 indicfaptul cs-a fcut o inversare

}} while(k);//sortarea se ncheie n momentul n care k a rmas 0 (deci

nu s-a fcut nici o//inversare de elemente

}

void main(void){int n,a[100],i;printf("Introd dim sirului:");scanf("%d",&n);printf("Introd elem sirului:\n");for(i=0;i


15/17

74

scanf("%d",a+i);}sortare_ordinara(a,n);printf("Sirul sortat este: ");for(i=0;i


16/17

108

Metoda Divide et Impera

Suma elementelor unui ir

S se calculeze suma elementelor unui ir folosind Divide etImpera.

#include#include

int a[20];

int divide(int ls, int ld){int mijloc,d1,d2;if(ls!=ld){

mijloc=(ls+ld)/2;d1=divide(ls,mijloc);d2=divide(mijloc+1,ld);return(d1+d2);

}elsereturn(a[ls]);

}

void main(void){int I,n;printf("Introd nr de elem ale sirului:");scanf("%d",&n);for(I=0;I


17/17

109

scanf("%d",a+I);}printf("Suma elem este: %d\n",divide(0,n-1));getch();

}

Problema Turnurilor din Hanoi

Legenda acestei probleme spune cBrahma a fixat pe Pmnttrei tije de diamante i pe una din ele a pus n ordinecresctoare 64 de discuri de aur de dimensiuni diferite, cu

discul cel mai mare jos. Singura operaiune permisclugrilorera mutarea a cte unui singur disc de pe o tijpe alta, astfelnct niciodatsnu se punun disc mai mare peste unul maimic. Legenda spune c atunci cnd clugrii vor muta toatecele 64 de discuri respectnd regulile de maa sus, atunci vaveni sfritul lumii. Presupunnd cn fiecare secundse mutun disc, lucrnd fr ntrerupere, cele 64 de discuri nu pot fimutate nici n 500 de miliarde de ani de la nceputul aciunii!

Vom considera trei tije verticale notate Stnga, Mijloc,Dreapta. Pe tija Stnga se gsesc aezate n discuri de diametrediferite, n ordinea descresctoare a diametrelor, privind de josn sus. Iniial, tijele Mijloc i Dreapta sunt goale. Sse afiezetoate mutrile prin care discurile de pe tija Stnga se mutpetija Mijloc, n aceeai ordine, respectnd urmtoarele reguli:

la fiecare micare se mutun singur disc un disc mai mare nu poate fi plasat peste un disc cu

diametrul mai mic un disc mai mare nu poate fi plasat peste un disc cu

diametrul mai mic

#include#include

presstern memorator informatica limbajul c

Documents