Algoritmi

INFORMATICA
Informatica este stiinta care se ocupa cu studiul reprezentarii si organizarii informatiei precum si cu studiul algotitmilor de prelucrare a informatiei cu ajutorul unui calculator.
ALGORITM
Un algoritm reprezinta o metoda de rezolvare a problemelor de un anumit tip.A rezolva o problema inseamna a obtine ,pentru anumite date de intrare ,rezultatul problemei (date de iesire ).Algoritmul este constiuit dintr-o succesiune de operatii care descriu, pas cu pas, modul de obtinere a datelor de iesire, plecand de la datele de intrare .

Exemplu :
Presupunand ca dispunem de un aragaz ,o tigaie ,2 oua ,sare si 200 ml ulei ,sa pregatim ochiuri .
“Date,, de intrare :oua ,ulei ,sare .
“Date ,,de iesire :ochiuri .
Pas 1: Se pune tigaia pe foc .
Pas 2: Se toarna uleiul in tigaie .
Pas 3: Asteptam pana cand se incinge uleiul.
Pas 4: Spargem cu indemanare ouale se rumenesc.
Pas 5: Asteptam pana cand ouale se rumenesc .
Pas 6: Daca nu tinem regim ,adaugam sare .

Proprietati caracteristice ale algoritmilor

1.Claritatea –la fiecare moment ,operatia care urmeaza a fi executata este unic determinata ,definita si realizabila .

2.Generalitatea (universalitatea )-o secventa de pasi reprezinta un algoritm de rezolvare a unei probleme daca obtine date iesire (rezultate ) pentru orice date de intraren specifice problemei .

3.Finititudinea –rezultatele problemei se obtin dupa o secventa de pasi .

Un algoritm este constituit dintr-o succesiune clara de operatii realizabile,
care au ca scop obtinerea intr-un timp finit a rezultatelor unei probleme,
pentru orice set de date de intrare .
DATE
Orice algoritm lucreaza cu date :date de intrare (datele pe care trebuie sa le primeasca un algoritm din exterior ),date de iesire (datele pe care trebuie sa le furnizeze aloritmul in exterior ),precum si date de manevra (date temporale ,necesare algoritmului pentru a obtine datele de iesire pe baza datelor de intrare ).

Datele cu care lucreaza algoritmii pot fi clasificate din mai multe puncte de vedere.O prima clasificare a datelor ,in functie de posibilitatea de a-si modifica valoarea ,este:

1.Constante –date care nu isi modifica valoarea .
2.Variabile –date care isi modifica valoarea .

In functie de valoarea lor,datele pot fi clasificate astfel:
a.Date numerice –au ca valori numere (naturale ,intregi sau reale );
b.Date alfabetice –au ca valori caractere sau siruri de caractere ; c.Date logice –au ca valori adevarat sau fals.
Expresii
O expresie este constituita dintr-o succesiune de operanzi ,conectati prin operatori.Un operand poate fi o constanta ,o variabila ,sau o expresie incadrata intre paranteze rotunde .Operatorii desemneaza operatiile care se executa asupra operanzilor.Operatorii care pot fi utilizati intr-o expresie depind de tipul operanzilor .

Vom prezenta trei categorii de operatori.

Operatori aritmetici definesc o operatie aritmetica si pot fi clasificati astfel:

1.operatori aritmetici multiplicative :*(inmultire ), /(impartire),%(restul impartirii intregi).

2.operatori aritmetici aditivi :+(adunare)si –(scadere ).

Operatori relationali
Opertorii relationali descriu relatia de ordine sau de egalitate dintre cei doi operanzi:<(mai mic),>(mai mare),<=(mai mic sau egal).>=”(mai mare sau egal),=(egal),!=(diferit ).

Operatori logici
Operatori logici definesc o operatie logica :negatia logica - !;conjunctie logica – si ;disjunctie logica - sau .Efectul acestor operatori este cel usual ,invatat la logica ,matematica .Il reamintim in tabelul urmator:

X
Y
!X
X sau Y
X si Y
Fals
Fals
Adevarat
Fals
Fals
Fals
Adevarat
Adevarat
Adevarat
Fals
Adevarat
Adevarat
Fals
Adevarat
Fals
Fals
Adevarat
Adevarat
Fals
Adevarat


Operatori logici se pot aplica operanzilor logici .Valoarea unui expresii logice este de tip logic .

