algoritm_pseudocod

8/11/2019 algoritm_pseudocod

http://slidepdf.com/reader/full/algoritmpseudocod 1/32

ALGORITMI

1. Algoritmi...............................................................................................................................2

1.1. No iunea de algoritm. Caracteristici.ț .............................................................................2

1.1.1. Ce este un algoritm ?...............................................................................................2

1.1.2. Proprietă i caracteristice ale algoritmilor ț ................................................................2

1.1.2.1. Claritatea..........................................................................................................3

1.1.2.2. Generalitatea (universalitatea).........................................................................3

1.1.2.3. Finititudine.......................................................................................................3

1.1.3. tapele re!olvării unei pro"leme............................................................................3

1.2. #"iecte cu care lucrea!ă algoritmii i opera ii permiseș ț .................................................$

1.2.1. %ate.........................................................................................................................$

1.2.2. &presii...................................................................................................................'1.2.2.1. #peratori aritmetici..........................................................................................'

1.3. #peraiile pe care le eectuea!ă un algoritm..................................................................*

1.3.1. #peraii de intrare + ie,ire........................................................................................-

1.3.2. Atri"uiri...................................................................................................................

1.3.3. #peraii de deci!ie...............................................................................................1/

2. Principiile programării structurate......................................................................................13

2.1. 0ntroducere...................................................................................................................132.2. epre!entarea algoritmilor n pseudocod....................................................................13

2.3. tructuri de "a!ă. %escrierea acestora n pseudocod...................................................1$

2.3.1. tructura liniară.....................................................................................................1$

2.3.2. tructura alternativă..............................................................................................1-

2.3.2.1. tructura alternativă %acă 4 atunci 4 altel................................................1-

2.3.2.2. tructura alternativă %acă 4 atunci..............................................................1

2.3.2.3. tructura selectivă electea!ă 4 dintre.........................................................1

2.3.3. tructura repetitivă................................................................................................15

2.3.3.1. tructura C6t timp. . . e&ecută (78ile %o).....................................................15

2.3.3.2. tructura de tip Pentru... e&ecută...................................................................22

2.3.3.3. tructura de tip epetă4.p6nă c6nd..............................................................2$

2.3.3.$ tructura epetă ... c6t timp............................................................................2'

3. %escrierea algoritmilor (Programe pseudocod)..............................................................2*

1



1. ALGORITMI

1.1. No iunea de algoritm. Caracteristici.ț

1.1.1. Ce este un algoritm ?

%espre algoritmi au!im astă!i din ce n ce mai des9 n conte&te dierite. Conceptul de

algoritm nu este nou. :ermenul de algoritm derivă din numele unui matematician persan9 A"u

;a<at =o8ammed i"n =usa al >8oari!mi9 care a scris o carte cunoscută su" denumirea latină

de @i"er algorit8miB.

=atematicienii vului =ediu nelegeau prin algoritm o regulă pe "a!a căreia se eectuau

calcule aritmetice. lterior9 termenul de algoritm a circulat ntrDun sens restr6ns9 e&clusiv n

domeniul matematicii. # dată cu de!voltarea calculatoarelor cuv6ntul algoritm a do"6ndit osemniicaie aparte9 astel nc6t astă!i g6ndirea algoritmică sDa transormat9 dintrDun instrument

speciic matematicii9 ntrDo modalitate undamentală de a"ordare a pro"lemelor n diverse

domenii.

n algoritm repre!intă o metodă de re!olvare a pro"lemelor de un anumit tip.

A re!olva o pro"lemă nseamnă a o"ine9 pentru anumite date de intrare9 re!ultatul

pro"lemei9 date de ie,ire.

Algoritmul este constituit dintrDo succesiune de operaii care descriu9 pas cu pas9 modul de

o"inere a datelor de ie,ire9 plec6nd de la datele de intrare.

e pot scrie algoritmi pentru re!olvarea pro"lemelor din orice domeniu de activitate. %e

e&emplu9 orice reetă de "ucătărie poate i considerată un algoritm prin care9 plec6nd de la

materiile prime9 o"inem printrDo succesiune inită de operaii produsul init.

1.1.2. Proprietă i caracteristice ale algoritmilor ț

Aspectele precedente din seciunea ECe este un algoritm ?Egenerea!ă n mod iresc două

ntre"ări• Pentru orice problemă există un algoritm de rezolvare ?

ăspunsul este N &istă pro"leme pentru care se poate demonstra (lucru diicil) că nu

e&istă algoritmi de re!olvare9 dar ,i pro"leme pentru care nici nu sDa demonstrat ca nu admit o

metodă de re!olvare algoritmică9 dar nici nu sDa descoperit (ncă) soluia algoritmică.

• Orice succesiune de paşi reprezintă un algoritm ?

%in nou9 răspunsul este N Pentru iecare algoritm9secvena tre"uie să ndeplinească trei

condiii

2



1.1.2.1. Claritatea

a iecare moment9 operaia care urmea!ă a i e&ecutată este unic determinată9 deinită ,i

reali!a"ilă (adică poate i eectuată la momentul respectiv9 cu miHloacele disponi"ile).

%e e&emplu9 secvena @%acă plouă stau acasă sau merg la cinemaB nu este clară9 deoarece9 n

ca!ul n care nu plouă9 operaia care se e&ecută nu este unic determinată.

au să presupunem că dorim să o"inem un număr natural9 care se poate scrie ca sumă de

pătrare. ecvena de mai Hos@scrie &I& J KIKB nu este clară deoarece nu putem calcula valoarea

&I& J KI!9 deoarece nu cunoa,tem valorile lui & ,i K.

1.1.2.2. Generalitatea (universalitatea)

# secvenă de pa,i repre!intă un algoritm de re!olvare a unei pro"leme dacă o"ine date de

ie,ire (re!ultate) pentru orice date de intrare speciice pro"lemei.

ecvena de pa,i pre!entată pentru re!olvarea ecuaiei a& J " LM / este generală pentru orice

valori reale ale coeicienilor a ,i ".

%ar9 dacă am i descris o secvenă de pa,i care să re!olve numai ecuaia & J 2 M /9 aceasta nu

ar i ost un algoritm

1.1.2.. !inititudine

e!ultatele pro"lemei se o"in după un număr init de pa,i.

%e e&emplu9 pro"lema @ă se determine toate !ecimalele număruluiB nu are o soluiealgoritmică9 deoarece este un număr iraional9 care are o ininitate de !ecimale. %ar dacă am

enuna pro"lema astel @Fie n un număr natural dat. ă se determine primele n !ecimale ale

numărului B9 această pro"lemă admite o soluie algoritmică9 deoarece primele n !ecimale se pot

o"ine după un număr init de pa,i.

On conclu!ie9 de,i nu putem deini cu riguro!itate noiunea de algoritm9 putem descrie mai

detaliat această noiune

Un algoritm este constituit dintr-o succesiune clară de operaii realizabile! care au ca scopobinerea "ntr-un timp #init a rezultatelor unei probleme! pentru orice set de date de intrare.

1.1.$. %tapele rezolvării unei probleme

epre!entarea unei pro"leme constituie un proces comple&9 care comportă mai multe etape.

1) &naliza problemei n scopul sta"ilirii datelor de intrare9 precum ,i a re!ultatelor

pe care tre"uie să le o"inem prin re!olvarea pro"lemei.

2) %laborarea unui algoritm de re!olvare a pro"lemei.

3) 'mplementarea algoritmului ntrDun lim"aH de programare.

$) (eri#icarea corectitudinii algoritmului propus.

3



n prim pas constă n testarea programului pe diverse seturi de date de test. eturile de date

de te&t tre"uie ela"orate cu atenie9 astel nc6t să se acopere9 pe c6t posi"il9 toate variantele de

e&ecuie a algoritmului9 inclusiv situaii de e&cepie9 ,i să veriice dacă iecare su"pro"lemă a

pro"lemei date este re!olvată corect (dacă este posi"il9 se va testa separat iecare modul de

program).:estarea poate pune n eviden ă9 eventual9 omisiuni sau erori de concepie a algoritmilor9 dar ț

