Transcript
Page 1: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

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.

Page 2: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

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

Page 3: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

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 <= Mai mic sau egal

Page 4: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

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

Page 5: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

5

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

DACĂ condiţie=True ATUNCI acţiune1 ALTFEL acţiune2

structura de decizie (alternativa)

DA

NU

ACŢIUNE2

ACŢIUNE1

Se testează îndeplinirea condiţiei din blocul de decizie. Dacă această condiţie este îndeplinită, se execută ACŢIUNE1. Dacă nu, se execută ACŢIUNE2. La un moment dat, se execută sau ACŢIUNE1, sau ACŢIUNE2.

Condiţie îndeplinită?

S1

S2

S3

Sn

Page 6: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

6

Exemple: 1. Se citesc 2 valori numerice reale, care reprezintă dimensiunile (lungimea şi lăţimea unui

dreptunghi). Să se calculeze şi să se afişeze 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

CITEŞTE L, l

aria <- L * l

AFIŞEAZĂ aria

STOP

ALGORITM aflare_arie_drept INCEPUT

Real L,l, aria CITEŞTE L,l aria <- L*l AFIŞEAZA aria

SFARŞIT

ALGORITM max_2_nr INCEPUT

Real max, a, b CITESTE a, b DACA a >= b

ATUNCI max<-a ALTFEL max<-b

AFISEAZA max SFARŞIT

ALGORITM max_2_nr ÎNCEPUT

Real max, a, b CITEŞTE a, b DACA a >= b ATUNCI AFISEAZA a ALTFEL

Sau:

Se evaluează condiţia de test (figura 1.5.). Dacă aceasta este îndeplinită, se execută ACŢIUNE. Se revine apoi şi se testează iar condiţia. Dacă este îndeplinită, se execută (se repetă) ACŢIUNE, ş.a.m.d. Abia în momentul în care condiţia nu mai este îndeplinită, se trece mai departe la urmatoarea operatie din algoritm. Astfel, cât timp condiţia este îndeplinită, se repetă ACŢIUNE. În cazul în care, la prima testare a condiţiei, aceasta nu este îndeplinită actiunea nu se executa nici macar odata.

Figura 1.5. Structură repetitivă cu test iniţial

DA

NU

ACŢIUNE

Condiţie îndeplinită?

Page 7: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

7

Observatie : actiune2 este de fapt actiunea care urmeaza structurii repetitive motiv pentru care in pseudocod se poate scrie : CÂT TIMP condiţie EXECUTĂ acţiune Exisă şi situaţii în care se ştie de la început de câte ori se va repeta o anumită acţiune. În aceste cazuri se foloseşte tot o structură de control repetitivă cu test iniţial. Se utilizează un contor (numeric) pentru a ţine o evidenţă a numărului de execuţii ale acţiunii. De câte ori se execută acţiunea, contorul este incrementat. In pseudocod :

PENTRU contor=val_ini LA val_finala [PAS p]

EXECUTĂ acţiune;

Structură repetitivă cu test final:

Figura 1.6. Structură repetitivă cu test iniţial, cu număr cunoscut de paşi

Se atribuie contorului valoarea iniţială (figura 1.6.). Cât timp condiţia (valoarea contorului este mai mică sau egală cu valoarea finală) este îndeplinită, se repetă: ACŢIUNE incrementare contor (se adună 1 la

valoarea anterioară a contorului).

contorvaloare_iniţială

valoare_contor valoare_finală

ACŢIUNE

valoare_contor valoare_contor + 1

DA

NU

Se execută mai întâi ACŢIUNE1. Se testează apoi condiţia (figura). Se repetă ACŢIUNE1 pana cand condiţia este îndeplinită. În acest caz, corpul ciclului (ACŢIUNE1) este executat cel puţin o dată.

DA

NU

ACŢIUNE 1

Condiţie îndeplinită?

Structură repetitivă cu test final

Page 8: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

8

In pseudocod :

REPETĂ acţiune PÂNĂ CÂND 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:

Page 9: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

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. Care este lungimea nasului dupa z zile, stiind ca initial nasul are p cm? (Zilele incep cu luni) 8. Ana a ramas singura acasa si vrea sa faca placinte. Pentru aceasta are nevoie de x grame faina, y grame zahar, z ml lapte, p oua, m kg mere. Stiind ca pretul unui kg de faina este px, al unui kg de zahar este py, litrul de lapte costa pz, kilogramul de mere costa pm si ouale sunt pp lei/buc, sa se afle pretul placintei Anei. 9. Sa se calculeze suma 1+2+3+…+n 10. Sa se calculeze suma k+(k+1)+…+ (k+n) 11. Sa se determine ultima cifra a sumei x+y, unde x si y sunt date de la tastatura. 12. Fiind dat un numar de 4 cifre, sa se construiasca inversul acestuia si sa se faca media aritmetica a cifrelor sale. 13. Sa se determine ultimele doua cifre ale produsululi a*b. 14. O persoana are initial la banca o suma de bani S. In primele 6 luni ale anului, dobanda a fost p%, iar in urmatoarele 6 luni a fost q% din suma la care s-a adaugat si dobanda pe lunile anterioare, sa se determine suma pe care o va avea persoana la sfarsitul anului. 15. Sa se calculeze aria si perimetrul unui:

patrat, cunoscand lungimea laturii dreptunghi, cunoscand lungimile celor doua laturi triunghi, cunoscand cele 3 laturi trapez, cunoscand lungimile bazelor si inaltimea cerc, cunoscand raza

Page 10: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

10

Structura alternativa 16. Sa se verifice daca un numar este par sau impar. 17. Scrieti un algoritm care sa determine cel mai mare dintre doua numere intregi citite. 18. Scrieti un algorim care sa determine cel mai mare dintre 3 numere intregi citite. 19. Scrieti un program care citeste de la tastatura trei valori numerice a, b, c si apoi afiseaza pe ecran cea mai mare diferenta dintre oricare doua valori date. Ex. a=100, b=15, c=105. Se va afisa 90. 20. Se da un numar din 3 cifre.Sa se genereze cel mai mare numar care are aceleasi cifre ca el. 21. Intr-un parc se joaca 3 copii care au greutatile a,b,c. Sa se stabileasca daca se pot aseza pe un balansoar astfel incat acesta sa stea in echilibru. 22. Sa se rezolve ecuatia de gradul I cu o necunoscuta: ax+b=0 unde a si b sunt coeficienti reali cititi. Discutie. 23. Sa se rezolve ecuatia de gradul al II-lea cu 2 necunoscute: ax2+bx+c=0 unde a,b,c sunt coeficienti reali cititi. Discutie (solutie unica reala, solutii distincte reale, solutii complexe) 24. Sa se verifice daca 3 numere a,b,c sunt pitagorice patratul unuia poate fi scris ca suma patratelor celorlalte doua) 25. Fie 2 numere cu 4 cifre. Sa se afiseze acela care are suma cifrelor mai mare. 26. Se citesc de la tastatura 3 numere reale. Sa se scrie un algoritm care verifica

daca acestea pot constitui lungimile laturilor unui triunghi. In caz afirmativ se va afisa tipul triunghiului (oarecare, isoscel sau echilateral).

27. Se citesc de la tastatura coordonatele extremitatilor a doua segmente. Sa se afiseze lungimea segmentului mai mare.

28. Sa se verifica daca o fractie a/b se poate simplifica prin k. Sa va afisa DA sau

NU. 29. Sa se determine ultima cifra a lui 7x, x citit de la tastatura. 30. Sa se determine ultima cifra a lui 3x, x citit de la tastatura. 31. Sa se determine daca un numar este sau nu par.

Page 11: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

11

32. Sa se determine ultima cifra a lui 2x, x citit de la tastatura. 33. Se citesc de la tastatura 2 numere naturale a si b si un operator op. Sa se calculeze expresia a op b, unde op poate fi: ‘+’, ‘-‘, ‘/’, ‘%’ 34. Sa se calculeze ultima cifra a lui a*b. 35. Sa se calculeze ultima cifra a lui 1+2+3+…+n

Structura repetitive 36. Sa se determine cel mai mare divizor comun a doua numere naturale a si b citite (prin scaderi repetate). 37. Sa se determine suma cifrelor unui numar natural 38. Sa se determine cate cifre are un numar natural 39. Sa se inverseze un numar natural Ex 4572 devine 2754 40. Sa se determine cifra cea mai mare a unui numar natural 41. Se citeste un numar natural de maxim 9 cifre. Sa se determine de cate ori se gaseste cifra 7 in scrierea lui 42. Un numar natural se numeste perfect daca este egal cu suma divizorilor sai, mai

putin el. Sa se verifice daca un n dat este numar perfect. (Ex : 6=1+2+3, 28=1+2+4+7+14)

43. Sa se numere si afiseze divizorii unui numar 44. Sa se afiseze triunghiul 1 1 2 1 2 3 1 2 3….. ……………… 1 2 3…………n pentru un n citit 45. Se citesc numere pana la 0. Sa se calculeze suma celor negative si produsul celor pozitive. Numarul 0 nu se ia in calcul. 46. Sa se verifice daca un numar natural este prim 47. Sa se afiseze triunghiul * * *

Page 12: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

12

