1.1. GHID DE LUCRU
Rezolvarea unei probleme cu ajutorul calculatorului presupune parcurgerea următoarelor faze:
‑ precizarea completă a problemei de rezolvat;
‑ proiectarea algoritmului de rezolvare a problemei;
‑ programarea propriu‑zisă (implementarea);
‑ testarea programului obţinut;
‑ exploatarea şi întreţinerea programului.
Aceste faze constituie ciclul de viaţă al programului.
De foarte multe ori, atunci când beneficiarul discută cu executantul despre problema care trebuie rezolvată, acesta dă un enunţ vag, incomplet, dacă nu chiar inexact sau contradictoriu, pentru problema de rezolvat. Urmează mai multe discuţii, uneori întinse în timp, în urma cărora se ajunge la un enunţ relativ complet şi exact al problemei. Întrucât problemele propuse sunt luate din domeniul matematicii sarcina noastră va fi mult mai uşoară.
După enunţarea problemei urmează modelarea matematică şi căutarea unei metode de rezolvare a ei. Uneori sunt posibile mai multe moduri de rezolvare, caz în care se va alege metoda considerată cea mai potrivită scopului urmărit. Modelarea matematică şi alegerea unei metode de rezolvare se îmbină aproape întotdeauna cu conceperea algoritmului, fiind greu să se separe una de cealaltă. Activităţile de mai sus constituie ceea ce numim proiectarea programului.
Pe toată durata proiectării trebuie menţionate în scris toate deciziile luate, întrucât este posibil ca ulterior să fie necesară o reproiectare şi deci, să se revină asupra acestor decizii. Documentaţia realizată este necesară în primul rând pentru următoarea fază a ciclului de viaţă al programului, implementarea. De asemenea, în faza de întreţinere a programului este posibilă modificarea unor module, modificare în care sunt necesare să fie cunoscute şi aceste decizii. E bine ca proiectarea să fie astfel făcută încât să permită o întreţinere cât mai uşoară. Faza următoare, implementarea sau codificarea, constă în traducerea algoritmului într‑un limbaj de programare. Evident, prima decizie ce trebuie luată constă în alegerea limbajului de programare în care va fi scris programul. În cele ce urmează vom folosi în acest scop limbajul Pascal. De multe ori se vor folosi mai multe limbaje pentru această activitate. De exemplu, pot exista unele module a căror scriere se poate face numai în limbajul de asamblare. Urmează testarea programului elaborat, care uneori pune în evidenţă erori grave de programare, erori care au dus în unele situaţii la refacerea (parţială sau integrală) a activităţilor anterioare. Sigur că este de dorit să nu se ajungă la astfel de situaţii şi, dacă proiectarea şi implementarea au fost făcute corect, în faza de testare nu ar trebui să întâlnim erori.
Următoarea fază din viaţa programului constă în exploatarea propriu-zisă a acestuia, fază în care execuţia se face cu date reale. Această activitate se întinde în timp pe mai mulţi ani şi cere adeseori schimbări în program, motiv pentru care este cunoscută sub numele de întreţinerea programului. Este faza cea mai costisitoare şi cea mai importantă din viaţa unui produsul real. Toată activitatea de realizare a programului trebuie să ţină seama de acest fapt şi programul să fie astfel conceput încât să se permită modificări în ceea ce face programul cu un număr minim de modificări în textul acestuia. Documentarea programului presupune elaborarea unor materiale scrise în care se precizează toate informaţiile utile despre programul realizat. Pentru proiectarea algoritmilor vom folosi limbajul Pseudocod. Avantajele folosirii acestui limbaj pentru proiectarea algoritmilor constau în faptul că permit programatorului să-şi îndrepte complet atenţia asupra logicii rezolvării problemei şi să uite de restricţiile impuse de limbajul de programare şi calculatorul folosit. În această fază este necesară o analiză atentă a problemei în vederea găsirii unui algoritm corect proiectat.
De asemenea, proiectarea algoritmului permite evitarea duplicării unui grup de instrucţiuni în mai multe părţi ale programului. Identificarea unui astfel de grup permite definirea lui ca un singur subalgoritm şi folosirea acestui subalgoritm ori de câte ori este necesar.
În descrierea unui algoritm deosebim următoarele activităţi importante:
- specificarea problemei;
- descrierea metodei alese pentru rezolvarea problemei;
- precizarea denumirilor şi semnificaţiilor variabilelor folosite;
- descrierea algoritmului propriu-zis.
Astfel, dacă ni se cere să calculăm radicalul de ordinul 2 din x, în partea de specificare a problemei vom menţiona:
Se dă un număr real nenegativ, notat prin x.
Se cere să găsim un alt număr pozitiv r astfel încât r2=x.
Pentru un informatician este clar că un astfel de număr nu se poate găsi în general prin nici un procedeu finit. Este însă posibil să găsim o aproximare oricât de bună a lui r. Deci specificarea făcută nu este corectă, neputând găsi un algoritm care să rezolve problema în forma enunţată. Vom modifica această specificaţie, cerând să se calculeze aproximativ r cu o eroare ce nu depăşeşte un număr real eps oricât de mic.
Specificaţia problemei este:
DATE eps,x; {eps,xR, eps>0 şi x0}
REZULTATE r; {r-rad(x)<eps}
unde prin rad(x) am notat radicalul de ordinul 2 din x definit în matematică.
Urmează să precizăm metoda de rezolvare a problemei. Se ştie că există cel puţin două posibilităţi de a calcula pe r:
- ca limită a unui şir (definit printr-o relaţie de recurenţă) convergent la r;
- prin rezolvarea ecuaţiei r2=x.
Precizăm că-l vom calcula pe r rezolvând ecuaţia r2=x. Dar şi rezolvarea acestei ecuaţii se poate face prin mai multe metode. Decidem că o vom rezolva prin metoda njumătăţirii. Această metodă constă în njumătăţirea repetată a intervalului [a,b] care conţine rădăcina r la intervalul [a',b'], care este jumătatea stângă, sau jumătatea dreaptă a intervalului [a,b], cea care conţine rădăcina.
Variabilele folosite în descrierea algoritmului sunt:
- a şi b = capetele intervalului în care se află rădăcina;
- m mijlocul intervalului (a,b). În momentul în care b-a<eps,
m va fi chiar valoarea căutată pentru r.
Algoritmul propriu-zis este descris în continuare:
*Iniţializează pe a şi b;
REPETĂ
FIE m:=(a+b)/2;
* Dacă rădăcina se află în [a,m] atunci b:=m altfel a:=m.
PNĂCND b-a<eps SF-REPETĂ
FIE r:=(a+b)/2;
În textul de mai sus apar două propoziţii nestandard care sugerează însă foarte bine ce acţiuni trebuiesc întreprinse. Prima stabileşte intervalul iniţial în care se află rădăcina, care depinde de mărimea lui x: (x,1) când x este mai mic decât 1 sau (1,x) în caz contrar. Deci ea se va transcrie în propoziţia standard
DACĂ x<1 ATUNCI ATRIBUIE a:=x; b:=1
ALTFEL ATRIBUIE a:=1; b:=x
SF-DACĂ
A doua propoziţie înjumătăţeşte intervalul. Condiţia ca rădăcina să se afle în jumătatea stângă a intervalului este (a2-x)*(m2-x)<0. Se ajunge la următoarea variantă finală:
ALGORITMUL RADICAL ESTE: {Calculează radical din x}
DATE eps,x; {eps,xR, eps>0 şi x0}
DACĂ x<1 ATUNCI FIE a:=x; b:=1 {Iniţializează pe a şi b}
ALTFEL FIE a:=1; b:=x
SF-DACĂ
REPETĂ
DACĂ (a2-x)*(m2-x)<0 ATUNCI b:=m {rădăcina în stânga}
ALTFEL a:=m {rădăcina în dreapta}
SF-DACĂ
PNĂCND b-a<eps SF-REPETĂ
FIE r:=(a+b)/2;
REZULTATE r; {r-rad(x)<eps}
SF-ALGORITM
Programul Pascal corespunzător este dat în continuare.
PROGRAM RADICAL; {Programul 1.1. Calculează radical din x}
VAR eps, {eps= precizia cu care se calculează}
x, {radical din x, eps>0 si x>=0}
r, {valoarea radicalului x}
a,b, {capetele intervalului ce conţine pe r}
m : REAL; {mijlocul intervalului [a,b]}
BEGIN
WRITELN(‘Se calculează radical din x cu precizia eps:’);
WRITE(‘eps=’); READLN(eps);
WRITE(‘ x =’); READLN(x);
IF x<1 THEN BEGIN a:=x; b:=1 END {Iniţializează pe a si b}
ELSE BEGIN a:=1; b:=x END;
REPEAT
m:=(a+b)/2;
IF (a*a‑x)*(m*m‑x)<0
THEN b:=m {rădăcina în stânga}
ELSE a:=m; {rădăcina in dreapta}
UNTIL b‑a<eps;
r:=(a+b)/2;
WRITELN; WRITELN;
WRITELN(‘Radical(‘,x:6:1,’) = ‘,r:6:3); {r‑rad(x)<eps}
READLN
END.
1.2. NUMERE PITAGORICE.
Numerele a,b,c, se numesc pitagorice dacă
Specificarea problemei este:
DATE n; {nN; pentru n<12 nu există triplete}
REZULTATE toate tripletele de numere pitagorice (a,b,c) cu proprietatea
0<a<b<c şi a+b+cn.
Vom nota prin S suma a+b+c. Se ştie că (3,4,5) este primul triplet de numere pitagorice. În acest caz S ia valori de la 12 la n. Întrucât 3a<S variabila a ia valori de la 3 la S/3. Apoi 2b<S-a deci b va lua valori de la a+1 la (S-a)/2. Algoritmul pentru rezolvarea problemei este dat în continuare :
Algoritmul NRPITAGORICE este :
Date n; {nN; pentru n<12 nu există triplete}
Dacă n<12
atunci Tipăreşte “Nu există numerele cerute”
altfel Pentru S=12,n execută
Pentru a=3,S/3 execută
Pentru b=a+1,(S-a)/2 execută
Fie c:=S-a-b;
Dacă c=a+b atunci Tipăreşte(a,b,c) Sf-dacă
Sf-pentru
Sf-pentru
Sf-pentru
Sf-dacă
Sf-algoritm.
Programul Pascal corespunzător este dat în continuare.
PROGRAM NRPITAGORICE; {Programul 1.1.2. Numere pitagorice}
VAR n, { nN; a+b+cn }
S, { S = a+b+c }
a,b,c, {(a,b,c) triplet de numere pitagorice}
{ 0 < a < b < c }
k : integer; { contor }
BEGIN
WRITELN(‘Se tipăresc tripletele(a,b,c) de numere pitagorice’);
WRITELN(‘cu proprietatea: a+b+c<=n, pentru n dat’);
WRITE(‘Daţi valoarea lui n:’); READLN(n);
For k:=1 to 4 do writeln;
k:=0;
IF n<12
THEN WRITELN(‘Nu exista numerele cerute’)
ELSE FOR S:=12 TO n DO
FOR a:=3 TO S DIV 3 DO
FOR b:=a+1 TO (S‑a) DIV 2 DO
BEGIN
c:=S‑a‑b;
IF c*c=a*a+b*b THEN BEGIN
k:=k+1;
WRITELN(‘Tripletul (a,b,c)’,k:3,’= ‘,a:3, b:3,c:3);
END {IF}
END;
READLN;
END.
68 de pagini de probleme rezolvate si teorie in Pascal