nu garantea!ă corectitudinea algoritmului. Pentru aceasta ar tre"ui să testăm algoritmul pe toate

seturile posi"ile de date de intrare9 ceea ce este practic imposi"il. %in acest motiv9 se impune

utili!area unor metode ormale de demonstrare a corectitudinii algoritmului9 etapă de o"icei

deose"it de la"orioasă9 necesită un aparat matematic comple&.

') &naliza complexităii algoritmului.

On general9 e&istă mai muli algoritmi de re!olvare a unei pro"leme date. Pentru a alege celmai "un algoritm9 tre"uie să anali!ăm ace,ti algoritmi n scopul determinării eicienei lor ,i9 pe

c6t posi"il9 a optimalităii lor.

iciena unui algoritm se evaluea!ă din două puncte de vedere

• din punctul de vedere al spaiului de memorie necesar pentru memorarea valorilor

varia"ilelor care intervin n algoritm (comple&itate spaiu)

• din punctul de vedere al timpului de e&ecuie (comple&itate timp).

Observaie) %laborarea algoritmilor nu este un proces liniar! adeseori este necesar sărevenim la o anumită etapă şi să o repetăm. *e exemplu! după ce am demonstrat corectitudinea

algoritmului şi am analizat e#iciena sa! ne putem pune problema de a optimiza algoritmul sau

numai implementarea sa! caz "n care trebuie să revenim la cea de a doua etapă! de proiectare a

algoritmilor şi de scriere a codului! etapă urmată "n mod necesar de teste de corectitudine!

eliminare a erorilor ! demonstraii de corectitudine! teste de determinare a complexităii! analiza

teoretică a complexităii etc.

1.2. O"iecte cu care lucrea#$ algoritmii i o%era ii %ermiseș ț

On linii mari9 algoritmii lucrea!ă cu două tipuri de o"iecte date i varia"ile. Cu acestea suntș

permise anumite opera ii. Preci!ăm că opera iile care vor i eectuate sunt e&empliicate nț ț

lim"aH de pseudocod.

1.2.1. *ate

#rice algoritm lucrea!ă cu date date de intrare (datele pe care tre"uie să le primească din

e&terior)9 date de ieşire (datele pe care tre"uie să le urni!e!e algoritmul n e&terior)9 precum ,i

date de manevră (date temporare9 necesare algoritmului pentru a o"ine datele de ie,ire pe "a!a

$



datelor de intrare)

%atele cu care lucrea!ă algoritmii pot i clasiicate din mai multe puncte de vedere. # primă

clasiicare a datelor9 n uncie de posi"ilitatea de aD,i modiica valoarea este

• Constante Q date care nu ,i modiică valoarea de e&emplu 1/9 3.1$9 @,ir de

caractereB9 RA<9 als.• &aria"ile Q date care ,i modiică valoarea.

# varia"ilă poate i reerită printrDun nume (o succesiune de litere ,i cire9 primul caracter

iind o"ligatoriu literă) ,i are asociată o valoare. Numele unei varia"ile nu se sc8im"ă pe

parcursul algoritmului9 dar valoarea acesteia se poate modiica.

%e e&emplu9 pentru re!olvarea ecuaiei de orma a' " *9 am utili!at două varia"ile a ,i

". Prin operaia @Cite,te datele de intrare a ,i "B9 acestora li se asocia!ă c6te o valoare reală9

introdusă de la tastatură. tili!area acestor două varia"ile era strict necesară9 pentru a respectageneralitatea algoritmului. %acă am i utili!at două valori constante (de e&emplu9 2 ,i 3.')9

secvena de operaii ar i re!olvat numai ecuaia 2& J 3.' M / 9 deci nu ar i avut utilitate.

#"servai că la nceputul algoritmului am speciicat (am declarat) aptul că a ,i " sunt

numere reale. Această declaraie este necesară9 pentru a cunoa,te natura valorilor care pot i

asociate celor două varia"ile ,i9 ca urmare9 operaiile permise cu acestea. punem că am declarat

tipul varia"ile respective . # varia"ilă poate reine numai valori de tipul declarat.

On uncie de valoarea lor9 datele pot i clasiicate astel • *ate numerice Q au ca valori numere (naturale9 ntregi sau reale)

• *ate al#abetice Q au ca valori caractere sau ,iruri de caractere

• *ate logice Q au valoarea adevărat sau als.

1.2.2. %xpresii

# e&presie este constituită dintrDo succesiune de operan!i9 conectai prin operatori. n

operand poate i o constantă9 o varia"ilă9 sau o e&presie ncadrată ntre parante!e rotunde.

#peratorii desemnea!ă operaiile care se e&ecută asupra operan!ilor. #peratorii care pot i

utili!ai ntrDo e&presie depind de tipul operan!ilor (numerici ntregi9 numerici reali9 caractere9

,iruri de caractere sau logici).

valuarea unei e&presii presupune calculul valorii e&presiei9 prin nlocuirea valorilor

varia"ilelor care intervin ca operan!i n e&presie ,i eectuarea operaiilor speciicate de operatori.

Som pre!enta trei categorii de operatori

1.2.2.1. O%eratori aritmetici#peratorii aritmetici deinesc o operaie aritmetică ,i pot i clasiicai astel

'



a. o%eratorii aritmetici multi%licativi I (nmulirea)9 + (mpărirea9 T (restul mpăririi

ntregi).

Operatorul de "mpărire +, are un eect dierit9 n uncie de tipul operan!ilor.

%acă am"ii operan!i sunt ntregi9 se ace mpărirea ntreagă (se o"ine ca re!ultat un număr

ntreg9 care este c6tul mpăririi primului operand la cel deDal doilea). =ai e&act9 a ,i " douăvaria"ile ntregi. &presia a+" are ca valoare c6tul mpăririi ntregi a lui a la ". %acă9 de

e&emplu9 a are valoarea - ,i " are valoarea 29 e&presia a+" are valoarea 3.

%acă cel puin unul dintre operan!i este real9 se ace mpărirea reală (se o"ine ca re!ultat un

număr real). %e e&emplu9 dacă a ,i " sunt două varia"ile reale9 iar a are valoarea - ,i " are

valoarea 29 e&presia a+" are valoarea 39'.

Operatorul se poate aplica numai asupra operan!ilor ntregi.

". o%eratorii aritmetici aditivi J(adunarea) ,i Q (scăderea)#peratorii aritmetici aditivi ,i multiplicativi sunt "inari (acionea!ă asupra a doi operan!i).

#peratorii aritmetici se pot aplica numai operan!ilor numerici. e!ultatul evaluării unei e&presii

aritmetice este numeric (ntreg sau real9 n uncie de operan!i ,i operatori).

c. O%eratori rela+ionali

#peratorii relaionali descriu relaia de ordine sau de egalitate dintre cei doi operan!i U

(mai mic)9 V (mai mare)9 (mai mic sau egal)9 (mai mare sau egal)9 M (egal)9 (dierit).

#peratorii relaionali sunt operatori "inari ,i se pot aplica numai operan!ilor numerici9 logici

(als U adevărat) ,i caractere.

Saloarea unei e&presii relaionale este ntotdeauna de tip logic (deci poate i adevărat sau

als).

d. O%eratori logici

#peratorii logici deinesc o operaie logică negaie logică D con/uncie logică Q ,i

dis/uncie logică Q sau. #peratorul este unar9 operatorii ,i9 sau sunt operatori "inari. ectul

acestor operatori este următorul

& K & & sau K & ,i Kals als adevărat als alsals adevărat adevărat adevărat als

adevăratadevărat

alsadevărat

alsals

adevăratadevărat

alsadevărat

#peratorii logici se pot aplica operan!ilor logici. Saloarea unei e&presii logice este de tip

logic.

*



1.. O%era+iile %e care le e,ectuea#$ un algoritm

On linii mari9 operaiile care se ac ntrDun algoritm se mpart n trei mari categorii

• #peraii de intrare + ie,ire

•

#peraii de atri"uire• #peraii de deci!ie.

On trecut9 se mai olosea o operaie ,i anume cea de salt.

1.$.1. Operaii de intrare , ieşire

Am arătat că orice algoritm lucrea!ă cu date de intrare ,i ie,ire. Acestea pot i citite sau

scrise.

Prin operaia de intrare (de citire) se nelege preluarea unei date de la un dispo!itiv de

intrare către memoria internă a calculatorului9 n !ona de memorie re!ervată pentru aceasta9 adică

n varia"ilă. %ispo!itivele de intrare pot i tastatura (cel mai des utili!ată) o unitate de disc8etă

o unitate de disc9 etc.

On pseudocod9 pentru citire vom olosi operaia Citeşte.

Prin operaia de ie-ire (scriere) se nelege preluarea unei date din memoria internă D adică

dintrDo varia"ilă D ,i transerul ei către un dispo!itiv de ie,ire. %ispo!itivele de ie,ire pot i

monitorul9 o unitate de disc9 imprimanta9 etc.

Pentru scriere vom olosi operaia Scrie.

%eocamdată vom presupune că dispo!itivul de intrare este tastatura9 iar cel de ie,ire este

monitorul. ă anali!ăm algoritmul de mai Hos Q scris n pseudocod D care cite,te un număr ntreg

,i l tipăre,te

întreg aCiteşte aScrie a

=ai nt6i am declarat varia"ila a9 de tip ntreg D adică are posi"ilitatea de a reine numere

ntregi. rmea!ă să se eectue!e operaia de citire a varia"ilei a. Aceasta nseamnă că se a,teaptăintroducerea de la tastatură a datei ntregi. n ca!ul n care introducem numărul 1/9 varia"ila a va

reine 1/9 dacă introducem numărul 1-*9 varia"ila a va reine 1-*.

O"serva+ii

• %upă scriere9 coninutul varia"ilei răm6ne nemodi,icat.

Fie secvena de mai Hos ,i introducem de la tastatură 1-. Pe monitor apare de două ori

numărul 1-.

întreg aCiteşte aScrie aScrie a

-



• a o nouă citire9 coninutul vec8i al varia"ilei se %ierde.

Fie secvena de mai Hos. Presupunem că introducem de la tastatură 1/9 12 (n această

ordine). Atunci varia"ila a va reine 129 deci pe monitor apare 12.

întreg a;Citeşte a

Citeşte aScrie a;

e pot citi mai multe varia"ile cu o singură operaie cite,te ,i se pot tipări valorile reinute de

mai multe varia"ile cu o singură operaie crie.

'em%lu Fie secvena

real a,b,c;Citeşte a,b,cScrie a,b,c

%acă introducem 1.29 D1.39 12.9 atunci a reine 1.29 " reine D1.39 c reine 12.. Pe monitor se

tipăre,te 1.2 /1. 12.0.1.$.2. &tribuiri

Prin operaia de atri"uire se reine o anumită dată ntrDo varia"ilă. a are mai multe orme9

pe care le vom pre!enta pe r6nd.

!orma 1.

v<—dată

emniicaia este următoarea

•

v este numele unei varia"ile de un tip oarecare.• notaia pentru operaia de atri"uire

• dată D o valoare de un tip oarecare

Cu o singură excepie! tipul variabilei trebuie să coincidă cu tipul valorii atribuite.

'em%le

întreg a;a 10;

Saria"ila a va reine 1/.

real b; b 7.25

Saria"ila " reine D-.2'.

Şir c;c 'latina si il!s!ie'

Saria"ila c reine valoarea de tip ,ir Wlatina si ilosoieW.

&cepia este următoarea unei variabile de tip real i se poate atribui o dată de tip "ntreg .

real d;d 7

!orma 2.

v1 v2

unde9 vl ,i v2 sunt nume de varia"ile. Cu o e&cepie9 tipul celor două varia"ile tre"uie să



coincidă. ectul este că varia"ila vl va reine coninutul varia"ilei v2. %upă aplicarea acestei

operaii9 coninutul varia"ilei v2 răm6ne nemodiicat9 iar coninutul iniial al varia"ilei vl se

pierde.

Conclu#ie. 0u este indi#erent modul de scriere ai variabilelor "n cadrul atribuirii . Atri"uirea

a " nu este identică cu atri"uirea " a. ste adevărat că9 după atri"uire9 cele două varia"ile vor avea acela,i coninut. nsă este important ce coninut (al lui " după prima atri"uire9 al lui a după a

doua). Aici ncepătorii gre,esc deseori. &tenie

