01+02 - Introducere. Subprograme (cont)

7/26/2019 01+02 - Introducere. Subprograme (cont)

1/39

Algoritmi i tehnici de

programare

? ? ??


2/39

programare

Fi a disciplinei ( programare.ase.ro, pagina ATP ) Con inut, cuno tin e anterioare necesare Bibliografie manual, culegere de probleme

Evaluare !eminar" 40% Teme obligatorii (condi ie de intrare la p.p.)" 10% Probe practice" 30%

E#amen" 50%

$in oficiu"10% $iverse

pre%en &, recuper&ri, studiu individual, reguli, colaborare

Consulta ii

'*, +oi *"*-", vineri /"*"'

Algoritmi i tehnici de programare
http://programare.ase.ro/http://var/www/apps/conversion/tmp/scratch_4/Algoritmi%20si%20tehnici%20de%20programare_Uscatu.JPGhttp://var/www/apps/conversion/tmp/scratch_4/Algoritmi%20si%20tehnici%20de%20programare_Uscatu.JPGhttp://programare.ase.ro/


3/39

Subprograme (continuare)

Pointeri la func ii (subprograme)

0ecursivitate

Biblioteci de subprograme


4/39


1umele unei func2ii poate fi folosit capointerconstant(asem&n&tor masivelor)

!emnifica2ie adresadin memorie unde se afl& codul e#ecutabil al

subprogramului respectiv Tip

pointer c&tre un subprogram care prime3te o anumitlist de parametri3i 4ntoarce un anumit tip de rezultat

5tili%are Transmiterea subprogramelor ca parametri pentru alte

subprograme


5/39


E#empluvoid sortare(float v[], int n);sortarepointer ctre o func!ie care prime"te ca parametri un

vector cu elemente float"i un ntreg"i are rezultat de tip void

float minim(float v[], int n, int poz[], int*

nr);minimpointer ctre o func!ie care prime"te ca parametri un vectorcu elemente float# un ntreg#un vector cu elemente ntregi"i un

pointer ctre ntreg"i are rezultat de tip float


6/39


$eclarare ariabil&parametru tip pointer la func!ie "i utili'are

void sortare(float v[], int n);

float minim(float v[], int n, int poz[], int* nr);

void main()

