Va
avertizam ca, īn practica concreta de programare, programatorul
(care nu este si analist) primeste de la cel care a analizat īnainte
problema doar indicatii de
programare. Rareori analistul pune la dispozitia programatorului
si o descriere īn pseudocod a algoritmilor ce trebuiesc implementati.
Deci, nici un programator īncepator nu trebuie sa-si faca
iluzia ca "generozitatea" din acest capitolo va mai īntīlni vreodata īn practica
concreta de programare sau ca va avea vreodata la
dispozitie surse "abundente" de inspiratie. Este cert
ca īn practica lipsa "inspiratiei" va trebui
compensata prin "transpiratie".
Probleme elementare. Exercitii de programare
Oferim
īn continuare o multime de probleme de programare "clasice"
rezolvate īntr-un mod didactic. Am adaugat īnaintea celor doua
versiuni de solutionare īn cele doua limbaje de programare, Pascal
si C, cīteva rīnduri ce cuprind elementele de baza ale analizei
probleme.
Ne-am
straduit sa asezam problemele īn ordinea
dificultatii lor, de la cele elementare spre cele mai dificile. De
aceea este recomandat ca ele sa fie parcurse īn aceasta ordine.
Atragem
atentia īncepatorilor: una din trasaturile specifice ale
programarii este ca o problema admite mai multe rezolvari
corecte. Desi pot fi diferite īn unele detalii, fiind echivalente prin
rezultatele pe care le ofera, noi le vom numi variante. Asa ca, ceea ce se ofera īn continuare
este doar o varianta de rezolvare pentru fiecare problema, ea fiind
pasibila de īmbunatatiri, atīt pentru versiunea Pascal cīt
si pentru versiunea C. Se zice ca o varianta de program
(algoritm) este mai eficienta
decīt alta daca cantitatea de resurse-calculator
folosita este mai redusa: memorie-calculator (necesarul de
spatiu)mai putina
si timp-calculator (necesarul de timpsau durata de executie) mai mic.
Este
cunoscut ca īn īnvatarea unei limbi straine ajuta mult
exersarea traducerilor dintr-o limba īntr-alta. Evident, pentru realizarea
retroversiunii (termenul de specialitate folosit) este necesara
cunoasterea temeinica a uneia din cele doua limbaje. La fel, īn
cazul programarii, īnvatarea celui de-al doilea limbaj de
programare este mult usurata de faptul ca am asimilat deja
primul limbaj de programare. Īn finalul capitolului vor apare, pentru
exercitiu, mai multe probleme avīnd varianta de rezolvare doar īntr-unul
din limbaje, Pascal sau C, si va propunem sa scrieti
programul corespondent īn celalalt limbaj. Astfel, cei care au
īnvatat deja Pascal vor putea astfel sa īnvete C-ul foarte
rapid , si reciproc.
Sa se afiseze solutiile reale ale
ecuatiei de gradul al doilea.
Analiza problemei- elaborarea
algoritmului:
Fie ecuatia de gradul II ax2+bx+c=0
-daca toti coeficientii ecuatiei sunt
egali cu 0 atunci avem o ecuatie
nedeterminata care are o infinitate de
solutii (S=R).
-daca a,b=0 ,iar c<>0 atunci avem
o ecuatie care nu are solutii.
-daca a=0 ,b,c <>0 atunci ecuatia
se reduce la o ecuatie de gradul I care
are o singura solutie x=-c/b.
-daca a,b,c <>0 atunci trebuie
calculat discriminantul (delta) ecuatieid=b*b-4*a*c
-daca d>=0 atunci ecuatia are solutii reale x1,2=(-b+-sqrt(d))/(2*a)
-daca d<0 atunci ecuatia
nu are solutii reale.
program ecuatie;
var a,b,c,d:real;
BEGIN
write('a=');readln(a);
write('b=');readln(b);
write('c=');readln(c);
if a=0 then
if b=0 then
if c=0 then
writeln('Ecuatie nedeterminata, S=R')
else writeln('Ecuatia nu are solutii.')
else writeln('Ecuatie de gradul I cu solutia
x=',-c/b:6:2)
else
begin
d:=b*b-4*a*c;
ifd>=0 then
begin
writeln('x1=',(-b-sqrt(d))/(2*a):6:2);
writeln('x2=',(-b+sqrt(d))/(2*a):6:2);
end
else writeln('Ecuatia nu are solutii
reale.');
end;
readln;
END.
#include <stdio.h>
#include <math.h>
float a,b,c;//
coeficientii ecuatiei de gradul II
float delta;
void main() else
}
Sa
se determine daca trei numere reale pot reprezenta laturile unui triunghi.
Daca da, sa se calculeze perimetrul si aria sa.
Analizaproblemei - elaborarea algoritmului :
-trebuie sa vedemcīnd trei numere pot fi lungimile laturilor unui triunghi: cele trei
numere trebuie sa fie pozitive sisuma a
oricare doua dintre ele sa fie mai mare decat a treia latura.
-algoritmul poate fi implementat folosind o functie
care sa verifice daca cele trei numere indeplinesc conditiile enumerate
maisus.
-dupa verificarea
celor trei numere calculam perimetrul si aria triunghiului folosind formula lui
Heron s=sqrt(p(p-a)(p-b)(p-c)), unde semiperimetrul este p=(a+b+c)/2.
program arie;
var a,b,c:integer;
s,p:real;
function
laturi_ok:boolean;
begin
laturi_ok:= (a>0) and (b>0) and
(c>0) and(a+b>c) and (a+c>b)
and (b+c>a) ;
end;
BEGIN
write('introduceti
laturile');readln(a,b,c);
P:=(a+b+c)/2;
IF laturi_ok then
begin
s:=sqrt(p*(p-a)*(p-b)*(p-c));
writeln('s=',s:5:2);
writeln('p=',p*2:5:2);
end
else
writeln('laturi negative sau prea mari');
readln;
END.
// solutia in
limbajul C
#include <stdio.h>
#include <math.h>
float a,b,c;
float s,p;
int laturi_ok(void)
void main(void)
else
printf("laturi negative sau prea mari");
}
Sa se afiseze media
aritmetica, geometrica si hiperbolica a trei valori reale.
Analiza problemei - elaborarea
algoritmului:
-trebuie aplicate formulele pentru calculul celor trei
medii si trebuieanalizate cazurile :
Ųcandnu putem calcula media geometrica a trei numere(cand produsul lor este
negativ,deci cand avem unul sau trei numere negative)
Ųcand nu
putem calcula media hiberbolica a numerelor(cand unul dintrenumere este egal cu 0 si nu poate fi facuta
impartirea cu 0).
- in TurboPascal exista o functie pentru calculul
radicalului de ordinul 2 (sqrt),dar pentru calculul radicalului de ordinul n nu
este implementata o functie de aceea pentru calculul radicalului de ordinul n
folosim functia exponentiala ( exp )pentru a calculao puterea a
lui:an =exp(n*ln(a)), iar
pentrua calcularadical de ordinul n din a:a1/n=exp(1/n*ln(a)) .
program medii;
var
a,b,c,ma,mg,mh:real;
BEGIN
write('a=');readln(a);
write('b=');readln(b);
write('c=');readln(c);
writeln('ma=',(a+b+c)/3:6:2);
if (a=0) or (b=0) or (c=0)then writeln('mg=0')
else
if a*b*c>0 then
writeln('mg=',exp(1/3*ln(a*b*c)):6:2)
else writeln('Nu putem calcula media
geometrica ,nr negative .');
if (a=0) or (b=0)
or (c=0) then writeln('Nu putem calcula media hiperbolica')
else
writeln('mh=',3/(1/a+1/b+1/c):6:2);
readln;
END.
// solutia in
limbajul C
#include <stdio.h>
#include <math.h>
float
a,b,c,ma,mg,mh;
void main(void) else
}
Sa se determine suma
primelor n numere naturale.
Analiza problemei - elaborarea
algoritmului:
-suma primelor n numere naturale poatefi calculata, fara a folosi formula
cunoscuta, cu una dintre instructiunile repetitive cunoscute(for,while
,repeat)
-indiferent
de instructiunea repetitiva folosita trebuie initializata suma cu 0 (s=0)
-folosim un
contor i (1,n) care la fiecare pas se incrementeaza cu 1 si se aduna la s
-ciclul se
incheie cand valoarea lui i>n
-daca folosim instructiunea for, numarul
pasilor este cunoscut, valoarea initiala acontorului fiind 1, iar cea finala fiind n.
program suma;
vars,i:word;
BEGIN
writeln('Introduceti
limita n=');readln(n);
s:=0;
for i:=1 to n
dos:=s+i;
writeln('s=',s);
readln;
END.
// solutia in
limbajul C
#include <stdio.h>
unsigned s,i;
void main(void)
Sa se determine
daca n este patrat sau cub perfect.
Analiza problemei - elaborarea
algoritmului:
-pentru a verifica daca un numar este patrat perfect
calculam radacina patrata a numarului
-daca numarul este patrat perfect radacina lui este un
numar intreg altfel este un numar cu zecimale
-verificam daca patratul partii intregii a radacinii
numarului este egal cu numarul dat ,daca da numarul este patrat perfect altfel
numarul nu este patrat perfect
-la fel procedam pentru a verifica daca un numar este
cub perfect .
program patrat_si_cub_perfect;
var n:longint;
BEGIN
write('n=');readln(n);
if
n=trunc(sqrt(n))*trunc(sqrt(n))then
writeln(n,'este patrat perfect')
else
writeln(n,'nu este patrat perfect');
if
n=trunc(exp(1/3*ln(n)))*trunc(exp(1/3*ln(n)))*trunc(exp(1/3*ln(n))) then
writeln(n,'este cub perfect')
else
writeln(n,'nu este cub perfect');
readln;
END.
// solutia in
limbajul C
#include <stdio.h>
#include <math.h>
unsigned long n,m;
void main(void)
Sa se determine toate numerele de 4 cifredivizibile cu n .
Analiza problemei - elaborarea
algoritmului:
-observam ca daca abordam solutia la "prima
mīna" numarul pasilor īn cadrul ciclului for este de 8999,
pentru ca valoarea de intrare in ciclul for este 1000iarvaloarea de iesire este 9999.
-re-analizīnd problema putem stabili un numar foarte
mic de pasi care este egal cu numarul de numere formate din patru cifre
divizibile cu n .
program
nr_divizibile;
var n,i:word;
BEGIN
write('n=');readln(n);
if 1000 mod n =0
then
for i:=(1000 div n) to 9999 div n do
write(i*n,',')
else
for i:=(1000 div n)+1 to 9999 div n do
write(i*n,',');
readln;
END.
// solutia in
limbajul C
#include <stdio.h>
unsigned n,i;
void main(void)
Sa se determine suma cifrelor lui n.
Analiza
problemei - elaborarea algoritmului:
-suma cifrelor
numarului citit se obtine adunīnd de fiecaredata ultimacifra ce este restul
impartirii lui n la 10 (n mod 10)iar
ceea ce ramine eliminind ultima cifra este dat de impartirea lui n la 10 (n div
10).
program
suma_cifre;
var n,s:word;
BEGIN
write('n=');readln(n);
s:=0;
while n<> 0
do
begin
s:=s+n mod 10;
n:=n div 10;
end;
writeln('s=',s);
readln;
END.
// solutia in
limbajul C
#include <stdio.h>
unsigned n,s;
void main(void)
printf("s=%u",s);
}
Sa se afiseze urmatorul triunghi de
numere:
1
1 2
1 2 3
......
1 2 3 ..n
program triunghi;
var i,j,n:word;
BEGIN
write('n=');readln(n);
for i:=1 to n do
begin
for j:=1 to i do
write(j,' ');
writeln;
end;
readln;
END.
// solutia in
limbajul C
#include <stdio.h>
int n,i,j;
void main(void)
}
Se citeste o valoare reala. Sa se
determine radical din x cu 5 zecimale
exacte pe baza sirului convergent xn=1/2(xn-1+x/xn-1),
cu x0>0 arbitrar ales.
Analiza problemei - elaborarea algoritmului:
Pentru rezolvarea
problemei folosim sirul convergent dat (metoda lui Newton) care consta in
etapele:
-pornind cu x0=1 se genereaza
recursiv urmatorul sir de numere reale
xn=1/2(xn-1+x/xn-1)
-cand diferenta
intre xn si xn-1 este foarte mica(mai mica decat o limita
data)procesul de generare a lui xn inceteaza
-la sfarsit xn
reprezinta radacina patrata a lui x.
var x,xn,xn_1:real;
BEGIN
write('Introduceti
valoarea:');readln(x);
xn:=1;
repeat
xn_1:=xn;
xn:=0.5*(xn_1+x/xn_1);
until
abs(xn-xn_1)<1e-5;
writeln('radical
din ',xn:6:2,'=',sqrt(x):10:5);
readln;
END.
// solutia in limbajul
C
#include <stdio.h>
#include <math.h>
float x,xn,xn_1;
void main(void) while
abs(xn-xn_1)<1e-5;
printf('radical
obtinut =%7.5f, comparativ cu %7.5",x,pow(x,0.5));
}
Se citeste n, sa se
determine toate numerele perfecte mai mici decīt n. Un numar este perfect
daca este egal cu suma divizorilor sai (de ex. 6=1+2+3).
Analiza problemei - elaborarea algoritmului:
-pentrua
verifica daca un numar este patrat perfect trebuie sa -i determinamdivizorii si sa verificam daca suma acestora
este egala cu n
- se observa ca ultimul divizor nu trebuie luat in
calculpentru ca este egal cu n
-pentru a afisa toate numerele perfecte < n folosim
un ciclu while in care ildecrementam
pe nsi verificam daca noul n este un
numar perfect ,daca da il afisam
program nr_perfecte;
var n,d,i:word;
BEGIN
write('n=');readln(n);
while n>1 do
begin
dec(n);
d:=0;
fori:=1 to n-1 do
if n mod i=0 thend:=d+i;
if
n=d then writeln(n);
end;
readln;
END.
// o varianta C
#include <conio.h>
#include <stdio.h>
main()
while(sum!=i);
printf("%ld
",i);
}
while(k<n);
}
Se citeste n
un numar īntreg pozitiv, sase afiseze n transcris īn
baza 2.
Analiza problemei - elaborarea
algoritmului:
- folosim
algoritmul cunoscut :
cīt timp n
<>0 executa
- imparte n
la 2
- in urma
impartirii n retine catul si restul
- numarul in baza doi se obtine scriind resturile in
ordinea inversa incare le-amobtinut
- pentru a retine aceste resturi care trebuie
tiparitein ordine inversa am folosit
un sir (n2inv) in care am retinut resturilepe care dupa aceea l-am afisat in ordine inversa.
program
transf_in_baza_2;
var n,n2,i,j:word;
n2inv:array[1..20] of word;
BEGIN
write('n=');readln(n);
i:=1;
while n>0 do
begin
n2:=n mod 2;
n2inv[i]:=n2;
n:=n div 2;
i:=i+1;
end;
for j:=i-1 downto
1 do
write(n2inv[j]);
readln;
END.
// o varianta C putin diferita
#include <stdio.h>
typedef unsigned char pointer[4];
void afiseaza(pointer px,int dim,char* format)
printf(" adica
");printf(format,*px);
}
float y;
long x;
void main(void)
Se citeste n si sirul de valori reale x1,x2,..,xn ordonate
crescator.Sa se determine
distanta maxima īntre doua elemente consecutive din sir.
Analiza problemei - elaborarea
algoritmului :
- este o
problemamaxim
- distanta
dintre primele valori consecutive din sir se noteaza cu max
- dupa care
facem o comparatie cu urmatoarele distante dintre valori
- in momentul
in care se intalneste o valoare mai mare decat max atunci aceasta valoare va
deveni noul max
- algoritmul
se opreste in momentul in care se face comparatia dintre max si distanta dintre
ultimele doua valori ale sirului.
program dist_elem;
var n,i:word;
max:real;
x:array[1..50] of real;
BEGIN
write('n=');readln(n);
for i:=1 to n do
begin
write('x[',i,']=');
readln(x[i]);
end;
max:=x[2]-x[1];
for i:=2 to n-1 do
if x[i+1]-x[i]>max then max:=x[i+1]-x[i];
writeln('max=',max:6:2);
readln;
END.
Se citeste n gradul unui polinom si sirul
coeficientilor an, .. , a0.Se citeste x, sa se determine P(x).
program polinom;
var n,i :integer;
p,x:real;
a:array[0..20] of integer;
BEGIN
write('n=');readln(n);
for i:=0 to n do
begin
write('a[',i,']=');
readln(a[i]);
end;
write('x=');readln(x);
p:=0;
for i:=n downto 0
do
p:=p*x+a[i];
writeln('P(',x,')=',p:6:2);
readln;
END.
Se citeste o
propozitie (sir de caractere) terminata cu punct. Sa se
determine cīte vocale si consoanecontine propozitia.
Analiza programului - elaborarea
algoritmului:
- citim
propozitia caracter cu caracter pana la intalnirea caracterului '.'
- folosim
instructiunea case (selectie multipla) care daca la intalnirea unei vocale din
sir incrementeaza nr de vocale ,iar la intalnirea unei consoane incrementeaza
nr de consoane.
Iata trei programe care
exemplifica modul de lucru cu fisiere īn limbajul C.
// Copierea unui fisier
text sursa intr-un fisier destinatie
#include <stdio.h>
void main(void)
out =
fopen(numfout, "wt");
while (!feof(in))
fclose(in);fclose(out);
printf("Lungimea fis.destinatie este de %ld octeti.",contor);
}
// Copierea unui fisier
text sursa intr-un fisier destinatie
// cu substituirea unor
cuvinte date prin linia de comanda
#include <stdio.h>
void main(int argc,char *argv[])
out =
fopen(numfout, "wt");
while (!feof(in))
else fputc(c,
out);contor++;
}
fclose(in);fclose(out);
printf("Lungimea fis.destinatie este de %d octeti.",contor);
}
// prelucrarea unul
fisier C ce contine o agenda telefonica
#include <stdio.h>
#include <ctype.h>
#include <conio.h>
struct articol
inreg;
FILE *fagenda,*ftemp;
char mod[3]="wb";
void creare(void)
while(toupper(temp)!='N'); // ciclu infinit ? NU!
fclose(fagenda); /*
close file */
}
void listare(void)
void main(void)
Probleme ce necesita back-tracking
Am
explicat pe larg aceasta metoda de programare īntr-un capitol
separat. Īn acest capitol vom oferi doar cīteva exemple de probleme rezolvate.
Majoritatea dintre ele sīnt de maxima dificultate si nu li se
cunoaste o altfel de rezolvare decīt prin aceasta metoda. Din
fericire, aceasta metoda de proiectare a solutiei are un
caracter foarte general si "functioneaza" īn fiecare
caz. Din nefericire, īn practica, atunci cīnd dimensiunea datelor de
intrare este consistenta (avīnd valori cel putin de ordinul
sutelor)programul rezultat devine, prin
durata astronomica de executie, total inutilizabil.
Atragem
atentia ca doar simpla lecturare a acestor exemple de probleme de
back-tracking rezolvate nu permite nicidecum īnsusirea acestei metode de
proiectare a solutiilor. Este necesara mai īntīi implicarea si
participare personala, a celui ce-si propune sa īnvete
aceasta metoda, īncercīnd direct solutionarea lor si abia
apoi comparīnd solutia rezultata cu cea propusa de noi.
Problema clasica de
programare care necesita back-tracking (revenirea pe urma
lasata) este problema iesirii din labirint.
- iata o
solutie simpla care initializeaza labirintul īn mod static,
ca o matrice de caractere
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define XMAX 6
#define YMAX 6
char a[XMAX+1][YMAX+1]=;
int x0=1,y0=2;
void print(void)
getchar();clrscr();
}
void escape(int x,int y)
a[x][y]='*';print();
if(a[x][y+1]=='
')
if(a[x+1][y]=='
')
if(a[x][y-1]=='
')
if(a[x-1][y]=='
')
return;
}
void main(void)
Sa
se genereze toate sirurile de lungime n
formate numai din caracterele a, b
si c a.ī. sa nu existe
doua subsiruri identice alaturate.
- de exemplu, daca n=3
putem avea siruri de forma abc, cab,
bcb, etc. dar nu si siruri de forma aab; pentru n=4 nu putem
genera siruri de forma abab, baac,
etc.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define byte unsigned char
char car[4]=" abc";
unsigned int n,contor;
int Valid(char *s,char c,byte k)
if (ok)
}
return Val;
}
void ConcatSir(char *s,byte k)
} else
}
void main(void)
Sa se afiseze toate
descompunerile unei sume s īntr-un
numar minim de monezi ale unui sistem monetar de n valori.
- de exemplu, īn cazul unui sistem monetar de forma 10, 5, 3, 1 putem descompune suma 18 īn diverse moduri dar solutia
minimala necesita doar 3 monezi: 18=1
x 10+1 x 5+1 x 3 ; descompunerea minimala poate sa nu fie
unica ; sistemul monetar trebuie sa fie astfel ales īncīt sa
permita descompunerea oricarei sume īncepīnd de la o valoare
minimala īn sus (orice sistem monetar contine de obicei moneda
unitara 1)
#include <stdio.h>
int m[10],a[10],a_final[10],s,n,nrmin=32000,kmin;
void
descompune(int s,int k,int contor)
else return;
if(k>n) return;
if(k==n)
else for(i=s/m[k];i>=0;i--)
}
void main(void)
Sa se afiseze toate
descompunerile unui numar s ca
suma de n elemente.
- de exemplu, pentru s=13 si n=3 avem
urmatoarele 14 descompuneri 13= 1+1+11= 1+2+10= 1+3+9=.= 1+6+6= 2+2+9=
2+3+8= 2+4+7= 2+5+6= 3+3+7= 3+4+6= 3+5+5=4+4+5
- desi este
cu totul alta problema decīt cea dinainte, putem observa
asemanarea dintre cele doua solutii (ambele sīnt date īn
varianta recursiva)
#include
<stdio.h>
int
a[10],s,n,contor=0;
void
descompune(int s,int k)
else for(i=1;i<s;i++)
}
void main(void)
Sa se afiseze toate
descompunerile unui numar s ca
suma de n elemente distincte.
- aceasta este o varianta a problemei dinainte;
puteti sesizati unde apare diferenta īn rezolvare ?
#include
<stdio.h>
int
a[10],s,n,contor=0;
void
descompune(int s,int k)
else for(i=a[n-k]+1;i<s;i++)
}
void main(void)
Document Info
Accesari:
22950
Apreciat:
Comenteaza documentul:
Nu esti inregistrat Trebuie sa fii utilizator inregistrat pentru a putea comenta