!orma .

v e"#resie

0niial se evaluea!ă e&presia9 iar valoarea o"inută este atri"uită varia"ilei v. Considerăm că

dacă cel puin unul din operan!i este real9 tipul e&presiei este real si poate i atri"uit doar unei

varia"ile de tip real9 iar dacă toi operan!ii sunt ntregi9 tipul e&presiei este ntreg ,i poate i

atri"uit unei varia"ile de tip ntreg sau real. Facem convenia ca operatorul 343 va da ntotdeauna

un re!ultat real9 c8iar dacă am"ii operan!i sunt ntregi.

O"serva+ii. %upă atri"uire9 varia"ilele care sunt operan!i răm6n nemodiicate n ce prive,te

coninutul. &cepie ace9 eventual9 varia"ila v n ca!ul n care igurea!ă ,i ca operand n

e&presie. %e asemenea9 primele două orme sunt particulari!ări ale acesteia.

a ce olose,te atri"uirea? Atri"uirea are un rol uria, n programare.

ă ncercăm o sistemati!are a ca!urilor c6nd olosim atri"uirea.

1. Ini+iali#$ri.

Aproape orice program olose,te varia"ile. Cum #acem ca acestea să conină o valoare pe

care o dorim? # posi"ilitate (singura studiată p6nă n pre!ent) ar i să citim valorile respective.

Procedeul este greoi ,i c8iar carag8ios n ca!ul n care valoarea de pornire este ntotdeauna

aceea,i. ă ne imaginăm că se dore,te ca valoarea iniială a trei varia"ile (a5"5c) să ie *. Ce

acem? Ontre"ăm care este valoarea lui a9 tastăm /9 ntre"ăm care este valoarea lui "9 tastăm /

,.a.m.d. ă im serio,i Saloarea iniială poate i sta"ilită prin trei instruciuni de atri"uire9 ca mai

Hosa 0; b 0; c 0;

tabilirea valorilor cu care anumite variabile intră "n calcule se numeşte iniializare

'niializările se #ac cu a/utorul instruciunii de atribuire.

2. Calcule.

=aHoritatea programelor eectuea!ă calcule. On aara tipăririi imediate a re!ultatului evaluării

