3.METODE DE PROIECTARE A ALGORITMILOR
Anii 1960-1970 s-au caracterizat prin:
- apariţia a numeroase limbaje de programare;
- răspândirea în întreaga lume a prelucrării datelor cu ajutorul calculatoarelor;
- creşterea complexităţii problemelor abordate de programatori.
Sfârşitul anilor ’60 a fost marcat de o criză în domeniul programării, manifestată printr-un cost ridicat al elaborării şi întreţinerii programelor, generat de metodele emperice utilizate în realizarea programelor de dimensiuni, adeseori enorme, care nu mai puteau fi înţelese nici de proprii lor autori.
Soluţia ieşirii din această criză a fost furnizată de metoda proiectării şi programării structurate, iniţializată de Dijkstra şi Hoare. Programarea structurată este o metodă, îndeplinită de limbajul de programare, care impune reguli stricte de concepere a algoritmilor de rezolvare a problemelor. Programarea structurată disciplinează realizarea algoritmilor prin restrângerea structurilor de control utilizabile la un număr redus de tipuri.
Un program structurat este format din unităţi funcţionale bine conturate, ierarhizate conform naturii problemei, cu o structură bine precizată, atât la nivelul instrucţiunilor cât şi al datelor, obţinută printr-un proces de rafinare treptată.
Unul din principiile de bază din programarea structurată este programarea descendentă. Aceasta presupune descompunerea problemei complexe în subprobleme mai simple. Descompunerea continuă până la atingerea unui nivel de dificultate acceptabil. Fiecărei subprobleme îi va corespunde câte un modul program cvasindependent de celelalte module. În paralel cu structurarea programului în module se realizează structurarea datelor problemei.
Avantajele programării modulare sunt următoarele:
- structurarea determină o definiţie precisă a funcţiilor fiecărui modul, fapt ce diminuează probabilitatea apariţiei erorilor de logică în rezolvarea problemei;
- scrierea programului şi punerea lui la punc se fac mai simplu şi mai rapid, deoarece modulele se pot realiza simultan, fiecare de diferite persoane;
- modificarea şi extinderea programului se poate face uşor, prin modificarea anumitor module şi adăugarea unora noi;
- fiecare modul se poate scrie în limbajul de programare cel mai avantajos în raport cu funcţia sa.
Celălalt principiu de bază din programarea structurată derivă din teorema de structură a lui Bohm şi Jacopini, care arată că orice algoritm se poate construi folosind doar trei tipuri de structuri de control:
- secvenţială (secvenţa);
- alternativă (decizia);
- repetitivă (ciclul).
Să analizăm metoda proiectării descendente, proiectând algoritmul problemei casierului. Fie dată specificarea problemei în forma standard:
Denumirea problemei
Problema casierului.
Descrierea problemei
Se imită lucrul casierului. De la tastatură se introduce suma cumpărăturii şi suma de bani primită de la cumpărător. Casierul calculează restul, care trebuie să-l returneze cumpărătorului. Restul trebuie să fie format dintr-un număr minim de bancnote.
Întroducerea datelor iniţiale
Se întroduc 2 numere întregi (suma cumpărăturii şi suma plătită), fiecare din rând nou.
Afişarea rezultatelor
Se afişează restul calculat şi numărul de bancnote de fiecare fel care vor fi returnate cumpărătorului
Erori
a) dacă nu au fost întroduse ambele numere, programul va aştepta următoarea întroducere;
b) dacă au fost întroduse mai mult de două numere, atunci celelalte numere se ignorează;
c) dacă în rând au fost întroduse mai multe numere,atunci programul afişează un mesaj de eroare şi se termină.
Exemplu
Suma cumpărăturii? 117
Suma plătită 200
Rest 83
Bancnote 100 0
50 1
20 1
10 1
5 0
1 3
Rezolvare:
Descompunem problema în 3 subprobleme:
1. Întroducerea datelor iniţiale
2. Calcularea rezultatelor
3. Afişarea rezultatelor
Detaliem prima subproblemă.
Avem 2 date iniţiale – suma cumpărăturii şi suma plătită. Cu acest scop vom declara două variabile care vor păstra valorile lor. Fie variabilele
Suma_cump: natutal
Suma_platita: natural
Subproblema se precizează astfel: Întroducerea sumei cumpărăturii şi a sumei plătite.
Detaliem subproblema 2. Problema are 7 rezultate: restul,numărul de bancnote de 100 lei, numărul de bancnote de 50 lei, numărul de bancnote de 20 lei, numărul de bancnote de 10 lei, numărul de bancnote de 5 lei, numărul de bancnote de 1 leu. Deci vom declara 7 variabile, care vor păstra valorile rezultatelor:
Rest: natural
B100: natural
B50 : natural
B50 : natural
B20 : natural
B10 : natural
B5 : natural
B1 : natural
Subproblema 2 se precizează în felul următor: Calcularea restului şi a numărului de bancnote de fiecare fel.
Subproblema 3 se precizează în felul următor: Afişarea restului şi a numărului de bancnote de fiecare fel.
Problema se precizează astfel:
1. Întroducerea sumei cumpărăturii şi a sumei plătite.
2. Calcularea restului şi a numărului de bancnote de fiecare fel.
3. Afişarea restului şi a numărului de bancnote de fiecare fel.
Proiectăm algoritmul rezolvării subproblemei 1.
Subproblema poate fi realizată cu ajutorul mijloacelor de care dispunem (operaţia de atribuire, operaţia te citire,operaţia de afişare). Algoritmul de rezolvare a primei subprobleme este următorul:
WriteString(‘Suma cumpărăturii?’)
ReadNat(Suma_cump)
Writeln
WriteString(‘Suma plătită?’)
ReadNat(Suma_platita)
Writeln
Proiectăm algoritmul de rezolvare a subproblemei 2.
Subproblema 2 poate fi realizată cu ajutorul mijloacelor de care dispunem (operaţia de atribuire şi operaţiile cu date de tip Natural)
Restul se calculează astfel:
Rest:=Suma_platita – Suma_cump
Numărul bancnotelor de 100 lei se calculează astfel:
B100:=rest div 100
Pentru a calcula valoarea variabile B50 trebuie determinat valoarea restului rămas neplătit, fie suma_r: natural.
Valoarea acestei variabile poate fi detrminată astfel:
Suma_r:=rest mod 100
Celelalte rezultate se calculează în felul următor:
B50:=suma_r div 50
Suma_r:=suma_r mod 50
B20:=suma_r div 20
Suma_r:=suma_r mod 20
B10:=suma_r div 10
Suma_r:=suma_r mod 10
B5:=suma_r div 5
B1:=suma_r mod 5
Algoritmul de rezolvare a subproblemei 2 este următorul:
Rest:=Suma_platita – Suma_cum
B100:=rest div 100
Suma_r:=rest mod 100
B50:=suma_r div 50
Suma_r:=suma_r mod 50
B20:=suma_r div 20
Suma_r:=suma_r mod 20
B10:=suma_r div 10
Suma_r:=suma_r mod 10
B5:=suma_r div 5
B1:=suma_r mod 5
Algoritmul de rezolvare a subproblemei 3 este următorul:
WriteString(‘Rest ‘)
WriteNat(rest)
Writeln
WriteString(‘Bancnote de 100 lei ‘)
WriteNat(B100)
Writeln
WriteString(‘Bancnote de 50 lei ‘)
WriteNat(B50)
Writeln
WriteString(‘Bancnote de 20 lei ‘)
WriteNat(B20)
Writeln
WriteString(‘Bancnote de 10 lei ‘)
WriteNat(B10)
Writeln
WriteString(‘Bancnote de 5 lei ‘)
WriteNat(B5)
Writeln
WriteString(‘Bancnote de 1 leu ‘)
Writenat(B1)
Writeln
Acum vom substitui fiecare punct al primei variante de proiectare cu subproblemele detaliate. Obţinem următorul algoritm:
Algoritm Casier
Var
Suma_cump: natural
Suma_platita: natural
Rest: natural
B100: natural
B50 : natural
B50 : natural
B20 : natural
B10 : natural
B5 : natural
B1 : natural
Suma_r: natural
Begin
WriteString(‘Suma cumpărăturii?’)
ReadNat(suma_cump)
Writeln
WriteString(‘Suma plătită?’)
ReadNat(suma_platita)
Writeln
Rest:=Suma_platita – Suma_cum
B100:=rest div 100
Suma_r:=rest mod 100
B50:=suma_r div 50
Suma_r:=suma_r mod 50
B20:=suma_r div 20
Suma_r:=suma_r mod 20
B10:=suma_r div 10
Suma_r:=suma_r mod 10
B5:=suma_r div 5
B1:=suma_r mod 5
WriteString(‘Rest ‘)
WriteNat(rest)
Writeln
WriteString(‘Bancnote de 100 lei ‘)
WriteNat(B100)
Writeln
WriteString(‘Bancnote de 50 lei ‘)
WriteNat(B50)
Writeln
WriteString(‘Bancnote de 20 lei ‘)
WriteNat(B20)
Writeln
WriteString(‘Bancnote de 10 lei ‘)
Writenat(B10)
Writeln
WriteString(‘Bancnote de 5 lei ‘)
Writenat(B5)
Writeln
WriteString(‘Bancnote de 1 leu ‘)
Writenat(B1)
Writeln
End
Niciun comentariu:
Trimiteți un comentariu