{ int dim; float a[100]; int unde[100], cite;

void (*p)(float v[], int n);

float (*q)(float v[], int n, int poz[], int* nr);

p = sortare;

q = minim;

sortare(a,dim); (*p)(a, dim); p(a, dim);

minim(a,dim,unde,!cite); (*q)(a,dim,unde,!cite);

"


7/39


E#emplu 6etoda bisec2iei pentru re%olvarea unei ecua2ii

#* #'

n, eps#

f(#)


8/39


#include $stdio%&'

float ecuatie(float ){ return * * + 1;"

int -isectie( float 1, float , float eps, int n,

float (*f)(float),

float *){ int cod = 0; .&ile ((n ' 0) !! (cod == 0)) { * = (1 + ) ; if((*f)(*) == 0)

cod = 1; else

if((1) $ eps)cod = ;

elseif((*f)(1)*(*f)(*)$0) = *; else

1 = *;n;

" return cod;"

void main(){ float a, -, sol, prec; int nr, cod; printf(/na=/); scanf(/f/,!a); printf(/n-=/); scanf(/f/,!-); printf(/nprecizia=/); scanf(/f/,!prec);

printf(/nnr=/); scanf(/d/,!nr);cod =-isectie(a,-,prec,nr,ecuatie,!sol);

s.itc&(cod) { case 02 printf(/n3ara solutie/); -rea4; case 12 printf(/n5olutia eacta

este

%6f/, sol);-rea4; case 2 printf(/n5olutia

aproimativa este %6f/, sol); ""


9/39

ecursiitate

Algoritmi iterativi Algoritmi recursivi

0ecursivitate simpl& (algoritm unirecursiv)

0ecursivitate multipl& (algoritm multirecursiv) Formul& de start (una sau mai multe) Formul& recursiv&

E#emple 1um&rarea valorilor care 4ndeplinesc o condi2ie !uma elementelor unui vector Algoritmul lui Euclid 7irul lui Fibonacci


10/39

ecursiitate# subprograme recursie

5n algoritm, iterativ sau recursiv, poate fi implementatprintrun subprogram iterativ, fie recursiv

!ubprogram recursiv" generea%& (cel pu2in) un apel c&tre

el 4nsu3i 0ecursivitate direct&

!impl& 6ultipl&

0ecursivitate mutual&

8mplica2ii 6od de construire a subprogramelor 1ecesar de memorie


11/39


Construc2ia subprogramelor recursive !& asigure respectarea caracterului finit alalgoritmului" ie3irea dup& un

num&r finit de pa3i Fiecare apel recursiv trebuie aplicat unei probleme mai simple dec4t 4n pasul

anterior 0e%ult& o metod& simpl& de oprire a gener&rii de noi apeluri

Condi2ie de oprire a gener&rii de noi apeluri Aplicarea formulei de start dac& e 4ndeplinit& condi2ia Aplicarea formulei recursive 4n ca% contrar

long factorial( unsigned n ){ long f; if ( !n )

f = 1; else

f = n*factorial( n-1); return f;}


12/39


1ecesarul de memorie


13/39


fib(n) = fib(n-1) + fib(n-2), fib(1) = fib(0) = 1

fib( - )fib( )

fib( )

fib( * )fib( ' )

9

'

*

*

fib( * )

*

fib( ' )

**

fib( * )

fib( )

'


14/39


C4nd alegem subprograme iterative : recursive; Avanta+e 3i de%avanta+e

Consum memorie

Timp de e#ecu2ie

53urin2& 4n proiectare : implementare


15/39


Calculul combin&rilor de nluate c4te k => ,

long comb(unsigned n, unsigned ){ long c; if (n)

c = 0;

elseif ((==0)""(==n))c = 1;

elsec = comb(n-1,) + comb(n-1,-1);

return c;}


16/39


!uma elementelor unui vector #(n) = $%n-1& + #(n-1), #(0) = 0

double suma(double '%&, int n)

{ double s; if( n == 0)

s = 0; else

s = '%n-1& + suma(', n-1);

return s;}

Produsul elementelor unui vector


17/39


C&utarea binar&

int cauta(float '%&, int , int u, float ){ int m;

if ( u)m = -1;

else {m = ( + u) 2; if( '%m&)

m = cauta(', , m-1, );

elseif( '%m&)m = cauta(', m+1, u, );

} return m;

}


18/39


Cum se transform& un subprogram iterativ 4n unulrecursiv;*. instruc2iunea iterativ& dispare

'. condi2ia de la instruc2iunea iterativ& devine (eventual modificat&)condi2ie de oprire a gener&rii de noi autoapeluri. 0epetarea este asigurat& prin autoapel. E#emplu" metoda bisec2iei


19/39


etoda bisec iei

int bisectie( float $1, float $2, float es, int n,float (*f)(float), float *$)

{ int cod = 0;

ile ((n 0) (cod == 0)) { *$ = ($1 + $2) 2; if((*f)(*$) == 0)

cod = 1; else

if(($2-$1) es)cod = 2;

elseif((*f)($1)*(*f)(*$)0)

$2 = *$; else

$1 = *$; n--;

} return cod;

}

int bisectie( float $1, float $2, float es, int n, float (*f)(float), float *$){ int cod; if ( n == 0)

cod = 0; else

{ *$ = ($1 + $2) 2; if((*f)(*$) == 0)

cod = 1; else

if(($2-$1) es)cod = 2;

else

{ if( (*f)($1) * (*f)(*$) 0 ) $2 = *$; else

$1 = *$; n--; cod = bisectie( $1, $2, es, n, f, $ ); }

return cod;}

if((*f)($1)*(*f)(*$)0)

cod = bisectie( $1, *$, es, n-1, f, $ );else cod = bisectie( *$, $2, es, n-1, f, $ );


20/39


Teme"

1um&rul de elemente negative dintrun vector

Produs scalar 4ntre doi vectori

Algoritmul lui Euclid

Calculul c.m.m.d.c.

6etoda tangentei

Problema turnurilor din =anoi!ortarea unui vector


21/39

*iblioteci de subprograme

Bibliotec&" colec ie de subprograme, grupate 4ntrunsingur fi ier (compilat)

!cop 0eutili%area codului 4n mai multe aplica ii $istribuirea c&tre al i utili%atori

Tipuri cod surs&, cod binar statice, dinamice


22/39

*iblioteci de subprograme

>ariante de lucru

?n mod comand&

cl+e,e - compilator lib+e,e - manager de biblioteci lin.+e,e - editor de legturi

?n mediul de programare (8$E) >isual !tudio

?n aceea i solu ie (mai multe proiecte) ?n solu ie independent&


23/39

*iblioteci de subprograme/ statice

Codul subprogramelor utili%ate este inclus 4n e#ecutabil

E#tensie @indos" +lib


24/39


Editare de leg&turi

Fi iere codsurs&(.c, .cpp, .)

Fi iere codobiect(.ob+)

Bibliotecicod obiect(.lib)


Cod binare#ecutabil(.e#e)

Compilare6anagerbiblioteci



Compilare


25/39


Fiiere sursantet matrice.h

implementare matrice.cpptest test.cpp

alocare dinamica matrice . - nr/ linii, nr/ coloane - adresa matriceidouble **alocamatrice(int m, int n);

dealocare matrice dinamica . - adresa matricei, nr/ linii - adresa matricei (3455)double** dealocarematrice(double **a, int m);

rodus matrice atrate de dimensiuni egale, realocate . - a, b, n - c'oid rodusmn(double** a, double **b, int n, double** c);

coiaa matrice realocate . - a, m, n - b'oid coiaa(double** a, int m, int n, double** b);

citire matrice atrata cu alocare . - - adresa matrice, dimensiunedouble** citirematrice(int *m);

afisare matrice atrata . - adresa matrice, dimensiune -'oid afisarematrice(double** a, int m);

6include stdio/6include malloc/

6include 7matrice/7

citire matrice atrata cu alocare . - - adresa matrice, dimensiunedouble** citirematrice(int *m){ int i,8; double** a; rintfs(79n9n:imensiune 7); scanfs(7


26/39


?n mod comand& !e creea%& un director nou pentru proiect 4n care se salvea%& cele

fi iere !e e#ecut&cars3+bat, aflat in subdirectorul binal >isual !tudio

?9@rogram Ailes ($B>)9icrosoft Cisual #tudio 10/09C?9bin

cl -c matrice/c

matrice/ob8

lib matrice/ob8 outmatrice/libmatrice/lib

cl test/c matrice/lib

test/e$e


27/39


?n 8$E creare bibliotec& binar& !e creea%& un proiect nou de tip Win32 Console Application

numele solu iei" BSIDE, al proiectului" matrice

?n fereastra Application settings se alege Application tpe! Static li"rar Additional options!Empt pro#ect, f&r& $recompiled %eaders

!e adaug& la proiect fi ierele surs& (antet i implementare)

!e compilea%& solu ia ( Build)

?n directorul BSIDE&De"u'se va genera biblioteca binar&

numele bibliotecii"matrice(li"


28/39


?n 8$E utili%are bibliotec& binar& 4n aceea i solu ie !e creea%& un proiect nou de tip Win32 Console Application

numele proiectului" )est, se adaug& la solu ia BSIDE ?n fereastra Application settings se alege

Application tpe! Console Application Additional options!Empt pro#ect, f&r& $recompiled %eaders !e adaug& la proiect fi ierul surs& (cu func ia main) $ro#ect $roperties Common $roperties *rame+ork and e-erences

Add .e+ e-erence/ matrice

$ro#ect $roperties Con-i'uration $roperties C0C11 eneralAdditional Include Directories calea c&tre matrice(% $ro#ect Set As Startp $ro#ect !e compilea%& solu ia ( Build) !e lansea%& 4n e#ecu ie din 8$E sau separat

)est(e4e se afl& 4n BSIDE&De"u'


29/39


?n 8$E utili%are bibliotec& binar& 4n alt& solu ie !e creea%& un proiect nou de tip Win32 Console Application

numele solu iei ( i al proiectului)" )estS ?n fereastra Application settings se alege

Application tpe! Console Application Additional options!Empt pro#ect, f&r& $recompiled %eaders

!e adaug& la proiect fi ierul surs& (cu func ia main) !e copia%& 4n directorul proiectului fi ierele matrice(% i matrice(li" $ro#ect $roperties Con-i'uration $roperties 5inker Input

Additional Dependencies se adaug& matrice(li" !e compilea%& solu ia ( Build) !e lansea%& 4n e#ecu ie


30/39

*iblioteci de subprograme/ dinamice

Codul subprogramelor utili%ate este separat de e#ecutabil

E#tensie @indos" +dll


31/39


Editare de leg&turi


Fi iere codobiect (.ob+)Tabela deimport (.lib)

Bibliotecidinamice(.dll)


Cod binare#ecutabil(.e#e)

CompilareEditare de

leg&turi



Compilare

Cod binare#ecutabil

(.e#e)

Biblioteci

dinamice(.dll)


32/39


Crearea i utili%area este asem&n&toare cu a bibliotecilorstatice

$iferen e Antetul func iilor trebuie s& con in& (doar 4n .) declspec(dlle,port)


33/39


?n mod comand& !e creea%& un director nou pentru proiect 4n care se salvea%& cele

fi iere !e e#ecut&cars3+bat, aflat in subdirectorul binal >isual !tudio

?9@rogram Ailes ($B>)9icrosoft Cisual #tudio 10/09C?9bin

cl matrice/c 5:

matrice/dll, matrice/lib

cl test/c matrice/lib test/e$e

Pentru e#ecu ie s4nt necesare" te$t/e$e i matrice/dll


34/39


?n 8$E creare bibliotec& binar& !e creea%& un proiect nou de tip Win32 Console Application

numele solu iei" BDIDE, al proiectului" matrice

?n fereastra Application settings se alege Application tpe! D55 Additional options!Empt pro#ect

!e adaug& la proiect fi ierele surs& (antet i implementare)

!e compilea%& solu ia ( Build)

?n directorul BDIDE&matrice&De"u'se va genera biblioteca binar&

fi iere" matrice(dll, matrice(li"


35/39


?n 8$E utili%are bibliotec& binar& 4n aceea i solu ie !e creea%& un proiect nou de tip Win32 Console Application

numele proiectului" )est, se adaug& la solu ia BDIDE ?n fereastra Application settings se alege


!e adaug& la proiect fi ierul surs& (cu func ia main) $ro#ect $roperties Common $roperties *rame+ork and e-erences

Add .e+ e-erence/ matrice $ro#ect $roperties Con-i'uration $roperties C0C11 eneral

Additional Include Directories calea c&tre matrice(% $ro#ect Set As Startp $ro#ect !e compilea%& solu ia ( Build) !e lansea%& 4n e#ecu ie


36/39


?n 8$E utili%are bibliotec& binar& 4n alt& solu ie !e creea%& un proiect nou de tip Win32 Console Application

numele solu iei ( i al proiectului)" )estD !e copia%& 4n directorul proiectului fi ierele matrice(% i matrice(li" ?n fereastra Application settings se alege


!e adaug& la proiect fi ierul surs& (cu func ia main) $ro#ect $roperties Con-i'uration $roperties 5inker Input

Additional Dependencies se adaug& matrice(li" $ro#ect $roperties Con-i'uration $roperties De"u''in'

En6ironment se adaug& calea c&tre matrice(dll !e compilea%& solu ia ( Build) !e lansea%& 4n e#ecu ie


37/39


Compara ie dimensiuni" T E 6

C4nd folosim biblioteci;

C4nd folosim biblioteci statice : dinamice;

Static (.lib) Dinamic (.dll)

L.C. IDE L.C. IDE

matrice/D D D D

matrice/lib D D D D

matrice/dll - - D D

test/e$e D D D D


38/39


Tem& Crea i i testa i o bibliotec& format& din func iile necesare

prelucr&rii vectorilor

Bibliotec& static&


39/39

Spor la nvat!

Date post:	13-Apr-2018
Category:	Documents
Upload:	chirita-alexandra
View:	252 times
Download:	0 times

01+02 - Introducere. Subprograme (cont)

Documents