unei e&presii9 e&istă ,i posi"ilitatea ca acesta să ie păstrat ntrDo varia"ilă (de multe ori este

imposi"il să procedăm altel). On astel de ca!uri se olose,te instruciunea de atri"uire. &istă9

n principal9 două orme n care atri"uirea intervine n calcule.

!orma direct$. Unei variabile i se atribuie o expresie cu operanzi variabile! constante! alii

5



dect variabila care va reine rezultatul. *upă atribuire! toi operanzii rămn nemodi#icai .

!orma indirect$. Unei variabile i se atribuie o expresie cu operanzi variabile! constante! "n

care intră şi valoarea pe care o reine variabila căreia i se #ace atribuirea.

3. Co%iere. %e multe ori9 este necesar ca o valoare re inută de o varia"ilă să ie reinută ,iț

de alta. =otivele sunt diverse. # simplă instruciune de atri"uire ne re!olvă pro"lema de mai sus.%e e&emplu9 dacă ' ,i 6 sunt două varia"ile de tip real care rein două valori oarecare9 ,i dorim

ca varia"ila ' să reină valoarea pe care o reine 69 eectuăm atri"uirea ' 6. Atenie *upă

atribuire! coninutul variabilei 3 rămne nesc4imbat . ăm6ne să preci!ăm că un raionament de

genul dacă varia"ila ' a preluat valoarea pe care o reine 69 re!ultă că 6 nu mai reine nici o

valoare9 nu are ce căuta la programare. Ca ,i cum am avea două vali!e9 ,i dacă luăm o căma,ă

din una ,i o punem n cealaltă9 prima vali!ă nu mai conine căma,a mutată. n ca! particular9 dar

des nt6lnit n programare este intersc4imbarea coninutului a două variabile (evident9 de acela,itip).

Fie varia"ila de tip 7ntreg ' care reine valoarea l ,i varia"ila de tip 7ntreg 6 care reine

valoarea 2. %orim să inversăm coninutul celor două varia"ile9 adică ' să reină 2 ,i 6 să reină 1.

e cere ca secvena să răm6nă vala"ilă indierent ce valori ar reine ' ,i 6. Ce putem ace? %acă

e&ecutăm atri"uirea 6 ' nu am re!olvat nimic ntruc6t coninutul lui 6 se pierde. %acă

e&ecutăm atri"uirea ' 6 am pierdut coninutul varia"ilei '. %acă e&ecutăm două atri"uiri ,i

anume ' 28 6 l raionamentul nu este general (dacă ' ar i reinut 3 ,i 6 valoarea $ secvenanu ar i ost vala"ilă). Atunci?

Pentru re!olvare9 olosim ,i o altă varia"ilă9 de acela,i tip9 pe care o notăm m. a are rolul

unei varia"ile au&iliare (nu ne olose,te dec6t ca să reali!ăm intersc8im"ul de valori)9 lată pa,ii

de lucru

• varia"ila m va prelua valoarea reinută de 6 m 6

• 6 va prelua valoarea reinută de ' 6 '8

• & va prelua valoarea reinută de m ' m.

1.$.$. Operaii de decizie

On pseudocod operaia de deci!ie are orma următoare

$acă c!ndi%ie at&nci !#era%ie1

altel !#era%ie2

Sdacă

1/



=odul de e&ecutare este următorul

• e testea!ă condiia (condiia este o e&presie logică)

• %acă condiia este ndeplinită (ia valoarea true)9 se e&ecută operaia19 altel (ia

valoarea ,alse) se e&ecută operaia2

• On continuare se e&ecută operaia alată după operaia deci!ională.

O"serva+ie. %eci!ia constă n a alege o operaie sau alta spre a i e&ecutată (n nici un ca!

am6ndouă). ă dăm un e&emplu se citesc două valori "ntregi a şi b. e cere să se tipărească cea

mai mare dintre ele.

întreg a,bCiteşte aCiteşte b$acă a(b at&nci Scrie a

altel Scrie bSdacă

0n primul r6nd9 se testea!ă condiia. On e&emplul nostru ea este a9". n ca!ul n care valoarea

reinută de varia"ila a este mai mare dec6t cea reinută de varia"ila "9 condiia este ndeplinită ,i

se tipăre,te a. Contrar9 se tipăre,te ".

&vem posibilitatea ca operaiile subordonate operaiei decizionale să #ie tot operaii

decizionale. &emplu se citesc $ valori reale a5 "5 c5 d. ă se evalue!e e&presia

<+

=+−

>++

=

/..

/9/9

d cba

d cbad cba

%

'em%lu numeric. Fie aMl9 "M29 cM39 dM$. Avem cJdM-V/9 re!ultă că se va tipări

aJ"MlJ2M3. Anali!ai algoritmul care urmea!ă

real a, b, c, d;Citeşte a, b, c, d $acă c)d(0 at&nci

Scrie a)b altel$acă c)d*0

at&nci Scrie a+b ltel Scrie a-b SdacăSdacă

%acă suma cd nu este mai mare dec6t /9 re!ultă că este mai mică sau egală cu *. %in acest

motiv9 clau!a alt,el a primului dacă va conine o altă operaie deci!ională (dac$) n urma căreia

se va decide dacă cd* sau cd*. On ca!ul n care cd nu este *9 singura posi"ilitate este

cd* (pentru că deHa cunoa,tem că nu este mai mare ca /). Acesta este motivul pentru care nu

mai acem testul cd*.

11



• #"servai aptul că e&presiile se pot calcula ,i tipări prin utili!area operaiei

:crie.

O problemă interesantă este şi aceasta) dacă algoritmul impune ca operaia care urmează

lui altfel să lipsească! cum procedăm?

Pseudocodul admite o ormă particulară a operaiei deci!ionale.$acă c!ndi%ie at&nci #era%ieSdacă

;rinci%iul de e'ecutare

• e testea!ă condiia

• On ca!ul n care aceasta este ndeplinită9 se e&ecută operaia alată după atunci9

altel se trece la operaia următoare.

'em%lu. e cite,te o valoare ntreagă. On ca!ul n care aceasta este pară (se mparte e&act la

2) se va ai,a mesaHul Eam citit un num$r %arE. Altel9 programul nu va da mesaH.

întreg nr;Citeşte n

$acă22

nr nr =

at&nci

Scrie 'a/ citi &n n&/ar #ar

Sdacă

Cum putem gre,i?

# eroare9 des nt6lnită este a,a numita eroare a testului inutil . eluăm e&emplul n care

evaluăm e&presia

<+

=+−

>++

=

/..

/9

/9

d cba

d cba

d cba

%

nii scriu instruciunea deci!ională astel

Citeşte a, b, c, d $acă c)d(0 at&nci Scrie a)b altel $acă c)d*0 at&nci Scrie a+b altel $acă c)d<0 at&nci Scrie a-b Sdacă SdacăSdacă

12



%acă cd9* nu este adevărat9 nseamnă că este mai mic sau egal cu /9 ,i dacă nu este /9 este

n mod sigur strict mai mic ca /. Nu are rost să acem un test suplimentar. Calculatorul nu

g6nde,te9 l ace9 programul uncionea!ă corect9 dar se pierde inutil timp de calcul

13



2. ;RINCI;IIL ;ROGRAM<RII :TR=CT=RAT

2.1. Introducere

Cre,terea comple&ităii aplicaiilor a impus la nceputul anilor X-/ apariia unei noi

paradigme n programare programarea structurată. copul era de a de!volta noi te8nici de

programare9 care să permită de!voltarea unor programe ia"ile9 u,or de ela"orat n ec8ipă9 u,or

de depanat9 de ntreinut ,i de reutili!at.

n prim principiu al programării structurare este modulizarea. Pentru proiectarea unor

aplicaii comple&e9 este necesară descompunerea pro"lemei care tre"uie re!olvată n

su"pro"leme relativ independente9 pentru iecare dintre aceste su"pro"leme scriinduDse module

de program mai simple. Fiecare modul eectuea!ă un set de prelucrări speciice ,i este relativindependent de celelalte module9 cu care comunică prin intermediul unui set de parametri9 care

constituie interaa. AvantaHele sunt multiple. Cum la orice irmă se lucrea!ă n ec8ipă9 modulele

de program pot i implementate de mai muli programatori. =odiicarea unui modul nu aectea!ă

celelalte module. Fiecare modul poate i implementat9 testat9 depanat9 modiicat9 independent de

celelalte.

n alt principiu undamental este structurarea datelor şi a prelucrărilor . Programatorul are

posi"ilitatea de aD,i grupa datele n colec ii9 organi!area după anumite reguli9 denumite structurițde date.

Prelucrările asupra datelor sunt structurare separat. Conorm teoremei de structură YZmD

;acopini9 orice prelucrare poate i descrisă prin compunerea a trei structuri undamentale

structura liniară +secvenială9 structura alternativă ,i structura repetitivă.

2.2. Re%re#entarea algoritmilor 7n %seudocod