Reprezentarea algoritmilor
I.Principiile programarii structurate
Programarea structurata a aparut in anii 70 datorita cresterii complexitatii aplicatiilor , aducand o serie de principii si tehnici inovative . Modularizarea este una dintre ele , permitand impartirea problemei in subprobleme de dimensiuni mai mici si complexitate mai redusa.Problemele erau rezolvate de echipe de programatori si rezultatele erau combinate in scopul rezolvarii problemei initiale.
O alta tehnica importanta a fost cea a structurarii datelor si prelucrarilor.Structurarea datelor permitea gruparea datelor in anumite zone de program , dar si descrierea si utilizarea unor structuri de date proprii.Structurarea prelucrarilor se poate realiza prin utilizarea modulelor si a subprogramelor .Un principiu important presupunea ca orice program se poate scrie prin secvente liniare , alternative si repetitive.
II. Descrierea algoritmilor
Un algoritm de rezolvare presupune stabilirea pasilor necesari. Pasii necesari pot fi descrisi intr-un limbaj de programare , insa nu toata lumea cunoaste acel program si niciun program nu s-a impus ca fiind singurul utilizat de programatori . Din acest motiv s-au impus niste metode generale de descriere a algoritmilor independente de limbajul de programare . Programele se scriu pe baza acestor descrieri . Metodele cele mai importante sunt :
∙ pseudocodul
∙ schema logica
PSEUDOCODUL reprezinta un set restrans de cuvinte in romana sau engleza asociate unor operanti.Astfel , cuvintele utilizate sunt : intreg , real , citeste , scrie , daca , atunci , altfel , sfarsit daca , pentru , cat timp , sfarsit cat timp , executa cat timp .
Exemplu : Cititi doua variabile intregi . Calculati suma lor si afisati rezultatul.
intreg a , b , c
citeste a , b
c= a + b
scrie c

SCHEMA LOGICA este reprezentarea grafica a unor prelucrari. Aceasta reprezinta un set de simboluri grafice.

STRUCTURA SECVENTIALA(LINIARĂ)
Presupune executarea unei prelucrari in ordinea precizata . ( ele nu se executa conditional sau repetitiv ). Exista cateva tipuri , printre care :
1.) Declararea variabilelor se face cu sintaxa ,, tip data variabila ’’. Definirea variabilei pune in legatura numele variabilei cu tipul sau .

2.)Citirea variabilei reprezinta operatia prin care continutul unei variabile e incarcat de la tastatura.

3.)Atribuirea este operatia prin care o valoare e asociata unei variabile.

4.)Afisarea se realizeaza cu sintaxa scrie exp 1 , … , exp n

5.)Instructiunea compusa reprezinta un set de prelucrari cuprinse intre acolade .

{ p1
.
.
} pn
STRUCTURA ALTERNATIVA

SCOP : permite efectuarea unei unui set de operații in functie de valoarea unei conditii.
Are două forme:
1.daca_conditie / expresie
instr.
sfarsit_daca
MECANISM DE FUNCTIONARE : se evalueaza conditia sau expresia la o valoare logica. Daca e adevarata se realizeaza instr. , daca nu , nu se executa nimic.
2. daca_cond atunci
instr1
altfel
instr2
sfarsit_daca
Mecanism de functionare : se evalueaza conditia la o valoare logica.Daca este adevarat se executa instr1 , daca nu , se executa instr2.

SELECTIA MULTIPLA
Este o structura derivata. Ea poate fi inlocuita prin struturi decizionale , deoarece este implementata de instructiuni in limbaje de programare. Ea poate fi prezentata in schema logica si pseudocod :
case_exp
v1 , p1
………..
vn , pn
end_case

Mecnism de functionare : se evalueaza expresia . Daca valoarea obtinuta = V1 , atunci se executa P1 si se iese din instructiune . Daca nu , se compara valoarea cu V2.Daca sunt egale se executa P2 . Daca nu , valoarea se compara cu Vn , daca e egala se executa Pn si se iese din instructiune.
STRUCTURA “PENTRU”
SCOP : permite executarea unei prelucrari de un numar cunoscut de ori . Este o structura cu text initial si numar cunoscut de iteratii.
Prin text initial se intelege faptul ca se efectueaza intai testarea conditiei si apoi se efectueaza prelucrarea.
pentru_K=Vc , Vf executa
instructiune
sfarsit_pentru
MECANISM DE FUNCTIONARE : se initializeaza K ( contorul ) cu o valoare initiala . Se evalueaza contorul K<_Vf . Daca e adevarat , se realizeaza prelucrarea si creste contorul initial cu o unitate , daca nu , se iese din structura.

Obs: Se efectueaza in mod repetat o singura prelucrare , mai multe prelucrari fiind incluse-ntr-o structura bloc.
Aplicatii:
1) Calculati suma primelor n numere naturale .
Rezolvare :
intreg n, i , S
citeste n
S=0
Pentru i=1 , n executa
S= s + i
Sfarsit pentru
Scrie S.
Simulare numerica:
n=3 , S=0
P1 i=1 , 1≤3 (a) , S=0+1=1 , i=1+1=2
P2 i=2 , 2≤3 (a) , S=1+2=3 , i=2+1=3
P3 i=3 , 3≤3 (a) , S=3+3=6 , i=3+1=4
P4 i=4 , 4≤3 (f) , scrie 6 .
2.)Se citesc n valori . Calculati produsul valorilor pozitive si suma valorilor negative .
Rezolvare :
intreg n , i , x , S , P
citeste n
S=0
P=1
Pentru i=1 , n executa
Citeste x
daca_x≥0 , atunci P=P*x
altfel S=S+x
sfarsit daca
sfarsit pentru
scrie S , P

