Clasa a IX-a Algoritmi 1

ALGORITMI REPREZENTAI N LIMBAJ PSEUDOCOD

n aplicaii complexe, cnd este necesar modular izarea, schemele logice devin stufoase i sunt greu de urmrit. Din acest motiv, mult mai eficient este reprezentarea algoritmilor pr in limbaj pseudocod. Un limbaj pseudocod este un ansamblu de convenii, respectate n mod sis tematic, care definesc operaiile permise (instruciuni) pentru reprezentarea algor itmilor.

Limbajul pseudocod folosete cuvinte cheie preluate din limbajul natural care descriu instruciuni le din algoritm. (dac, atunci, altfel, ct timp, altfel, execut). Acestea formeaz vocabularul (lexicul) limbajului.

Regulile de folosire a cuvintelor cheie pentru formarea instruciunilor mpeun cu alte cuvinte sau simboluri determin sintaxa limbajului.

1. Structura secvenial

Declararea datelor variabila tip;

La nceputul oricrui algoritm, vom preciza datele de intrare, datele de ieire, datele intermediare, precum i tipul lor. nainte de a utiliza or ice variabil, se va declara, prec iznd numele i tipul ei. O variabil nu poate fi declarat de mai multe ori n acelai algoritm. Exemple: x real; c character; i ntreg; Operaia de citire citete variabila1, variabila2,, variabilan;

Efect: Prin operaia de citire (operaia de intrare) se preiau succesiv valori de la tastatur i se asociaz, n ordine, variabilelor specificate. Operaia de scriere scrie expresie1, expresie2,, expresien;

Efect: Operaia de scriere (operaia de ieire) presupune evaluarea n ordine a expresiilor specifica te i afiarea pe ecran a valorilor lor pe aceeai linie. Operaia de atribuire variabila expresie; Efect: se evalueaz expresia, apoi se atr ibuie valoarea expresiei variabilei din membrul s tng. Parcurgerea instruciunilor n secven, n ordinea lor, reprezint o structur liniar (secvenial). Aplicaii 1. Fie a un numr real, citit de la tastatur, care reprezint lungimea laturii unui cub. S se scrie un algoritm care s calculeze

i s se afieze volumul i aria total a cubului. Date de intrare a real; Date de ieire: V real; A real; nceput citete a; Va*a*a; scrie volumul cubului este: , V; A6*a*a; scrie aria cubului este: , A; sfrit

Clasa a IX-a Algoritmi 2

2. n urma analizelor efectuate, asupra unui compus chimic descoperit pe planeta Marte s-a dedus c o molecul din acest compus este format din mC atomi de carbon, mO atomi de oxigen i mH atomi de hidrogen. tiind masele moleculare petru mC=12, mO=16, iar mH=1, s se scrie un algor itm care calculeaz i s afieze masa molecular a acestui compus. Date de intrare: mC natural mO natural mH natural Date de ieire: m natural nceput citete mC, mO, mH m mC*12+ mO*16+ mH*1 scrie Masa molecular a compusului este: ,m sfrit

3. De ziua lui, Ionel a pr imit S lei i ar vrea s-i invite colegii la o ngheat. tiind c o ngheat cost P lei, s se scrie un

algoritm care s calculeze i s afieze numrul maxim de colegi pe care Ionel i poate invita i suma de bani care i mai rmne lui Ionel. Date de intrare: S natural P natural nr natural Date de ieire: rest natural

nceput citete S,P nr S/(P+1) /*P+1 pt c I Ionel mnnc ngheat*/ rest S%(P+1) scrie numrul maxim de invitai este: ,nr scrie Suma rmas este: , rest sfrit

4. Fie x un numr natural format din 5 cifre(x4x3x2x1x0). S se afieze un tr iunghi format din cifrele numrului x astfel:

- prima linie ( n vf. triunghiului) se va afla cifra din mijloc x2. x2 - Pe linia a doua se vor afla cifrele x3x2x1 x3x2x1 - a treia linie se vor afla toate cifrele lui x x4x3x2x1x0 Date de intrare: x natural Date de ieire: x4,x3,x2,x1,x0 natural nceput citete x x0x%10 /*rein cifra unitilor*/ xx/10 /*elimin cifra unitilor*/ x1x%10 /*rein cifra zecilor*/ xx/10 /*elimin cifra zecilor*/ x2x%10 /*rein cifra sutelor*/