Pentru ca o secvenă de operaii să constituie un algoritm9 ea tre"uie să ie clară9 adică laorice moment operaia care urmea!ă a i e&ecutată tre"uie să ie unic determinată9 deinită ,i

reali!a"ilă (să poată i eectuată la momentul repesctiv9 cu miHloacele disponi"ile). %eDa lungul

timpului sDau impus două modalităi de repre!entare a algoritmilor sc4eme logice ,i limba/ele

de tip pseudocod .

c8emele logice constituie o metodă de repre!entare graică9 oarte sugestivă9 dar cu o serie

de de!avantaHe se dă o egală importană componentelor principale ca ,i detaliului9 prin urmare

sc8emele logice devin deose"it de stuoase ,i greu de urmărit pentru aplicaiile mai comple&e9c6nd este necesară modulari!area9 este practic imposi"il de pus n evidenă legăturile dintre

1$



module n cadrul sc8emei logice.

%in acest motiv9 treptat sDa impus o altă metodă de repre!entare a algoritmilor pseudocodul.

n lim"aH de tip pseudocod este un ansam"lu de convenii9 respectate n mod sistematic9 care

deinesc operaiile permise (denumite ,i instruciuni) pentru repre!entarea algoritmilor.

2.. :tructuri de "a#$. >escrierea acestora 7n %seudocod

tructurile de "a!ă utili!ate n descrierea algoritmilor sunt de trei eluri

• tructura liniară

• tructura alternativă

• tructura repetitivă

2.$.1. tructura liniară

Som deini structura liniară astel

• #rice operaie (citire + scriere9 atri"uire9 deci!ională considerată n ansam"lul ei)

constituie o structură liniară

• %acă :1 ,i :2 sunt structuri (de orice tip)9 atunci

S1S2

este structură liniară.

Pornind de la deiniie9 se aHunge la următoarea ormă de structură liniară!#era%ia 1!#era%ia 2

!#era%ia n.

%e ce? #peraia 1 este structură liniară9 operaia 2 este structură liniară9 re!ultă că operaia 19

urmată de operaia 2 este structură liniară ,i cum operaia 3 este structură liniară9 nseamnă că

operaia 1 urmată de operaia 29 urmată de operaia 3 este structură liniară ,.a.m.d. #rdinea de

e&ecutare este operaia 19 apoi operaia 29 9 p6nă la operaia n.

'em%lul 1. e citesc două variabile reale. ă se intersc4imbe coninutul lor şi să se a#işeze.

real a, b, /an;Citeşte a, b

/an a;a b;

b /an;Scrie a, b

• se citesc cele două varia"ile D operaia 19 de citire

• varia"ilei man i se atri"uie coninutul varia"ilei a Q operaia 29 de atri"uire

• varia"ilei a i se atri"uie coninutul varia"ilei " D operaia 39 de atri"uire

1'



• varia"ilei " i se atri"uie coninutul varia"ilei man Q operaia $9 de atri"uire

• se ai,ea!ă a5 " D operaia '.

'em%lul 2. e citesc două valori reale. ă se a#işeze valoarea cea mai mică .

real a, b;Citeşte a, b$acă a < b at&nci scrie aaltel

scrie bS$aca

Prima operaie este de citire. A doua operaie este cea deci!ională D aceasta privită n

ansam"lul ei. a su"ordonea!ă alte două operaii de tipărire (scriere).

'em%lul . e citesc două variabile "ntregi. ă se intersc4imbe coninutul lor! #ără a #olosi

o variabilă auxiliară de manevră.

întreg a, b;Citeşte a, ba a)b

b a+ba a+bScrie a, b

Pentru valorile citite ale lui a ,i " (aM39 "M$) algoritmul uncionea!ă astel

• lui a i se atri"uie valoarea 3J$M-

• lui " i se atri"uie valoarea -D$M3

• lui a i se atri"uie valoarea -D3M$

• se ai,ea!ă a? si " (re!ultat corect).

'em%lul ?. e citesc două valori "ntregi a şi b. e cere să se a#işeze media lor aritmetică.

Pro"lema are o capcană. %in aptul că valorile citite sunt ntregi9 nu tre"uie trasă conclu!ia

că media aritmetică este număr ntreg (de e&emplu dacă citim ,i 5 media va i 9'/). Aceasta

nseamnă că varia"ila care reine media tre"uie să ie de tip real.

întreg a, b;real /edie;Citeşte a, b

/edie <— 3a)b42Scrie /edie

'em%lul @. e citeşte un număr natural #ormat din $ ci#re. e cere să se a#işeze suma

ci#relor sale. %xemplu) dacă citim 12$ se va a#işa 5 .

1*



Cum re!olvăm? %acă o varia"ilă reine un număr9 nu putem n mod direct să vedem care

sunt cirele sale. :re"uie să găsim ceva care să ne permită accesul la ele. Cunoa,tem aptul că

restul 7m%$r+irii la 1* al unui num$r este ultima sa ci,r$. =uli vor i tentai să găsească

prima ciră a numărului ,i nu ultima. %ar ce importană are n ce ordine adunăm cirele? Putem

aduna 1J2J3 dar ,i 3J2J1. e!ultatul este acela,i. :ot este "ine că putem o"ine ultima ciră. Ceacem cu celelalte? %acă am reu,i să o"inem numărul ără ultima ciră pro"lema ar i re!olvată

(am putea repeta procedeul). ste posi"il. Num$rul ,$r$ ultima ci,r$ este dat de ctul 7ntreg

dintre num$r -i 1*. On conclu!ie9 vom o"ine suma cirelor numărului citit adun6nd9 de iecare

dată9 ultima ciră ,i o"in6nd numărul ără ea.

întreg ", s;Citeşte "s 0s s)" /!d 10

" " div 10s s)" /!d 10" " div 10s s )" /!d 10Scrie s

#peraia prin care o"inem restul mpăririi unui număr la o valoare am notatDo cu mod9 iar

cea prin care o"inem c6tul ntreg al unei mpăriri am notatDo cu div. &emple

126 /!d 10 *6126 div 10*12.

On pseudocod putem sim"oli!a operaiile a,a cum dorim. Condiia este să inem minte ce am

notat prin operaia respectivă (eventual să preci!ăm aceasta alăturat9 printrDun mic comentariu).#"servai aptul că la varia"ila s9 care a ost iniiali!ată cu /9 sDa adunat de iecare dată

ultima ciră. %ar nu vă deranHea!ă aptul că aceea,i secvenă a ost repetată de 3 ori? %ar dacă

numărul avea mai multe cire? Som nvăa că astel de algoritmi pot i scri,i mult mai eicient9

prin utili!area structurilor repetitive.

'em%lul B. e citesc $ numere naturale. e cere să se a#işeze primul număr! suma dintre

primul şi ai doilea! suma primelor $ numere. %xemplu) dacă se citeşte 2! 6 şi 7! se va a#işa 2! 7!18.

Pentru re!olvare9 se adună la o varia"ilă s iniiali!ată cu /9 pe r6nd9 cele trei numere. Ce

o"servăm? Faptul că se citesc 3 numere nu nseamnă că tre"uie să re!ervăm 3 varia"ile pentru

citire. ste suicient să avem una (nr). a prima citire ea va reine primul număr. %upă ce acesta

a ost adunat la coninutul varia"ilei s9 nu mai avem nevoie ca programul săDl reină. Citirea n

acela,i loc (aceea,i varia"ilă) a numărului următor (se cite,te tot varia"ila nr) conduce la

pierderea coninutului iniial al varia"ilei. [i aici9 deranHea!ă aptul că o secvenă este repetată.

întreg s, nr;s 0Citeşte nr s s)nr Scrie s

1-



Citeşte nr s s)nr Scrie sCiteşte nr s s)nr Scrie s

2.$.2. tructura alternativă

2..2.1. :tructura alternativ$ >ac$ atunci alt,eltructura alternativă >ac$ atunci alt,el se deine,te astel