Simulare numerica :
n=3 , P=1 , x=2 , -1 , 3
P1 i=1 , 1<_3 (a) , x=2 , 2>0 (a) , P=1*2=2 , i=1+1=2
P2 i=2 , 2<_3 (a) , x=-1 , -1>0 (f) , S=-1 , i=1+2=3
P3 i=3 , 3<_3 (a) , x=3 , 3>0 (a) , P=2*3=6 , i=3+1=4
P4 i=4 , 4<3(f) scrie -1 , 6

STRUCTURA “CAT TIMP”
SCOP : permite executarea unei prelucrari cat timp o conditie e indeplinita . Este o structura cu test initial si numar necunoscut de iteratii.( test initial=se efectueaza mai intai testul conditiei si apoi prelucrarea , numar necunoscut de iteratii= programatorul nu cunoaste la momentul scrierii programului de cate ori se repeta prelucrarea respectiva )

Cat_timp cond/expresie executa
instructiune
Sfarsit cat_timp

MECANISM DE FUNCTIONARE : se evalueaza conditia la o valoare logica. Daca e adevarata , se executa prelucrarea P si se revine la testul conditiei , daca nu , se iese din structura.
OBS :
1-Dacă expresia este falsa (egala cu zero) din primul pas, instrucțiunea nu se execută niciodată.
2-Este obligatorie modificarea condiției/expresiei , în caz contrar ciclul este infinit.

Alpicatii :

1.)Calculati suma primelor n numere naturale folosind structura cat timp.
Rezolvare :
intreg n , i , S
citeste n
S=0
i=1
cat_timp i≤n executa
S=S + i
i=i+1
sfarsit_cat_timp
scrie S
Simulare numerica:
Po n=3 , S=0 , i=1
P1 i=1 , 1<_3 (a) , S=0+1=1 , i=1+1=2
P2 i=2 , 2<_3 (a) , S=1+2=3 , i=1+2=3
P3 i=3 , 3<_3 (a) , S=3+3=6 , i=3+1=4
P4 i=4 , 4<_3 (f) , scrie 6.

2.)Calculati produsul a n valori citite de la tastatura.
Rezolvare :
intreg n , i , P , x
citeste n
P=1
i=1
cat_timp i<_n executa
citeste x
P=P*x
i=i+1
sfarsit cat timp
Simulare numerica:
Po n=3 , x=2,4,6 , P=1
P1 i=1 , 1<_3 (a) , x=2 , P=1*2=2 , i=1+1=2
P2 i=2 , 2<_3 (a) , x=4 , P=2*4=8 , i=1+2=3
P3 i=3 , 3<_3 (a) , x=6 , P=6*8=48 , i=1+3=4
P4 i=4 , 4<_3 (f) , scrie 48.

RETINETI!

∙ Pentru a calcula inversul unui numar trebuie sa folosim formula :

NINV=NINV*10+c

unde c=n%10 , iar n=n/10

∙ Pentru a demonstra daca un numar e palindrom trebuie ca acesta sa fie egal cu inversul sau.
Ex : 123 nu e palindrom
121 e palindrom.
3.) Calculati suma cifrelor unui numar .
Ex : n=123
Suma cifrelor=1+2+3=6
Pseudocod:
Intreg n,s,c
Citeste n
S=0
Cat timp n>0 executa
C=n%10
S=s+c
N=n/10
Sfarsit cat timp
Scrie s

Simulare numerica:
P0:n=123,s=0
P1:123>0 A, c=123?%10=3,s=0+3,n=12310=12
P2:n=12>0 A,c=12%10=2,s=3+2=5,n=110=1
P3:n=1>0 A,c=1%10=1,s=5+1=6,n=110=0
P4:n=0>0 F,scrie s=6

4.)Calculati produsul cifrelor unui numar.

Pseudocod:
Intreg n,p ,c
Citeste n
P=1
Cat timp n>o executa
C=n%10
P=p*c
N=n/10
Sfarsit cat timp
scrie p
Simulare numerica:

P0:n=123,p=1
P1:n=123>0 A,c=123%10=3, p=1*3=3,n=12310=12
P2:n=12>0A, c=12%10=2,p=3*2=6,n=1210=1
P3: n=1>0 A,c=1%10=1, p=6*1=6,n=110=0
P4:n=0>0 F,scrie p=6


STRUCTURA EXECUTĂ..CAT TIMP


SCOP : permite executarea unei prelucrari cat timp o conditie e indeplinita . Este o structura cu test final si numar necunoscut de iteratii.( test final=se efectueaza mai intai prelucrarea și apoi testul conditiei , numar necunoscut de iteratii= programatorul nu cunoaste la momentul scrierii programului de cate ori se repeta prelucrarea respectiva )



executa

instructiune


Cat_timp cond/expresie




MECANISM DE FUNCTIONARE : se execută instrucțiunea, se evalueaza conditia la o valoare logica. Daca e adevarata , se executa din nou intrucțiunea si se revine la testul conditiei , daca nu , se iese din structura.

OBS :

1- Instrucțiunea se execută cel puțin o dată indifereant de valoarea condiției



2-Este obligatorie modificarea condiției/expresiei , în caz contrar ciclul este infinit.