algoritmi - wiki- · pdf filestructuri repetitive cu test initial (fara contor) condiţie...

Click here to load reader

Post on 06-Feb-2018

249 views

Category:

Documents

2 download

Embed Size (px)

TRANSCRIPT

  • 1

    Algoritmi

    Algoritmi. Introducere Notiunile cu care opereaza algoritmii

    Principiile programarii structurate Teorema lui Bohm si Jacopini

    Aplicatii propuse

    http://infoscience.3x.ro/c++.html

    ALGORITMI. NOTIUNI GENERALE

    Algoritmul este conceptul fundamental al informaticii. Orice echipament de calcul poate fi considerat o masina algoritmica. ntr-o definitie aproximativa algoritmul este un set de pasi care defineste modul n care poate fi dusa la ndeplinire o anumita sarcina. Exemplu de algoritm: algoritmul de interpretare a unei bucti muzicale (descris n partitura).

    DEFINITII SI CARACTERISTICI

    Definitie: Algoritmul este un set finit de pasi executabili, descrisi fara echivoc, care solutioneaza o clasa de probleme.

    Proprietatile fundamentale ale algoritmilor:

    Caracterul finit: orice algoritm bine proiectat se termina ntr-un numar finit de pasi;

    Claritatea : algoritmul trebuie descris clar, fara ambiguitati Generalitatea: orice algoritm trebuie sa rezolve toate problemele dintr-o clasa de

    probleme; Completitudinea-presupune tratarea cazurilor speciale (a exceptiilor) unei

    probleme. Realizabilitatea: orice algoritm trebuie sa poata fi codificat ntr-un limbaj de

    programare; Eficienta- se refera la timpul de executie (in care sunt folosite resursele

    calculatorului: memorie, procesor) si la spatiul de memorie utilizat. Un algoritm este cu atat mai eficient cu cat spatiul de memorie utilizat este mai mic si numarul de operatii mai putine.

    Nerespectarea acestor caracteristici generale conduce la obtinerea de algoritmi neperformanti, posibil infiniti sau nerealizabili.

  • 2

    Observatia1. Nu orice problema admite un algoritm de rezolvare. Observatia2. Doi agoritmi sunt echivalenti cand pentru aceleasi date de intrare se obtin aceleasi date de iesire.

    Etapele rezolvarii unei probleme: -stabilirea cerintelor problemei -stabilirea datelor de intrare si a datelor de iesire -stabilirea unui rationament general de rezolvare a problemei -reprezentarea algoritmului problemei intr-o forma simpla si clara -verificarea rationamentului pentru valori concrete -implementarea algoritmului intr-un limbaj de programare

    http://infoscience.3x.ro/c++/alg_introducere.html

    Notiunile cu care opereaza algoritmii

    Algoritmii opereaza cu urmatoarele notiuni:

    Un algoritm prelucreaza datele de intrare in scopul obtinerii unor rezultate (a datelor de iesire) utilizand si date intermediare.

    Datele sunt valori concrete specifice fiecarei probleme care vor fi retinute de calculator in anumite zone de memorie.

    Dimensiunea zonelor de memorie depinde de tipul datelor respective. Intuitiv, memoria poate fi reprezentata ca locatii succesive (zone de memorie)

    identificate prin adrese (numere de ordine). Programatorul are sarcina de a gandi algoritmul unei probleme si de a utiliza cat

    mai eficient memoria. n program datele apar fie sub forma unor constante (valori cunoscute anticipat, care nu se modifica pe parcursul executiei), fie sub forma de variabile. Constantele si variabilele sunt obiectele informationale de baza manipulate ntr-un program. Putem defini o variabila ca fiind un nume dat unei zone de memorie. Datele se caracterizeaza printr-un anumit tip care va determina :

    -o anumita multime din care data poate lua valori - un anumit mod de reprezentare n memoria calculatorului - o multime de operatori care pot fi aplicati acestor valori. - tipul unei date determina lungimea zonei de memorie ocupata de acea

    data. n general, lungimea zonei de memorare este dependenta de calculatorul pe care s-a implementat compilatorul.

    Datele se pot clasifica dupa tipul lor in:

    Caractere Intregi Reale Logice

  • 3

    Sir de caractere -variabilele: retin date de un tip anume. O variabila isi poate schimba valoarea dar tipul nu.

    O variabila pentru a fi prelucrata trebuie sa fie declarata (anuntata). Acest lucru consta de fapt in precizarea tipului variabilei.

    Exemplu: caracter car intreg a real b,c logic x sir y - expresii: o expresie este alcatuita din unul sau mai multi operanzi legati intre ei prin

    operatori. Operanzii pot fi constante sau variabile. Exemplu: 4.5+2*a unde 4.4, 2, a sunt operanzi iar + si * sunt operatori Expresiile pot interveni cel mai adesea in instructiuni de atribuire de tipul: variabila expresie Exemplu: c 2*b-1 Operatori pentru tipuri numerice :

    operator semnificatie + adunare - scadere * inmultire / catul impartirii % restul impartirii

    Operatori relationali :

    operator semnificatie = De egalitate diferit > Mai mare >= Mai mare sau egal < Mai mic

  • 4

    Operatori logici :

    operator semnificatie ! Negatie logica si Si logic sau Sau logic

    Datele de tip logic pot avea doua valori : A (adevarat) si F (fals) Reguli de compunere a operatorilor logici :

    ! A F F A

    si A F A A F F F F

    sau A F A A A F A F

    Principiile programarii structurate Programarea structurata a inceput la inceputul anilor 70. Este un concept cu o

    importanta fundamentala in scrierea algoritmilor. In general, algoritmii se eleboreaza prin utilizarea exclusiva a anumitor structuri

    (liniara, alternativa, repetitiva). Prin structura se intelege o anumita forma de imbinare a operatiilor cu care lucreaza

    algoritmii. Structura liniara Vom defini structura liniara astfel: Daca S1, S2, S3,Sn sunt structuri ( de orice tip), atunci: S1 S2 S3 . Sn

  • 5

    Constituie o strucura liniara reprezentata in pseudocod. Iar: . Constituie o strucura liniara reprezentata in schema logica. Structura alternativa In pseudocod :

    DAC condiie=True ATUNCI aciune1 ALTFEL aciune2

    structura de decizie (alternativa)

    DA

    NU

    ACIUNE2

    ACIUNE1

    Se testeaz ndeplinirea condiiei din blocul de decizie. Dac aceast condiie este ndeplinit, se execut ACIUNE1. Dac nu, se execut ACIUNE2. La un moment dat, se execut sau ACIUNE1, sau ACIUNE2.

    Condiie ndeplinit?

    S1

    S2

    S3

    Sn

  • 6

    Exemple: 1. Se citesc 2 valori numerice reale, care reprezint dimensiunile (lungimea i limea unui

    dreptunghi). S se calculeze i s se afieze aria dreptunghiului. Se citesc 2 valori reale. S se afiseze valoarea maximului dintre cele 2 numere. Structura repetitiva Structuri repetitive cu test initial (fara contor)

    START

    CITETE L, l

    aria

  • 7

    Observatie : actiune2 este de fapt actiunea care urmeaza structurii repetitive motiv pentru care in pseudocod se poate scrie : CT TIMP condiie EXECUT aciune Exis i situaii n care se tie de la nceput de cte ori se va repeta o anumit aciune. n aceste cazuri se folosete tot o structur de control repetitiv cu test iniial. Se utilizeaz un contor (numeric) pentru a ine o eviden a numrului de execuii ale aciunii. De cte ori se execut aciunea, contorul este incrementat. In pseudocod :

    PENTRU contor=val_ini LA val_finala [PAS p]

    EXECUT aciune;

    Structur repetitiv cu test final:

    Figura 1.6. Structur repetitiv cu test iniial, cu numr cunoscut de pai

    Se atribuie contorului valoarea iniial (figura 1.6.). Ct timp condiia (valoarea contorului este mai mic sau egal cu valoarea final) este ndeplinit, se repet: ACIUNE incrementare contor (se adun 1 la

    valoarea anterioar a contorului).

    contorvaloare_iniial

    valoare_contor valoare_final

    ACIUNE

    valoare_contor valoare_contor + 1

    DA

    NU

    Se execut mai nti ACIUNE1. Se testeaz apoi condiia (figura). Se repet ACIUNE1 pana cand condiia este ndeplinit. n acest caz, corpul ciclului (ACIUNE1) este executat cel puin o dat.

    DA

    NU

    ACIUNE 1

    Condiie ndeplinit?

    Structur repetitiv cu test final

  • 8

    In pseudocod :

    REPET aciune PN CND exp_test=TRUE http://infoscience.3x.ro/c++/lab2stucturi%20de%20control.htm

    Teorema lui Bohm si Iacopini Cele 3 structuri de control: liniara, alternativa si repetitiva sunt suficiente pentru a descrie orice algoritm. http://infoscience.3x.ro/c++/alg_teor.html

    Structuri de control Aplicatii propuse

    Structura liniara 1. a si b retin valorile pentru doua numere intregi citite de la tastatura. Sa se interschimbe valorile celor doua numere. 2. Cunoscand cele 4 note obtinute de un elev la informatica pe parcursul unui semestru si nota de la teza scrieti un algoritm care sa afiseze media lui. 3. Fie un numar format din trei cifre. Sa se afiseze cifrele sale incepand cu cifra unitatilor. 4. Se citeste un numar natural format din 4 cifre. Afisati numerele obtinute in urmatoarele moduri:

  • 9

    schimband prima cifra cu ultima -schimband intre ele cifrele din mijloc 5. Fie a un numar natural format din 5 cifre. Scrieti un algoritm care sa determine si sa afiseze numarul format din prima, a treia si a cincea cifra din a. 6. Un melc a cazut intr-o fantana adanca de x metri. Ziua, melcul urca a cm iar noaptea aluneca b cm. In cate zile va iesi melcul din fantana? 7. In fiecare zi lucratoare din saptamana, Pinocchio spune o minciuna in urma careia ii creste nasul cu x cm pe zi. Sambata si duminica, cand vine Gepetto acasa, pentru a nu-l supara, nu spune nici o minciuna, ba chiar ii scade nasul cu y cm/zi. In fiecare saptamana, singur acasa, Pinocchio continua sirul minciunilor