%acă 1 ,i 2 sunt structuri ,i este o condiie9 atunci

$acă at&nci S1 altel S2S$acă

este structură alternativă.

=ecanismul de e&ecutare este

• se evaluea!ă condiia

• dacă aceasta este ndeplinită se e&ecută 19 altel se e&ecută 2.

'em%lul 1. ă se scrie un algoritm care citeşte un număr natural +comanda. *acă acesta

este 9 se vor citi două numere "ntregi a şi b şi se va a#işa suma lor! contrar se vor citi două

numere reale x şi y şi se va a#işa suma lor.

On am"ele ca!uri tre"uie e&ecutate mai multe instruciuni. Pentru aceasta am olosit structura

alternativă.

întreg c!/anda, a, b, sl;real ", 8, s2;Citeşte c!/anda$acă c!/anda * 0 at&nci Citeşte a,b

sl )b Scrie sl ltel Citeşte ", 8 s2 ")8 Scrie sS$acă

'em%lul 2. e citesc a şi b ! numere reale. ă se rezolve ecuaia de gradul 1) ax : b ; 9.

On matematică9 ecuaia de gradul 1 este deinită numai dacă a ≠ /. On inormatică9 tre"uie

tratat ,i ca!ul a*9 pentru că nimeni nu garantea!ă că utili!atorul nu gre,e,te la introducerea

datelor.

Cum g6ndim? OntrDo primă etapă algoritmul nostru va testa dacă a este dierit de *. On ca!

1



ltel Secven aț n)1

SSelecteaă

unde

:ecven aț 1 :ecven aț n1 sunt secven e de instruc iuni9 iarț ț ListaEvalori1 ListaEvalorin

sunt predicate satisăc6nd

Lista_valori i Lista_valori ˄ j M / /i ≠∀

tructura este ec8ivalentă cu următorul te&t Pseudocod

$acă i*v1 at&nci a1 altel $acă i*v2 at&nci a2 altel . . .

$acă i*vn t&nci n S$acă ... S$acăS$acă

2.$.$. tructura repetitivă

tructura repetitivă apare n următoarele variante

• condiionată anterior D este de două eluri

o Ct tim%... e'ecut$ (File >o)

o ;entru... e'ecut$ (!or)

• condiionată posterior

o Re%et$ ... %n$ cnd (Re%eat until)

o 'ecut$ ... ct tim% (>o File)8

ingura structură indispensa"ilă este ct tim%... e'ecut$ (Hile >o) D restul se poate o"ine

din aceasta.

2...1. :tructura Ct tim%. . . e'ecut$ (File >o)

tructura de tip Ct tim%... e'ecut$ se deine,te astel

%acă este condiie ,i : o structură atunci

C@t ti/# e"ec&tă SSC@t ti/#

este o structură de tip Ct tim% ... e'ecut$.

Principiul de e&ecutare este următorul

P1 e evaluea!ă condiia. %acă este ndeplinită9 se e&ecută : ,i se trece la P29 altel

e&ecutarea se nc8eie

P2. e reia pasul P0.

2/



O"serva+ie. e o"servă aptul că : se e&ecută numai dacă condiia este ndeplinită. %in acest

motiv9 structura se mai nume,te condi+ionat$ anterior. %e la "un nceput preci!ăm următoarele

este o"ligatoriu să olosim structura Ct tim%...e'ecut$ atunci c6nd sunt ndeplinite

simultan două condiii

• instruciunea su"ordonată se e&ecută (de c6te ori este ca!ul) numai dacă estendeplinită o anumită condiie

• n momentul n care se intră n secvena repetitivă nu se ,tie de c6te ori aceasta

se va e&ecuta.

'em%lul 1. e citeşte un număr natural n ! di#erit de 0. ă se a#işeze suma ci#relor sale.

*acă se citeşte 248 se va a#işa 18.

întreg i, n, s;Citeşte ns 0C@t ti/# n ˂˃ 0 e"ec&tă s s)n /!d 10; n n div 10SC@t ti/#Scrie s

'em%lu numeric. e cite,te n M 2$.

2$\/9 2$ mod 1/ M 9 sM/JM nM2$

2$\/9 2$ mod 1/ M $9 sMJ$M12 nM2

2\/9 2 div 1/ M /9 sM12J2M1$ nM/

/M/9 se ai,ea!ă sM1$.

'em%lul 2. e citeşte un număr natural n. ă se a#işeze numărul obinut prin inversarea

numărului citit. &emplu %acă citim n2?0 se va ai,a 0?2.

ă considerăm două numere al doilea număr a ost o"inut din primul prin adăugarea la

s6r,it a unei cire ($'* ,i $'*3). Avem relaia $'*3M$'*&1/J3. vident9 relaia este adevărată

pentru oricare două numere naturale care ndeplinesc condiia de mai sus. ste clar că numărul

inversat va ncepe cu ultima ciră a numărului citit. ă presupunem că am citit 2$. Som construi

numărul inversat astel

M/&l/J9 ( este ultima ciră a numărului citit ,i răm6ne 2$).