* * * * * *….. ……………… * * *…………* n ‘*’ pentru n citit 48. Sa se descompuna un numar natural in factori ireductibili. Afisarea se va face sub forma factor1^exponent1, factor2^exponent2 etc. 49. Sa se verifice daca doua numere a si b citite de la tastatura sunt gemene (adica sunt prime si diferenta lor in modul este 2).Ex 11 si 13 sunt gemene, 19 si 21 nu sunt gemene. 50. Se citesc numere intregi pana cand se introduce un numar de 2 ori, unul dupa altul. Sa se afiseze cate din numerele citite sunt pare. 51. Sa se aduca la forma ireductibila fractia a/b (a si b nenule, citite de la tastatura) 52. Sa se scrie numarul n, daca este posibil, ca suma de numere naturale consecutive. (Ex. 6=1+2+3, 38=8+9+10+11) 53. Suma, produsul, media aritmetica a primelor n numere naturale citite. 54. Inversarea unui numar. Verificarea daca un numar este palindrom (pb.39) 55. Sa se afiseze si sa se contorizeze toate numerele prime din intervalul [a,b]. 56. Determinarea divizorilor unui numar. Suma divizorilor. 57. Sa se calculeze suma S=1k+2k+3k+………+nk. 58 . Determinarea cmmdc si cmmmc a 2 numere. 59. Se citeste un numar cu n cifre (n<=9). Sa se determine numarul obtinut prin eliminarea cifrei / cifrelor din mijloc. cifrelor sale. 60. Sa se determine daca un numar este patrat perfect 61. Sa se determine daca un numar este cub perfect 62. Serviciul de pază al unei firme are nevoie de un program care să verifice corectitudinea codului de pe cartelele de identificare a angajaţilor. Codul este un număr

Page 13: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

13

întreg de maxim 9 cifre, care conţine cel puţin o cifră pară şi una impară pentru care suma tuturor cifrelor impare şi produsul tuturor cifrelor pare trebuie obligatoriu să producă acelaşi rest la împărţirea cu prima cifră a codului (în ordinea de la stânga la dreapta). Scrieţi un program care să citească de la tastatură un cod şi să afişeze pe ecran mesajul CORECT sau INCORECT, în funcţie de situaţie. Exemplu: pentru n=253271 se va afişa mesajul CORECT 63. Bit-Imparat se afla la mare ananghie : tinutul stapanit de el este de amar de vreme parjolit de ostile lui Rau-Imparat, care e pe cale sa puna stapanire pe tara. Sarmanul Bit-mparat nu are alta solutie decat sa ceara ajutor varului sau, Help-Imparat, pentru ca acesta sa-i trimita grabnic intariri. Bit-Imparat pregateste un sol ce va duce mesajul. Odata ajuns, solul trebuie sa-i sopteasca lui Help-Imparat o parola, care consta dintr-un numar ce poate fi scris ca putere a lui 2. Daca numarul corespunde regulii, mesajul solului va fi interceptat, altfel solul va fi considerat spion si i se va taia capul. Sa se decida daca pentru « o soapta data », solul scapa cu viata sau nu. 64. Sa se calculeze valoarea expresiei a) 1-2+3-4+5- ….. n pentru n natural citit b) 1 +1+2+1+2+3+….1+2+3+…+n c)1+1*2+1*2*3+…..+1*2*3*…*n d) 12-22 +32-42….n2 e) 12*(1+2)3*(1+2+3)2*(1+2+3+4)3……*(1+2+3+…+n)2 sau 3

f) 11...

4332

3221

211

nn

nn pentru n citit

65. Se citeste un intreg n si n perechi (a,b) de numere naturale. Sa se afiseze acele perechi de numere prime intre ele.

66. Se citeste n numar natural. Sa se afiseze indicativul Euler pentru n . (Indicativul

lui Euler al unui numar x este numarul de numere naturale mai mici ca x si prime cu el Ex pt x=9 e= 6 pt ca 1,2,4,5,7,8 sunt prime cu 9)

67. Scrieti un algoritm care verifica daca un numar natural este numar perfect (adica, este egal cu suma divizorilor sai pana la el. Ex: 6=1+2+3)

68. Sa se detrmine suma a doua fractii dc

ba

, a,b,c,d numere naturale nenule citite. Rezultatul va fi exprimat sub forma de fractie ireductibila. 69. Sa se determine termenul al n-lea din sirul 0,1,1,2,3,5,8,13,21… etc. (ex. Pentru n=5 se va afisa 3)

Page 14: Algoritmi - WIKI-INFOPROIECTEwiki-proiecte.wikispaces.com/file/view/algoritmi1.pdf · Structuri repetitive cu test initial (fara contor) Condiţie START CITEŞTE L, l aria

14

70. Se citesc n cifre binare. Se va afisa numarul in baza 10 corespunzator. De ex pt n=4 daca se citesc 1 0 0 1 se va afisa 9. http://infoscience.3x.ro/c++/alg_aplicatii.htm


Top Related