xx/10 /*elimin cifra sutelor*/ x3x%10 /*rein cifra miilor*/ xx/10 /* elimin c ifra miilor, n x rmne cifra zecilor de mii*/ scrie , x2 scrie ,x3,x2, x1 scrie x,x3,x2,x1,x0 sfrit Probleme propuse 1. Ce va afia urmtorul algoritm pentru valor ile citite 7 i 23 :

Date intrare/iesire: a natural,b natural; nceput citete a,b aa+b ba-b aa-b scrie a= ,a, b=,b sfrit

Clasa a IX-a Algoritmi 3

2. Ce va afia urmtorul algoritm dac se citete valoarea: Date de intrare: a natural; Date intermediare: b natural Date de ieire: c natural nceput citete a ba mod 100 aa/100 cb*100+a scrie c

s frit 3. Ce valoare va avea var iabila a la sfritul urmtoarei secvene de instruciuni?

a, b ntregi a3 b7 ba+b/2: aa-b/2*a

4. Fie a, b,c i d patru variabile reale. Care din urmtoarele instruciuni atribuie variabilei d media aritmetic a valor ilor variabilelor a, b i c? a) d(a+b+c)/3 b) da/3+b/3+c/3

c) da+b+c/3 d) d(a+b+c)/3-1

5. Se consider polinomul P(x)=ax3+bx2+cx+d. Se citesc valorile a,b,c,d i x0. S se calculeze valoarea P(x0). 6. Se citete un numr natural cu exact trei cifre. S se afieze suma c ifrelor acestui numr. 7. Fie x1,x2,x3,x4, x5 cinci valori reale. Scriei un algoritm care s foloseasc o singur variabil suplimentar pentru a permuta

circular valorile celor cinci variabile (ex: 1,2,3,4,5 s devin 2,3,4,5,1). 8. Se citete un numr ntreg ce reprezint un numr de ore. S se afieze acest numr n minute, apoi n secunde. 9. S se determine ctul i restul mpririi lui a la b fr a realiza efectiv mprirea. 10. Fie a, b i c trei numere reale, care reprezint lungimile latur ilor unui tr iunghi. S se scrie un algor itm care s calculeze i

s afieze perimetrul i aria triunghiului. 11. O broasc estoas parcurge o distan de D kilometr i n H ore. S se scrie un algoritm care s calculeze i s se afieze

viteza cu care se deplaseaz broasca estoas (exprimat n metri/secund). 12. Doi colegi (Vic tor i Florin) pleac simultan din oraele n care locuiesc, unul ctre cellalt. tiind c dis tana dintre ce le 2

orae este D, c Vic tor merge cu viteza v1, iar Florin merge cu viteza v2 (D,v1,v2 numere reale), scriei algoritmul care calculeaz dup ct timp se ntlnesc cei doi colegi i la ce dis tan de oraul locuiete Vic tor.

13. Fie A i B dou puncte n plan, specificate prin coordonatele lor carteziene. S se scrie un algor itm care s calculeze i s afieze lungimea segmentului AB.

14. A fost odat un balaur cu 6 capete. ntr-o zi Ft-Frumos s-a suprat i i-a tiat un cap. Peste noapte i-au crescut alte 6 capete n loc. Pe acelai gt! A doua zi, Ft-Frumos i-a tiat iar un cap, dar peste noapte balaurul i-au crescut n loc alte 6 capete...i tot aa timp de n zile. n cea de-a (n+1)-a zi, Ft-Frumos s-a plic tis it i a plecat acas scriei un algoritm care citete de la tastatur n, numrul de zile i care afieaz pe ecran cte capete avea balaurul dup n zile. De exemplu: pentru n=3, algoritmul va afia: Dupa 3 zile balaurul are 15 capete.

(Olimpiada 2002 cl a V-a) 15. S se calculeze ma a dou numere a,b reale. 16. Se citesc de la tastatur dou numere naturale nenule. S se calculeze media ar itmetic, media geometric i media

armonic a celor 2 numere.

Clasa a IX-a Algoritmi 4

2. Structura alternativ dac condiie atunci instructiune_1 altfel ins truciunea_2 sf.dac Efect: Se evalueaz expresia. Dac valoarea expresiei este Adevrat, atunci se execut instruciune_1. Dac valoarea expresiei este Fals, se execut instruciune_2. Observaii

1. Att in ramura atunci, ct i in ramura altfel este permis executarea unei singure instruciuni. n cazul n care este necesar efectuarea mai multor operaii, acestea se grupeaz ntr-o singur instruciune compus.

2. Dac pe ramura altfel nu este necesar efectuarea nic i unei operaii, aceasta poate lips i (structura alternativ cu o ramur vid).