$M&1/J$9 ($ este ultima ciră a numărului rămas ,i se o"ine 2)

$2M$&1/J2. (2 este ultima ciră a numărului 2 ,i se o"ine /).

întreg i, n, s;Citeşte ns 0C@t ti/# n ˂˃ 0 e"ec&tă

21



s s-10)n /!d 10 n n div 10SC@t ti/#Scrie s

'em%lul . e citesc numerele naturale nl şi n2. ă se calculeze produsul lor! #ără a utiliza

operatorul de "nmulire.

Algoritmul se "a!ea!ă pe aptul că nmulirea este o adunare repetată. %e e&emplu9 dacă

citim 3 ,i $9 calculăm produsul astel 3J3J3J3M12 (am adunat de $ ori). Adunarea repetată se

ace utili!6nd structura Ct tim% ... e'ecut$.

Poate că vă vei ntre"a de ce am olosit Ct tim% n * e'ecut$˂˃ (at6t timp c6t9 este evident9

numărul de e&ecutări ale instruciunii su"ordonate lui Ct tim%... e'ecut$ este cunoscut de la

"un nceput). A,a este. %ar dacă olosirea structurii c6t timp ...e&ecută nu este indispensa"ilă9 nu

nseamnă că nu avem voie sDo olosim.

întreg nl, n2, s, i;Citeşte nl, n2s 0i 1C@t ti/# i <* n2 e"ec&tă s s)nl i i)1SC@t ti/#Scrie s

'em%lul ?. e citesc două numere naturale nl şi n2. e cere să se calculeze ctul şi restul

"mpăririi "ntregi a lui n1 la n2 ! #ără a utiliza operatori de "mpărire.

Cum procedăm? A,a cum nmulirea se poate ace prin adunare repetată9 tot a,a mpărirea se

poate ace prin scădere repetată. %in dempărit (n1) se scade (dacă este posi"il D dacă

dempăritul este mai mare sau egal cu mpăritorul) mpăritorul (n2)9 ,i la iecare scădere se

adună 1 la c6t (iniial /). C6nd ne oprim? Atunci c6nd valoarea rămasă (n urma scăderilor

repetate din dempărit a mpăritorului) este mai mică dec6t mpăritorul.

&emplu numeric. n1l*5 n2.

1* / *8 n11*/J8 cl8

J / *8 n1J/?8 c28

? / *8 n1?/l8 c8

1 / *8 se iese din ciclu se a,i-ea#$ ctul () -i restul l.

întreg nl, n2, c;

Citeşte nl, n2c 0C@t ti/# nl+n2 (* 0 e"ec&tă

22



il9 s sJ1 sM/JlMl

i29 s sJ2 sMlJ2M3

i39 s sJ3 sM3J3M*

i$9 ssJ$ sM*J$M1/.

4444

Pre!entăm algoritmul o"inut

întreg n, i, s;read nS 0Aentr& i 1, n e"ec&tă s s)iSAentr&Scrie s

'em%lul 2. ă se calculeze suma) S = 0,1 + 0,2 +...+ 0,9.

n elev "un la matematică ,i dă seama imediat cum se re!olvă pro"lema cu aHutorulormulelor9 sau olosind algoritmul precedent. On ce ne prive,te am ales varianta de mai Hos.

Avem 5 pa,i. a iecare pas se adună un număr. e!ultatul este de tip real (varia"ila s are acest

tip). ste adevărat9 varia"ila de ciclare nu poate lua dec6t valori ntregi. ecurgem la următorul

artiiciu vom considera o varia"ilă i care ia valori de la 1 la 5. a iecare pas se adună valoarea

reală i41*. C6nd i este 19 se adună 1+1/M/919 c6nd i este 2 se adună 2+1/M/92 ,.a.m.d.

întreg ireal s

s 0Aentr& i 1, B e"ec&tă s s)i10SAentr&Scrie s

'em%lul . e citeşte n număr natural. ă se calculeze suma)

n1 •••++••+•+= ...21...321211

Ce avem de ăcut? #"servăm că avem n pa,i. a pasul i se adună valoarea 1K2.Ki5 iar i

este cuprins ntre 1 ,i n. Avem

Pasul 1. e adună l

Pasul 2. e adună 1I2

444..

Pasul n. e adună 1I2I3I...In.

%acă la pro"lemele anterioare valoarea care se adună se o"ine u,or9 aici este puin mai

complicat. %e ce? Pentru că ,i ea tre"uie calculată. Cum o calculăm? Folosim un nou ciclu? On

nici un ca!. e poate mai simplu. #"servăm aptul că singura dierenă ntre valorile care se

adună la pasul i ,i pasul il este că valoarea adunată la pasul iJ1 se o"ine nmulind cu il

valoarea adunată la pasul i. &emplu a pasul 2 se adună 1K2. a pasul 3 se adună 1K2K9 adică

(1I2)I3. ă notăm cu % valoarea care se adună la iecare pas. 0niial % este 1. a pasul il9 nainte

2$



de a i adunată9 valoarea % se nmule,te cu il.

întreg i, s, #, n;Citeşte ns 0A 1

Aentr& i 1, n e"ec&tă # A-i s s)#SAentr&Scrie s

ni%ial s * 0; # * 1.Aas&l 1. # #-l; #*l-l*l; s s)#; s*0)l*l;Aas&l 2. # #-2; #*l-2*2; s s)#; s*l)2*6;Aas&l 6. # #-6; #*2-6*D; s s)#; s*6)D*B;

'em%lul ?. e citesc n numere ntregi. e cere să se ai,e!e cel mai mare număr citit.&emplu Avem n9 iar numerele sunt D-9 59 2. e va ai,a 5.

Pe e&emplul anterior identiicăm cel mai mare număr din ,ir astel

cel mai mare număr este /J

9/J9 deci cel mai mare număr este

29 deci cel mai mare număr răm6ne

9 cel mai mare număr răm6ne .

Am parcurs integral ,irul ,i cel mai mare număr răm6ne . Să dai seama că raionamentulde mai sus răm6ne vala"il pentru un ,ir de n numere (n9 număr natural oarecare). #"servăm că

nu este necesar să reinem9 la un anumit moment9 dec6t un singur număr (cel anali!at) precum ,i

ma&imul dintre cele anterior anali!ate. e cite,te primul număr n varia"ila ma'. Apoi avem n/l

pa,i9 pe care i numerotăm de la 2 la n. a iecare pas citim un număr n varia"ila nr9 apoi l

comparăm cu valoarea reinută n varia"ila ma'9 rein6nd permanent n ma' valoarea cea mai

mare.

întreg 1, /a", n, nrCiteşte n, /a"Aentr& i 2, n e"ec&tă Citeşte nr $acă nr ( /a" at&nci /a" nr S$acăSAentr&Scrie /a"

2.... :tructura de ti% Re%et$.%n$ cnd

Fie : o structură ,i o condiie. Atunci

2'



:e#etă S

#@nă c@nd

este o structură Re%et$. . .%n$ cnd

Principiul de e&ecutare este următorulP1 e e&ecută :

P2 %acă este nu este ndeplinită9 se trece la P19 altel e&ecutarea este nc8eiată.

#"servai aptul că : se e&ecută ntotdeauna o dată. Apoi se testea!ă dacă se mai e&ecută sau

nu. i această structură poate i simulată cu aHutorul structuriiȘ Ct tim% ... e'ecut$

S;C@t ti/# n!t e"ec&tă SSC@t ti/#

0ată cum se poate calcula suma primelor n (n 9 1) numere naturale prin utili!area acesteistructuri

întreg n, i, s;Citeşte ni 1s 0:e#etă s s)i i i)l

#@nă c@nd i(nScrie s

ă vedem cum decurge algoritmul după citirea lui n (citim )• i ia valoarea 19 iar s ia valoarea /

• s ia valoarea /J1M19 iar i ia valoarea 2

• i nu este mai mare dec6t 39 deci s ia valoarea 1J2M39 iar i va lua valoarea 3

• i nu este mai mare ca 39 deci s va lua valoarea 3J3M*9 iar i va lua valoarea $

• i este mai mare dec6t n9 deci se trece la instruciunea următoare9 unde se ai,ea!ă

valoarea *.

# astel de structură se utili!ea!ă n lim"aHul Pascal.

2...? :tructura Re%et$ ... ct tim%

Fie : o structură ,i o condiie. Atunci

:e#etă Sc@t ti/#

este o structură Re%et$. . .ct tim%.

Această structură are acela,i mecanism de e&ecutare ca Re%et$.. .%n$ cnd9 dierena iind

dată de aptul că secvena : se e&ecută din nou dacă este ndeplinită.

2*



# astel de structură se utili!ea!ă n lim"aHul C.

. >:CRIRA ALGORITMILOR (;ROGRAM

;:=>OCO>)

;ro"lema 1. e citesc trei numere "ntregi a, b, . ă se a#işeze "n ordine crescătoare.

0deea de lucru este următoarea

• se compară primele două (a ,i ")

• după ce se cunoa,te ordinea ntre acestea9 se ncearcă plasarea lui c aă de ele.

%acă a este mai mic dec6t " tre"uie vă!ut unde l plasăm pe c. l poate i mai mic dec6t a9

deci ordinea ar i c5 a5 " sau mai mare sau egal cu a. n acest din urmă ca!9 c tre"uie comparat cu

". %acă el este mai mic dec6t "9 ordinea este a5 c5 "9 n ca! contrar9 este a5 "5 c. :ot a,a seraionea!ă n situaia n care a nu este mai mic dec6t " (este mai mare sau egal). On pseudocod9

algoritmul arată astel

întreg a, b, cCiteşte a, b, c$acă a < b at&nci $acă c < a at&nci Scrie c, a, b altel

$acă c < b at&nci Scrie a, c, b ltel Scrie a, b, c S$acă altel $acă c < b at&nci Scrie c, b, a altel $acă c < a at&nci Scrie b, c, a ltel Scrie b, a, c

S$acă S$acăS$acă

# altă modalitate (mai generală) de re!olvare a acestei pro"leme va i descrisă n continuare.

Considerăm trei numere oarecare9 spre e&emplu J5 ?5 l. Avem dreptul de a inversa po!iiile a

două numere alăturate. %orim ca9 n inal9 numerele să ie scrise n ordine crescătoare. 0lată cum

procedăm

• - este mai mare dec6t $9 se inversea!ă cele două numere9 o"in6nd $ - 1

• - este mai mare dec6t l9 se inversea!ă cele două numere $ 1 -

• $ este maimare dec6t l9 o"inem 1 $ -.

2-



Acest e&emplu numeric ne sugerea!ă posi"ilitatea de a re!olva altel pro"lema anterioară

• On locul numerelor considerăm varia"ilele a5 "5 c8• compar6nd pe r6nd a cu "9 " cu c ,i din nou a cu "9 iar dacă este ca!ul intersc8im"ăm

coninutul acestor varia"ile.întreg a, b, c, /;Citeşte a, b, c

$acă a ( b at&nci / a a b b / S$acă$acă b ( c at&nci

/ b b c c / S$acă$acă a ( b at&nci / a

a b b / S$acăScrie a, b, c

;ro"lema 2. e citeşte n număr natural! strict mai mare ca 1. ă se precizeze dacă este prim

sau nu.

Pentru re!olvare9 o primă idee de lucru constă n a considera toi divi!orii posi"ili ai

numărului n. %acă nici unul dintre ace,tia nuDl divide9 nseamnă că numărul este prim. %ar care

sunt ace,ti divi!ori?

• o posi"ilitate ar i să considerămdivi!orii cuprin,i ntre 2 ,i nDl• o a doua posi"ilitate este de a considera divi!orii cuprin,i ntre 2 ,i Humătatea lui n

(n >I& 2)9 soluie mult mai avantaHoasă dec6t prima9 ntruc6t avem mai puinidivi!ori ,i implicit se calculea!ă mai puin

• o a treia posi"ilitate constă n a considera toi divi!orii cuprin,i ntre 2 ,i partentreagă din radical din n (presupun6nd cunoscută teorema care airmă că9 dacă unnumăr nu are nici un astel de divi!or9 el este prim).

ltima variantă este mai "ună. pre e&empliicare9 vom considera numărul 555 n prima

variantă tre"uie veriicai 55- divi!ori9 n a doua $$- iar n a treia numai 25 de divi!ori.

Corespun!ător acestei ultime variante redactăm algoritmulîntreg n, il!gic #ri/;Citeşte n

#ri/ tr&e

Aentr& i 2, n e"ec&tă $acă n /!d i * 0 at&nci #ri/ alse S$acăSAentr&$acă #ri/ at&nci Scrie =n&/ăr&l este #ri/=

ltel Scrie =n&/ăr&l n& este #ri/=S$acă

Algoritmul pre!entat are un neaHuns. ă presupunem că dorim să veriicăm dacă numărul

2



1/// este prim. Primul divi!or posi"il (2) divide acest număr. Cu toate acestea9 n loc să se

ai,e!e re!ultatul imediat9 se veriică ,i ceilali divi!ori posi"ili. :re"uie găsită o modalitate prin

care9 la găsirea unui divi!or9 să se ai,e!e aptul că numărul nu este prim.

întreg n, i;Citeşte n

i 2c@t ti/# i < n şi n /!d i 9 0 e"ec&tă i i)iSC@t ti/#$acă i * n at&nci Scrie =n&/ăr&l este #ri/= ltel Scrie =n&/ăr&l n& este #ri/=S$acă

Acest algoritm are de!avantaHul că9 atunci c6nd numărul este prim9 se ncearcă toi divi!orii

posi"ili cuprin,i ntre 2 ,i nDl. Putei găsi un algoritm care să elimine acest de!avantaH?

;ro"lema . ă se scrie un algoritm care a#işează primele nr numere prime! nr #iind citit de

la tastatură.

e pune pro"lema să asigurăm un ciclu n care să se caute numerele prime printre numerele

29 39 ,.a.m.d.9 p6nă se ai,ea!ă cele nr cerute.

întreg n, i, E, nr, găsitCiteşte nrn 2E 0

:e#etă găsit 1

Aentr& i 2, [ ]n e"ec&tă

$acă n /!d i * 0 at&nci găsit 0 S$acă SAentr& $acă găsit*l t&nci Scrie n E E)i S$acă n n)1

#@nă c@nd E * nr

;ro"lema ?. e citeşte n ! număr natural !1. ă se descompună "n #actori primi.

Algoritmul constă n următoarele

• se cite,te n• se iniiali!ea!ă primul divi!or posi"il (iM2)• secvena următoare se repetă p6nă c6nd nMl

o se iniiali!ea!ă ,m cu / (actor de multiplicitate9 arată puterea la care segăse,te actorul prim)

o

at6t timp c6t i l divide pe n9 se e&ecută următoarele se măre,te cu 1 actorul de multiplicitate se mparte n la i

25



o dacă ,m este dierit de / (a ost găsit divi!or al lui n) se ai,ea!ă i ,i ,mo se adună 1 la i (se incrementea!ă).

ă presupunem că am citit n 12. Algoritmul decurge astel

• se iniiali!ea!ă i cu 2• se iniiali!ea!ă ,m cu /

• ntruc6t 2 divide pe 129 ,m va lua valoarea 19 iar n valoarea *• ntruc6t 2 divide pe *9 ,m va lua valoarea 2 ,i n valoarea 3• 2 nu divide pe trei9 se trece mai departe• ,m este dierit de /9 se ai,ea!ă 2 Rla puterea< 2• se măre,te i cu l• 4• n este 1 ,i algoritmul se nc8eie.

întreg n, i, /;Citeşte ni 2;:e#etă

/ 0; C@t ti/# n /!d i * 0 e"ec&tă / /)1; n n div i SC@t ti/# $acă / 9 0 at&nci Scrie i, =la #&terea F / S$acă i i)1A@nă c@nd n * 1

;ro"lema @. ă se a#işeze toate numerele naturale mai mici sau egale cu 19999 care se pot

descompune "n două moduri di#erite ca sumă de cuburi. &emplu 1J21

12

1*

.OntrDo structură repetitivă de tip ;entru... e'ecut$ se generea!ă9 pe r6nd9 numerele n

∈ ]19 1////^. Presupun6nd că n se descompune n i3JH39 este evident aptul că 39 n /i ≤ . Pentru

a nu găsi o perec8e (i9 H) de două ori (de e&emplu 39' ,i '93)9 391 ni ∈ 9 iar 391 n / ∈ . Saria"ila

nr re ine numărul de perec8i (i9H) găsite.ț

întreg n, nr, /a", i, E, i1, El, i2, E2;Aentr& n 1, 10000 e"ec&tă

/a" 3n

nr 0 Aentr& i 1, /a" e"ec&tă Aentr& E i, /a" e"ec&tă $acă i-i-i)E-E-E * n at&nci $acă nr * 0 at&nci il i El E altel i2 i E2 E S$acă nr nr)1; S$acă SAentr& SAentr& $acă nr * 2 at&nci

