Scribd
Încărcați
9 vizualizări9 pagini

Algoritmi

Încărcat de

ItzEmi
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PDF sau citiți online pe Scribd
9 vizualizări9 pagini

Algoritmi

Încărcat de

ItzEmi
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PDF sau citiți online pe Scribd
IL, Algoritmi 1. Nofiunea de algoritm. Caracteristi ici. Exemple 2. Etapele rezolvarii unei probleme 3. Obiectele cu care lucreazi algoritmii 4. Reprezentarea algoritmilor 1. Notiunea de algoritm Algoritmul = metoda de solutionare a unui tip de probleme, constand into multime finita, bine definita si ordonata de operatii, Proprietati: 1) Generalitate —algoritmul rezolva o clasa de probleme nu o problema particulara Ex: Nu3+2ciatb 2) Claritate — algoritmul nu contine ambiguitati 3) Finitudine — algoritmul se termina dupa un numar finit de pasi Alte proprietati ‘© Completitudinea — algoritmul tine cont de toate cazurile particulare ale problemei generale. Ex : calculul lui 2 la n, Caz particular : 2 la 0 care trebuie tratat separat, « Eficienta — algoritmul se va executa cu numar minim de pasi, folosind un minim de memorie ‘© Realizabilitatea - sa poata fi codificat intr-un limbaj de programare Observatial. Nu orice problema admite un algoritm de rezolvare. Ex: pot realiza un algoritm pentru determinarea numarului de divizori ai unui numar, dar nu pentru determinarea numarului de multiplii Observatia2. Doi agoritmi sunt echivalenti cand pentru aceleasi date de intrare se obtin aceleasi date de iesire. Ex: Analogie cu “algoritmii” pe care ii executa omul { Observam 3 tipuri de instructiuni: pas [Link] ia pe foe De tip executa pas [Link] o lingurita de ulei in tigaie - Conditionale — -cuvant cheie pas [Link] timp uleiul nu s-a incins asteapta “daca” ~ Repetitive -cuvinte cheie “ cat timp” , “pana cand” aie pas 4,Pune oualele in tig pas [Link] pana cand se rumenese pas [Link] nu tii regim, pune sare TEMAL Dati 2 exemple de algoritmi din viata de zi eu zi pg 28/Ex. 1,2 Manual Note de curs Prof. Isabela Coman 2. Etapele rezolvarii unei probleme Completitudine: Studiu de exz Sa luam spre analiza, rezolvarea ecuatiei de gradul I: ax+b=0; Aceasta problema presupunea aflarea lui x, in funetie de 2 date numerice, a sib. Din enuntul problemei, deducem ca, a sib vor fi datele pe care noi le vom primi iar noi va trebui sa il aflam pe x in funetie de acestea. Spunem ca ceea ce se da, a si b, sunt date de intrare, iar ceea ce se cere, adica x, reprezinta data de iesire. Va trebui sa elaboram o metoda, prin care sa rezolvam in pasi aceasta problema. Un algoritm rapid care ar descrie modul de rezolvare ar fi urmatorul: pas 1 : preluam datele de i pas 2 : calculam pe x ca fiind furnizam rezultatul x Insa acest mod de rezolvare nu se va putea insa aplica pentru orice valori a si b. Putem sa observam, ca, in cazul in care a = 0, algoritmul nostru ar face o operatic nepermisa, anume impartire la 0. Ca urmare, ar trebui sa gandim o solutie care sa ia in considerare si pacest caz particular. Vom distinge 2 astfel de cazuri a) cand a= 0 si b=0,, x va putea fi orice numar si b=" b) cand a= ; in acest caz mu avem nici o solutie pentru x. Tinand cont de aceste doua cazuri particulare, vom putea completa algoritmul, rezultand unul complet care va putea furniza un raspuns pentru orice pereche de valori a,b. pas i: preluam datele de intrare a si b si b=0 furnizam mesaj “ ” pas 2: daca a ‘exista o infinitate de solatii pas 3: daca nu esista nici © solutie” 0 si b <> 0 furnizam mesaj zam rezultatul x Programatorii au cazut de acord in privinta unor reguli de reprezentare a acestor pasi ai algoritmilor, astfel incat acestia sa fie scrisi cat mai schematic, reguli pe care le vom studia la capitolul “reprezentarea algoritmilor”, lata un exemplu de reprezentare a acestui algoritm: Dupa ce am analizat, am definit pasii de rezolvare pentru problema data si am verificat algoritmul rezultat pe un set de date de intrare, putem sa implementam intr-un limbaj de programare algoritmul, Note de curs Prof. Isabela Coman PSEUDOCOD SCHEMA LOGICA Intreg a,b Citeste a, b daca (a=0) atunei scrie “x nu exista’ va serie x Sx "x nu existay *x oricarey Studiu de eaz2: Eficienta (timp mai scurt): Sa luam spre analiza, calculul sumei primelor n valori naturale; Analizam 2 metode de rezolvare : prin formula sau prin adaugarea pe rand a celor n valori, la calculul sumei Eficienta (memorie folosita mai mica): Suma elementelor dintr-o secventa de ne valori. Tata pe scurt etapele de rezolvare a unei probleme: pas 1. Identificarea datelor de intrare/iesire (ce se da si ce se cere?) Ce sunt datele? Ce sunt informatiile? pas 2. Proiectarea algoritmului Cum reprezentam un algoritm pe hartie? Cum identificam cazurile particulare ale unei probleme? pas 3. Testarea algoritmului dupa faza de proiectare. pas 4, Traspunere algoritm intr-un limbaj de programare ‘Cum implementam in calcularor un algoritm? pas [Link] algoritmului dupa implementarea acestuia (depistare erori de sintaxa sau erori logice) Cum verificam algoritmul realizat? Tema 2: Dati 2 exemple de algoritmi in care sa puneti in evidenta proprietatile algoritmului (Completitudine, Eficienta, etc) Note de curs Prof. Isabela Coman 3. Obiecte cu care lucreaza algoritmii 3.1 Date (variabile sau constante) Pot fi date de doua tipuri © Elementare(intregi, reale, logice, caracter) © Structurate (optional citim despre memorarea numerelor naturale si intregi din documentul “Memorarea Datelor”) De asemenea datele pot fi: © Constante = informatii care se autodefinese; date care nu isi modifica valoare: Constante numeric 4; reale: 5.2, 7.8 Constante logice: TRUE, FALSE : intregi: Constante Caracter: ‘e’, “in Constante sir de caractere : “mama are mere”, “Cuvantul \"while\” reprezinta cuvant cheie pentru imbajul ¢“ ‘© Variabile = date care isi modifica valoarea. Pot fi de aceleasi tipuri ca si constantele. Proprietatile variabilelor: nume, tip, locatie de memorie, valoare la un moment dat Obs: Algoritmul urmator va afisa de doua ori valoarea 3 deoarece in locatia de memorie a lui x ramane doar ultima valoare primita, X=2 Xe: Serie x Serie x De adaugat o schema grafica cu proprietatile unei variabile Note de curs Prof. Isabela Coman 3.2 Operatori Operatorii —au rolul de a preciza ce operatii se vor realiza asupra datelor cu care lucram. Operatorii se aplica doar anumitor tipuri de date. De pilda nu putem aduna doua caractere sau nu putem imparti cu rest numerele reale (cele cu virgula).. Tipuri de operatori: 3.2.1 Matematici : boty In plus vom avea doi operator diy ‘catul impartirii a doua numere intregi mod=restul impartirii a doua numere intregi Ex: 243, a div 2, a*2*x; aceste expresii au un rezultat numeric, de aceea se numesc expresii aritmetice 3.2.2 Relational Ex: a.>5) Aceste expresii au ca rezultat 0 valoare logica (adevarat sau fals). De aceea vom spune despre acestea ca sunt expresii logice chiar daca nu contin operatori logici, 3.2.3 Logici: AND/OR/NOT a » aANDb [aORb |NOTa TRUE | TRUE | TRUE TRUE | FALSE TRUE |FALSE |FALSE [TRUE | FALSE FALSE | TRUE | FAL! FALSE [FALSE FALSE | FALSE | TRUE E | TRUE | TRUE Proprietati (Relatiile lui Morgan): 1) NOT (a AND b)=NOTa OR NOTb 2) NOT (a OR b)=NOTa AND NOTb Demonstratie pentru prima relatie: a b aANDb [NOT(aAND b) |NOTa |NOTb | NOTa or NOTb TRUE [TRUE [TRUE | FALSE FALSE | FALSE | FALSE) TRUE | FALSE | FALSE | TRUE FALSE |TRUE | TRUE FALSE | TRUE TRUE TRUE |FALSE | TRUE FALSE | FALSE TRUE TRUE |TRUE | TRUE TEMA in clasa: Demonstrati relatia a doua a lui MORGAN urmand exemplul primei demonstratii. Note de curs Prof. Isabela Coman a Db aORb |NOT@ORb) |NOTa |NOTb | NOTaANDNOTb TRUE [TRUE | TRUE | FALSE FALSE [FALSE | FALSE TRUE | FALSE | TRUE | FALSE, FALSE [TRUE | FALSE FALSE | TRUE | TRUE | FALSE TRUE |FALSE | FALSE FALSE | FALSE | FALSE | TRUE TRUE |TRUE | TRUE 3.3 Expresii Ca si la matematica, 0 expresie este formata din operanzi si operatori. In functie de tipul de date, vor fi aplicati operatori specifici. De pilda, are sens sa aplicam un operator aritmetic asupra unor date numerice. Nu are sens 0 operatie de adunare asupra a doua date caracter. Cum nu are sens de asemenea sa aplicam un operator logic asupra a 2 numere: ce sens ar avea expresia : "2 si3”? Expresiile se pot clasifica si ele in functie de valoarea rezultata in urma evaluarii expresiei. Vom avea: intregi. ex: 2+3; 4*50; 30+a, unde a este o variabila numerica de tip intreg reale. ex: 2.3+4, 2+x, unde x este 0 variabila numerica de tip real 3. expresii logice. Ex: a>b AND 4S2.4 De la stanga la dreapta [Conjuntia logica ( si ) AND De la stanga la dreapta Disjunctia logica(sau) [OR De la stanga la dreapta 1. Culegere rosie : 44,45,31 Note de curs Prof. Isabela Coman 4, Reprezentarea algoritmilor Obs: Algoritmul “oua ochiuri” este un algoritm pe care il va executa un om, Instructiunea “Pune tigaia pe foc” nu ar putea fi executata de catre calculator. De aceea algoritmii pe care ii vom studia la informatica vor contine doar operatii pe care un calculator le-ar putea executa. Aceste operatii pot fi: * Operatii de intrare/iesire ~operatile de citire/seriere © Operatii de atribuire © Operatii decizionale Vom folosi doua modalitati de reprezentare a algoritmilor: 1, PSEUDOCOD = limbaj apropiat limbajului nostra natural, dar care este de asemenea foarte apropiat si de limbajele de programare in care vor fi transpusi algoritmii. 2. SCHEMA LOGICA = Reprezentare grafica. Fiecdrui tip de prelucrare elementar’ (fiecatei operatii) ii corespunde un simbol grafic. Prelueratile suecesive sunt indicate prin conectarea prelucririlor elementare si prin sige Obs. Asa cum un constructor nu se apuca de construit pana ce nu are un plan al constructiei, nici tun programator nu trebuie sa se apuce de implementat algoritmul direct in calculator. El isi va reprezenta mai intai algoritmul pe hartic, concentrandu-se mai intai asupra metodei de rezolvare a problemei, asupra analizei cazurilor particulare si asupra modului de reprezentare Schema | Pseudocod logica Descriere Blocul de inceput/sfarsit - orice schema logica incepe cu un bloc de start si se termina cu blocul de stop Blocul de citire - se citesc de la dispozitivul de intrare valorile variabilelor specificate in lista_variabile ( separate prin virgula ) Citeste lista_variabile Citeste x Citeste x, y Blocul de seriere ( doua variante ) - se Serie lista_expresii scriu la dispozitivul de iesire valorile Serie y obtinute in urma evaluarii expresiilor din lista( separate prin virgula ) Blocul de atribuire - se cevalueaza Variabila¢—expresie expresia; valoarea obtinuta memorata | [X= %X41 | | xex+1 in variabila, vechea valoare pierzandu-se; Blocul de decizie - se evalueaza conditia: daca (conditie) ... daca ¢ adevarata se continua cu prelucrarea indicata de ramura da, altfel cu ramura nu; conditia poate contine operatori relationali, operatori logici KS y 23>] | daca zy +3), Note de curs Prof. Isabela Coman Operatii pe care le efectueaza algoritmii 1) Operatii de intrare iesire *Citire/scriere Operatia de citire este operatia prin care se preiau date de la un dispozitiv de intrare( ex. De la tastatura- de la utilizator) Operatia de scriere este operatia prin care sa preiau date din memoria interna a calculatorului si se transfera catre un dispozitiv de iesire (ex: Catre monitor - catre utilizator) Aplicatial: Se citesc 2 valori intregi a si b de la tastatura, Sa se afiseze produsul acestora pe ecran. Pseudocod € Intreg a,b #include Citest a,b Serie “produsul numererlor este, atb #include int mainO{ int a, b; printf( "Introduceti doua numere: " ); seanf("%d", &a ); seanf("%d", &b )s printf( "Produsul numerelor este %d\n", a * b); return 0; 2) Operatii de atribuire Operatia de atribuire este operatia prin care dam valoarea unei variabile Aplicatia2: sa se interschimbe continutul a doua variabile, Pseudocod Cc Tntreg a,b,aux Citeste a,b Auxa Ab Be aux Serie a,b #include #include int main int a, b, aux; printf( "Introduceti doua numer scant "%d", &a); sani "%d", &b ); aux=a; Note de curs Prof. Isabela Coman UX; printf( "Valorile interschimbate sunt %d %d:\n", a, b ); return 0; } 3) Operatii decizionale Operatia decizionala este operatia prin care caleulatorul poate decide valoarea de adevar a unei expresii logice. In functie de aceasta operatie calculatorul poate executa sau nu alte operatii Ex3: Se citesc 2 numere. Sa se afiseze care este numarul cel mai mare Pseudocod c Intreg a,b,aux #include Citeste a,b #include daca(a

S-ar putea să vă placă și