Selectarea instruciunii ce urmeaz s fie executat n funcie de valoarea unei expresii reprezint o structur alternativ. Aplicaii

1. Modulul unui numr Se intoduce de la tastatur un numr ntreg x. Scriei un algor itm care calculeaz i afieaz modulul numrului x.

Date de intrare: x ntreg; Date de ieire: rezultatul testului citete x; dac x

Clasa a IX-a Algoritmi 5

Structura alternativ generalizat La cest tip de s tructur se face selectarea ntre mai multe aciuni, n funcie de o var iabil de memorie numit selector, care poate lua mai multe valori, dintr-o mulime ordonat de leemente de acelai tip cu selectorul.

Sintaxa:

n cazul c selector

caz1 v1: instruciune1 caz2 v2: instruciune2 cazn vn: instruciunen altfel instruciune n+1 // (optional) sf.cazuri

Selector este o var iabil sau o expres ie de tip ntreg sau caracter (nu este permis tipul real). caz1,cazn se numesc etichete i sunt valor i pe care la poate lua selectorul. Dac selector=v1 se execut instruciune1. Dac selector=v2 se execut instruciune2 Dac selectorv k(k=1,n) i exis t ramura altfel atunci se execut instruciune n+1; Dac nu exis t ramuar else (altfel) atunci nu se execut nimic i se trece la urmtoarea instruciune de dup case(cazur i).

Probleme propuse 1. Fie ecuaia de gradul al II-lea ax2+bx+c=0 cu a0. Scriei un algor itm care s rezolve ecuaia n mulimea numerelor

reale. 2. Fie a i b dou nr ntregi. Scriei un algor itm care s verifice dac a i b sunt numere consecutive. 3. Stabilii relaia de ordine dintre dou numere reale oarecare , citite de la tastatur . 4. Se citesc trei numere a,b,c. S se tipreasc maximul dintre ele .

S se calculeze valoarea expresiei de mai jos pentru A,B,C numere ntregi date . 5.

E= A+B+C , C

Clasa a IX-a Algoritmi 6

19. Fie ecuaia cu coefic ieni reali ax2+bx+c=0 cu a0. Scriei un algor itm care, fr a calcula rdcinile ecuaiei, s se determine natura i semnul acestora. (relaiile lui Viete x1+x2= S=-b/a, x1*x2=P= a/c).

20. Se citesc dou numere ntregi a, b cu a>b. S se testeze dac cele dou numere se div id. n caz afirmativ s se afieze un mesaj corespunztor, n caz contrar afai ctul i restul mprir ii lui a la b.

21. Fiind date numere ntregi a, b, c, d s se afieze minimul dintre ele. 22. Cunoscnd numrul natural n s se calculeze suma 1+2+3+...+n. 23. Cunoscnd k i n (k7) poate fi pltit numai cu monede de 3 i 5 lei. Dat fiind S>7, scriei un program care s determine o modalitate de plat a sumei S numai cu monede de 3 i 5 lei.

34. Calculai intersecia a dou intervale [a,b] i [b,c] date pr in valori reale a,b,c,d unde a

Clasa a IX-a Algoritmi 7

Structura repetitiv

De multe ori, n construirea algoritm ilor de rezolvarea unor pr tobleme, este necesar repetarea unor operaii atta timp ct condiia este adevrat:

- ct timp este culoarea verde, mai trece o main. - ct timp mai sunt bilete, vindei biletele; sau vindei bilete pn le terminai. - Ct timp mai avei greeli de corectat, corectai greelile. - ct timp mai avei numere, le adunai. - ct timp mai avei cifre ntr-un numar afisai-le. - ncepnd de la 1 scriei n ordine numerele pn la 100.

Metoda de implementare a unei repetiii este structura repetitiv. Structura repetitiv cuprinde: un grup de instruciuni, numite corpul ciclului, ce se execut repetat, i testarea unei condiii care face ca procesul de repetare s continue sau nu. Ex: Se introduce de la tastatur numere pn cnd ultimul numr este 0, i se calculeaz suma numerelor. DI: S iniial 0, i a valoarea citit ce se adaug la sum pn cnd a=0. Spunem pe scurt ct timp a0, adun-l pe a la S. Procesul de control cuprinde trei aciuni: Iniializarea- stabilete s tarea iniial, starea dinainte de prima parcurgere a corpului ciclului. Operaia de atribuire s0, i citirea primului numr (citete a). Testarea- compar starea curent cu s tarea final care face ca procesul de repetare s se s freasc. Se compar numrul a cu 0 (a0) dac condiia este adevrat se continu citirea lui a. Procesul de executare repetat se termin cnd valoarea introdus pentru a este 0. Modificarea- Schimb starea curent astfel nct s se avanseze ctre starea final. Modificarea face parte din corpul ciclului i n exemplul dat const n citirea unei noi valori a lui a (citete a), care poate s fie 0. Structura repetitiv Executarea repetat a unor aciuni, sub un proces de control, este conceput algor itmic printr-o structur repetitiv.