3/



Scrie n, il, El, i2, E2 S$acăSAentr&

;ro"lema B. ă se calculeze

{ }

∉

=

=+=−

=

'939291/

'93

211'

)(

2

x

xa

xax xax

x #

real a, ", cite te a, "ș

Selecteaă " dintre G*1? a-"-"+5

G*2? a-")1 G*6, 5? a ltel 0SSelecteaă

;ro"lema J. e citesc $9 de numere. ă se a#i eze cte sunt pare i impareș ș .

întreg n, i, #are, i/#are #are 0i/#are 0

#entr& i 1, 60 e"ec&tă cite te nș

dacă n /!d2 *0 at&nci #are #are )1 altel i/#are i/#are )1 S$acăSAentr&

;ro"lema 0 e cite te un număr "ntreg i se veri#ică dacă este un număr de 2 ci#re i seș ș ș

a#i ează răspunsul ș

întreg / Cite te n;ș

$acă 33nH104 i 3nș IBB44 at&nci

Scrie Jn&/ăr de 2 cireF ltel Scrie Jn&/ăr dierit de 2 cireFS$acă

;ro"lema ă se scrie un algoritm care cite teș n numere "ntregi i a#i ează suma celor ș ș

pozitive

întreg n, i, ", ss 0; i 1Cite te n;ș

C@t ti/# 3iIn4 Cite te ";ș

$acă 3"H04 at&nci s s ) " S$acă

31



i i ) 1SC@t ti/#Scrie s

32

algoritm_pseudocod

Documents

Transcript of algoritm_pseudocod