Procesul de control presupune trei aciuni:

Iniializare- Stabilete, s tarea dinainte de prima parcurgere a corpului cic lului. (ex.s0, i1) Testare - compar starea curent cu s tarea care termin procesul de repetare i are rolul de a termina procesul de

ciclare.(i

Clasa a IX-a Algoritmi 8

Observaii: 1. Instruciunea se execut, ct timp valoarea expresiei din condiiei este adevrat. Pentru ca ciclul s nu fie infinit, este

obligatoriu ca instruciunea care se execut s modifice cel puin una din var iabilele care intervin n expresie, astfel nct acesta s poat lua valoarea fals.

2. Dac expresia din condiie are de la nceput valoarea fals, instruciunea nu se execut nic i mcar o dat. 3. Instruciunea din corpul cic lului ct_timp poate s conin o alt instruciune ct_timp. n acest caz se spune c

instruciunile ct_timp sunt imbricate. Probleme propuse

1) S se calculeze suma S=1+2+3=....+n , respectiv produsul P=1*2*3*....*n , pentru numrul n natural nenul dat. 2) S se calculeze media ar itmetic a n valori reale citite pe rnd de la tastatur. 3) Se citesc pe rnd de la tastatur numere ntregi nenule ntr-o variabil x, pn la introducerea valor ii 0. S se

calculeze suma numerelor pozitive introduse i produsul celor negative. 4) Se citesc pe rnd n numere ntregi i apoi o valoare ntreag a. S se determine numrul de apariii ale valor ii a

printre numerele citite. 5) Precizai ce se va afia n urma execuiei secvenei de program de mai jos pentru n=5 (s,n i k sunt variabile ntregi).

Date de intrare: n intreg. Date de iesire:S intreg Citeste n; S0; k1; cat_timp(k

Clasa a IX-a Algoritmi 9

Structura repetitiv cu test final Sintaxa: Schema logic echivalent: repet instructiune corpul c iclului F A pn cnd condiie Efect:

- se execut secvena de instructiuni (orice instruciune pseudocod) care formeaz corpul cic lului, apoi se verific condiia, care este o expresie logic;

- dac condiia este fals, se execut din nou secvena, s.a.m.d.; - corpul cic lului se execut n mod repetat pn cnd condiia devine adevrat (adic ct timp este fals).

Observaii: - este un c iclu cu test final pentru c mai nti se execut secvena i apoi se ver ific condiia; - este un c iclu cu numr necunoscut de pai, numrul minim de execuii asigurat pentru secven este 1 (cnd din

star t condiia este adevrat); - pentru a evita buclarea infinit, corpul c iclului trebuie s conin cel puin o instruciune care s asigure ieirea din

bucl ( la un moment dat condiia s devin adevrat). Probleme propuse Se citete un ir de numere ntregi pn la ntlnirea valorii 0. S se calculeze media ar itmetic a numerelor din ir.

1. Se considera algoritmul urmator: citeste n repeta

cifra n mod 10; scrie c; n n div 10

pana cand n=0 Determinati ce se afiseaza pentru n =1234.

2. Sa se afiseze inversul numarului n. 3. Sa se calculeze cmmdc-ul, respectiv cmmmc-ul a doua numere a, b. 4. Sa se realize algoritmul de determinarea produsului a doua numere a si b prin adunar i repetate. 5. S se calculeze ctul i restul mprir ii a dou numere naturale nenule , a i b date , prin scderi repetate. 6. S se descompun un numr natural nenul dat n factori pr imi , afisnd pentru fiecare factor prim i puterea

corespunztoare 7. Se citesc pe rnd n numere ntregi . S se verifice dac apar sau nu n ordine cresctoare. 8. S se verifice dac un numr natural nenul dat este palindrom , adic citit de la dreapta la stnga i de la s tnga la

dreapta reprez int acelai numr . 9. S se determine numrul de apar iii ale unei valori date, pr intre elementele unui ir dat cu n elemente. 10. Se consider urmtoarea secven: x2; ind0; repeata zx+4; yx+2; n1x^3+x^2+x+1; n23*(y^3+y^2+y+1); n3z^3+3*z^2+2*z+4; daca n1+n2=n3 atunci

ind1; scrie x, ,y, ,z; altfel xx+1; sf.daca

pana cand ind=1

Instructiune

Cond.

Clasa a IX-a Algoritmi 10

12.1. Ce valori se vor afisa dupa executarea secventei de instructiuni descries anter ior: a) 3 5 7 b) 1 6 7 c) 7 3 5 d) 5 3 7 12.2. Ce valori au var iabilele n1,n2, n3 la terminarea executiei secventei? a) 3 5 7 b) 40 468 508 c) 15 288 403 d) 0 0 0 13. Se consider algoritmul urmtor: citeste n repeta cn mod 10 nn div 10 pana cand (n mod 10 >c) or (n=0) daca n=0 atunci scrie ordonat altfel scrie neordonat

Ce rezultat va afisa algoritmul pentru n=1223? a) neordonat b) ordonat c) eroare d) ordonat neordonat

Clasa a IX-a Algoritmi 11

Structura repetitiv cu numr cunoscut de pai Sintaxa:

Schema logic echivalent: pentru i vi , vf , pas execut Sf.pentru corpul ciclului Observaii:

modificare contor - i = variabila contor (de tip ntreg sau caracter); - vi = valoarea iniial de la care ncepe numrarea; - vf = valoarea final la care se oprete numrarea;

- pas = din ct n ct se numr (pasul contorului). vi , v f i pas sunt constante, variabile sau expresii de acelai tip cu v . Dac a) vi 0 - contor cresctor b) vi >= vf i pas

Secvena

vvi

vv+pas

Clasa a IX-a Algoritmi 12

Probleme propuse 1. S se calculeze suma S=1+2+....+n, respectiv produsul P=1*2*...*n pentru n numr natural

nenul citit de la tastatur. 2. S se calculeze media aritmetic a n valori ntregi citite pe rnd de la tastatur, unde n este un

numr natural nenul dat. 3. S se determine i s se afieze divizorii proprii ai unui numr natural nenul n dat de la

tastatur. 4. Se citesc pe rnd n numere ntregi (n natural nenul dat). S se verifice dac numerele apar sau

nu n ordine cresctoare. 5. S se verifice dac un numr natural nenul dat este perfect, adic este egal cu suma divizorilor

si proprii, inclusiv 1. Exemplu, 6=1+2+3 este numr perfect. 6. Se citesc pe rnd n numere reale, n numr natural nenul dat. S se determine numrul valorilor

pozitive, numrul valorilor negative i, respectiv, numrul valorilor nule introduse. 7. Se citesc pe rnd n numere reale. S se determine minimul (maximul) dintre ele. 8. Se citesc pe rnd n numere reale. S se determine media aritmetic a valorilor strict pozitive

citite. 9. Fiind dat un numr n natural nenul s se verifice dac este prim sau nu. 10. S se calculeze:

a) S=1+3+5++nr, unde nr este un numr impar mai mic sau cel mult egal cu n, n numr natural nenul dat

b) P=1*3*5*.*nr, unde nr este un numr impar mai mic sau cel mult egal cu n, n numr natural nenul dat

c) S=1+1/2+1/3+...+1/n, n numr natural nenul dat d) S=1+1*2+1*2*3+.+1*2*..*n, n numr natural nenul dat e) S=1+2

2+3

2+....+n

2, n numr natural nenul dat

f) S=1+1/22+1/3

2+...+1/n

2, n numr natural nenul dat

g) S=1+1/(1*2)+1/(1*2*3)+....+1/(1*2*...*n), n numr natural nenul dat h) R=(1*2*...*n)/(1+2+...+n), n numr natural nenul dat i) P=2*4*6*.....*nr, unde nr este un numr par mai mic sau cel mult egal cu n, n numr

natural nenul dat 11. Se consider irul 1,4,7,10,13,....S se calculeze suma primilor n termeni, n numr natural nenul

dat. 12. S se genereze toate numerele de patru cifre de forma 3a2b care se divid cu numrul 9. 13. Se citesc pe rnd n numere ntregi. S se determine cte numere pare i, respectiv, cte

numere impare au fost citite. 14. Se citesc pe rnd n numere naturale nenule. S se afieze i s se numere acele numere pentru

care suma cifrelor este divizibil cu 5. 15. Se citesc pe rnd n numere naturale mai mari ca 1. S se determine c.m.m.d.c. al celor n

numere. 16. S se afieze numerele prime mai mici dect 100 fcnd un numr ct mai mic de verificri.