QReferate - referate pentru educatia ta.
Cercetarile noastre - sursa ta de inspiratie! Te ajutam gratuit, documente cu imagini si grafice. Fiecare document sau comentariu il poti downloada rapid si il poti folosi pentru temele tale de acasa.



AdministratieAlimentatieArta culturaAsistenta socialaAstronomie
BiologieChimieComunicareConstructiiCosmetica
DesenDiverseDreptEconomieEngleza
FilozofieFizicaFrancezaGeografieGermana
InformaticaIstorieLatinaManagementMarketing
MatematicaMecanicaMedicinaPedagogiePsihologie
RomanaStiinte politiceTransporturiTurism
Esti aici: Qreferat » Documente informatica

Probleme rezolvate si exercitii de programare



Probleme rezolvate si exercitii de programare


Vom incepe prin a face o observatie importanta: exista totdeauna un pericol in oferirea 'pe tava' a solutiilor la probleme. In urmatoarele subcapitolele nu am fost deloc 'zgirciti' si se pot gasi destule probleme rezolvate atit in Pascal cit si in C, desi pentru unele veti putea gasi rezolvarea doar intr-unul din limbaje. Pericolul consta in faptul ca, incepatorilor lenesi, lipsiti de vointa si inclinati catre a copia mereu, li se ofera posibilitatea sa nu-si mai 'bata' capul cu rezolvarea problemelor acum cind au totul 'de-a gata'. Desigur, cei care ies in pierdere sint tot ei. Ne-am asumat acest risc gindindu-ne nu atit la cei lenesi cit mai ales la programatorii incepatori bine-intentionati carora aceste probleme, cu rezolvarile lor tipice, le poate fi de un real folos. Putem spune ca urmat astfel exemplul autorilor mediilor de programare Turbo Pascal si Turbo C (sau Borland) care prin help-urile lor generoase au contribuit decisiv la formarea multor generatii de programatori.



Va avertizam ca, in practica concreta de programare, programatorul (care nu este si analist) primeste de la cel care a analizat inainte problema doar indicatii de programare. Rareori analistul pune la dispozitia programatorului si o descriere in pseudocod a algoritmilor ce trebuiesc implementati. Deci, nici un programator incepator nu trebuie sa-si faca iluzia ca 'generozitatea' din acest capitol o va mai intilni vreodata in practica concreta de programare sau ca va avea vreodata la dispozitie surse 'abundente' de inspiratie. Este cert ca in practica lipsa 'inspiratiei' va trebui compensata prin 'transpiratie'.


Probleme elementare. Exercitii de programare


Oferim in continuare o multime de probleme de programare 'clasice' rezolvate intr-un mod didactic. Am adaugat inaintea celor doua versiuni de solutionare in cele doua limbaje de programare, Pascal si C, citeva rinduri ce cuprind elementele de baza ale analizei probleme.

Ne-am straduit sa asezam problemele in ordinea dificultatii lor, de la cele elementare spre cele mai dificile. De aceea este recomandat ca ele sa fie parcurse in aceasta ordine.

Atragem atentia incepatorilor: una din trasaturile specifice ale programarii este ca o problema admite mai multe rezolvari corecte. Desi pot fi diferite in unele detalii, fiind echivalente prin rezultatele pe care le ofera, noi le vom numi variante. Asa ca, ceea ce se ofera in continuare este doar o varianta de rezolvare pentru fiecare problema, ea fiind pasibila de imbunatatiri, atit pentru versiunea Pascal cit si pentru versiunea C. Se zice ca o varianta de program (algoritm) este mai eficienta decit alta daca cantitatea de resurse-calculator folosita este mai redusa: memorie-calculator (necesarul de spatiu) mai putina si timp-calculator (necesarul de timp sau durata de executie) mai mic.

Este cunoscut ca in invatarea unei limbi straine ajuta mult exersarea traducerilor dintr-o limba intr-alta. Evident, pentru realizarea retroversiunii (termenul de specialitate folosit) este necesara cunoasterea temeinica a uneia din cele doua limbaje. La fel, in cazul programarii, invatarea celui de-al doilea limbaj de programare este mult usurata de faptul ca am asimilat deja primul limbaj de programare. In finalul capitolului vor apare, pentru exercitiu, mai multe probleme avind varianta de rezolvare doar intr-unul din limbaje, Pascal sau C, si va propunem sa scrieti programul corespondent in celalalt limbaj. Astfel, cei care au invatat deja Pascal vor putea astfel sa invete 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) ecuatiei d=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;

if d>=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.


Analiza problemei - elaborarea algoritmului :

-trebuie sa vedem cind trei numere pot fi lungimile laturilor unui triunghi: cele trei numere trebuie sa fie pozitive si suma 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 mai sus.

-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 trebuie analizate cazurile :

cand nu 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 dintre numere 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 calcula o puterea a lui: an =exp(n*ln(a)), iar pentru a calcula radical 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 poate fi 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 a contorului fiind 1, iar cea finala fiind n.



program suma;

var s,i:word;


BEGIN

writeln('Introduceti limita n=');readln(n);

s:=0;

for i:=1 to n do s:=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 cifre divizibile cu n .


Analiza problemei - elaborarea algoritmului:


-observam ca daca abordam solutia la 'prima mina' numarul pasilor in cadrul ciclului for este de 8999, pentru ca valoarea de intrare in ciclul for este 1000 iar valoarea de iesire este 9999.

-re-analizind 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 adunind de fiecare data ultima cifra 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 decit n. Un numar este perfect daca este egal cu suma divizorilor sai (de ex. 6=1+2+3).


Analiza problemei - elaborarea algoritmului:


-pentru a verifica daca un numar este patrat perfect trebuie sa -i determinam divizorii si sa verificam daca suma acestora este egala cu n

- se observa ca ultimul divizor nu trebuie luat in calcul pentru ca este egal cu n

-pentru a afisa toate numerele perfecte < n folosim un ciclu while in care il decrementam pe n si 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;

for i:=1 to n-1 do

if n mod i=0 then d:=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 intreg pozitiv, sa se afiseze n transcris in baza 2.


Analiza problemei - elaborarea algoritmului:

- folosim algoritmul cunoscut :

cit 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 in care le-am obtinut

- pentru a retine aceste resturi care trebuie tiparite in ordine inversa am folosit un sir (n2inv) in care am retinut resturile pe 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 intre doua elemente consecutive din sir.


Analiza problemei - elaborarea algoritmului :

- este o problema maxim

- 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 cite vocale si consoane contine 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.


program nr_consoane_si_vocale;

var c:char;

i,nv,nc:word;

sir:string[25];


BEGIN

write('Introduceti propozitia:');readln(sir);

i:=1; nv:=0; nc:=0;

repeat

case sir[i] of

'a','e','i','o','u': nv:=nv+1;

'b','c','d','f','g','h','j','k','l','m','n','p','r','s','t','x','y','w' :

nc:=nc+1;

end;

i:=i+1;

until sir[i]='.';

writeln('Nr de vocale=',nv);

writeln('Nr de consoane=',nc);

readln;

END.


// varianta C


#include <stdio.h>

#include <ctype.h>


int i,vocale=0,consoane=0;

char c,sir[80];


void main(void)

printf('Vocale:%i, Consoane:%i, Alte car.:%i', vocale, consoane, i-vocale-consoane);


Se citeste m,n dimensiunea unei matrici A=(a[i,j])mxn de valori reale. Sa se determine suma elementelor pe fiecare linie si coloana.


program matrice3;

var m,n,i,j:word;

a:array[1..50,1..50] of real;

sl,sc:array[1..50] of real;


BEGIN

write('Introduceti nr de linii m=');readln(m);

write('Introduceti nr de coloane n=');readln(n);

for i:=1 to m do

begin

for j:=1 to n do

begin

write('a[',i,',',j,']=');

read(a[i,j]);

end;

writeln;

end;


for i:=1 to m do sl[i]:=0;

for j:=1 to n do sc[j]:=0;


for i:=1 to m do

begin

for j:=1 to n do

sl[i]:=sl[i]+a[i,j];

writeln('suma elementelor de pe linia ',i,'=',sl[i]:6:2);

end;


for j:=1 to n do

begin

for i:=1 to m do

sc[j]:=sc[j]+a[i,j];

writeln('suma elementelor de pe coloana ',j,'=',sc[j]:6:2);

end;

readln;

END.


// varianta C


#include <stdio.h>


unsigned m,n,i,j;

float a[50][50];

float sl[50],sc[50];


void main(void)

putchar('n');


for (i=0;i<m;i++) sl[i]=0;

for (j=0;j<n;j++) sc[j]=0;

for (i=0;i<m;i++)

for (j=0;j<n;j++)


Se citeste n si k, si o matrice A=a[i,j]nxn patratica. Sa se determine Ak.


Analiza problemei - elaborarea algoritmului:

-algoritmul consta de fapt in calcularea elementelor matricii produs

-elementul c[i,j] =suma(k=1..n) a[i,k]*b[i,k] .

-Ak=A*A*..*A

-matricea fiind patratica atunci cand k=2 termenii b[i,k]=a[i,k],iar cand k>2 termenii b[i,k] pastreaza elementele produsului anterior A*A, folosim pentru aceasta atribuire procedura aribuire.


program matrice1;

type matrice= array[1..3,1..3] of real;

var a,b,p: matrice;

n,i,j,k,l:word;


procedure atribuire(a:matrice);

begin

for i:=1 to n do

for j:=1 to n do

b[i,j]:=a[i,j];

end;


procedure inmultire ;

begin

for i:=1 to n do

for j:=1 to n do

p[i,j]:=0;

for i:=1 to n do

for j:=1 to n do

for l:=1 to n do

p[i,j]:=p[i,j]+a[i,l]*b[l,j];

end;


BEGIN

write('Introduceti puterea lui A ,k=');readln(k);

write('Introduceti dimensiunea matricii n=');readln(n);

for i:=1 to n do

begin

for j:=1 to n do

begin

write('a[',i,',',j,']=');

readln(a[i,j]);

end;

writeln;

end;


if k=1 then

for i:=1 to n do

for j:=1 to n do

p[i,j]:=a[i,j]

else

if k=2 then

begin

atribuire(a);

inmultire;

end

else

begin

atribuire(a);

inmultire;

k:=k-1;

while k>1 do

begin

atribuire(p);

inmultire;

k:=k-1;

end;

end ;



for i:=1 to n do

begin

for j:=1 to n do

write('p[',i,',',j,']=',p[i,j]:6:2,' ');

readln;

end;

readln;

END.



Iata un program Pascal care gestioneaza cu ajutorul unui fisier un catalog de note si persoane.


Type Persoana=Record Nume:String[20];Nota:Array[1..4]of integer; End;

Var f:File of Persoana;

Perstemp:Persoana;

Procedure Creare;

Begin

Writeln('Introd.');

Assign(f,'Test.jo');

Rewrite(f);

Repeat

With PersTemp do begin

Write('Numele:');Readln(Nume);

If Nume='' then break;

Write('Notele:');Readln(Nota[1],Nota[2],Nota[3],Nota[4]);

end;

Write(f,PersTemp);

Until False;

Close(f);

End;

Procedure Citire;

Begin

Writeln('Introd.');

Assign(f,'Test.jo');

Reset(f);

Repeat

Read(f,PersTemp);

With PersTemp do begin

Writeln('Numele:',Nume);

Writeln('Notele:',Nota[1],Nota[2],Nota[3],Nota[4]);

end;

Until Eof(f);

Close(f);

End;

BEGIN

Creare;

Citire;

END.



Iata trei programe care exemplifica modul de lucru cu fisiere in 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 intr-un capitol separat. In acest capitol vom oferi doar citeva exemple de probleme rezolvate. Majoritatea dintre ele sint de maxima dificultate si nu li se cunoaste o altfel de rezolvare decit prin aceasta metoda. Din fericire, aceasta metoda de proiectare a solutiei are un caracter foarte general si 'functioneaza' in fiecare caz. Din nefericire, in practica, atunci cind dimensiunea datelor de intrare este consistenta (avind 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 insusirea acestei metode de proiectare a solutiilor. Este necesara mai intii implicarea si participare personala, a celui ce-si propune sa invete aceasta metoda, incercind direct solutionarea lor si abia apoi comparind 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 in 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.i. 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 intr-un numar minim de monezi ale unui sistem monetar de n valori.


- de exemplu, in cazul unui sistem monetar de forma 10, 5, 3, 1 putem descompune suma 18 in 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 incit sa permita descompunerea oricarei sume incepind de la o valoare minimala in 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 decit cea dinainte, putem observa asemanarea dintre cele doua solutii (ambele sint date in 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 in 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)



Probleme cu solutie surprinzatoare


In rezolvarea fiecareia din problemele urmatoare este foarte usor de cazut in capcana solutionarii de genul 'la prima mina' sau brute-force-approach in limba engleza (abordare in forta bruta). Este cea mai des intilnita capcana pentru programatorii lipsiti de subtilitate, experienta sau cultura de specialitate. Este si aceasta o rezolvare, desigur, dar lipsa ei de eficienta si de eleganta este evidenta. Tocmai de aceea, consideram foarte utila prezentarea citorva exemple elocvente, impreuna cu solutiile lor. Unele dintre probleme au fost selectionate dintre problemele date la concursurile si olimpiadele scolare de programare .

Prin acest capitol nu urmarim doar insusirea unor cunostinte practice de programare ci, mai ales, aprofundarea capacitatii de analiza si proiectare a solutiilor. Aceasta presupune un salt calitativ in invatarea programarii si de aceea acest capitol devine cu adevarat util numai pentru acei programatori inteligenti si dornici de auto-perfectionare. Sau pentru cei care se pregatesc pentru participarea la concursurile si olimpiadele de informatica.

Solutiile oferite de noi sint, pentru fiecare problema, eficiente si 'elegante'. Acest fapt se datoreaza accentului pus pe aprofundarea si imbunatatirea primei analize a problemei.

Putem atunci spune, ca motto-ul acestui capitol este: 'Nu te multumi niciodata cu solutia la prima mina !'.



Sa se afiseze numarul cuburilor perfecte mai mici decit n.


Analiza problemei - elaborarea algoritmului:


Capcana problemei consta in tentativa de a parcurge printr-un ciclu for toate numerele de la 1 la n si de a contoriza cele care sint cuburi perfecte.

La o a noua privire, mai atenta, observam ca partea intreaga a radicalului de ordinul 3 din n ne ofera acel numar care ridicat la a 3-a este cel mai apropiat cub de n. Deci, partea intreagp a radicalului de ordinul 3 din n este egala chiar cu numarul cuburilor mai mici decit n.

(Este suficient sa calculam radical de ordinul 3 din n pentru a afla cite cuburi mai mici decit n exista.)


program cuburi_perfecte;

var n,i,nr_cub:word;

BEGIN

write('n=');readln(n);

nr_cub:=trunc(exp(1/3*ln(n)));

writeln('numarul cuburilor perfecte < ',n,' este = ', nr_cub);

readln;

END.


Se citesc m, n numaratorul si numitorul unei fractii. Sa se simplifice aceasta fractie.


Analiza problemei - elaborarea algoritmului:

Capcana consta in a efectua simplificarea pas cu pas, cautind pe rind fiecare divizor comun al numaratorului si numitorului. In plus, ar trebui sa avem grija ca, pentru unii divizori comuni, este nevoie de o simplificare repetata. Deci, doua cicluri imbricate !

-pentru a obtine o fractie ireductibila este suficient sa o simplificam o singura data cu cmmdc al numitorului si al numaratorului,eliminindu-se astfel simplificarile succesive

-vom folosi subalgoritmul (Euclid) care calculeaza cmmdc al numaratorului si al numitorului.


program simplificare;

var m,n:word;


function cmmdc(m,n:word):word;

begin

while m<>n do

if m>n then m:=m-n

else n:=n-m;

cmmdc:=m;

end;


BEGIN

write('numaratorul fractiei m= ');readln(m);

write('numitorul fractiei n= ');readln(n);

if n=0 then writeln('Fractie inexistenta.')

else

if m=0 then writeln(m,'/',n,'=',0)

else

writeln(m,'/',n,' = ',m div cmmdc(m,n),'/',n div cmmdc(m,n));

readln;

END.



Se citesc a, b, c intregi. Sa se determine toate perechile intregi (x,y) solutii ale ecuatiei ax+by=c.


Analiza problemei - elaborarea algoritmului;


Problema a fost data la olimpiada scolara de informatica. Ea pare la prima vedere imposibila. Exista ecuatii, de exemplu: 3x+2y=1 care are o infinitate de solutii . , (1,-1), (3,-4), (5,-7), (7,-10), . Cum ar putea fi afisata atunci pe ecran o multime infinita de perechi ? Solutia este de a afisa aceasta multime printr-o descriere sintetica a ei (afisind formula care poate genera toate perechile ce o compun).

1. daca c=1 atunci exista (x0,y0) a.i. ax0+by0=1 doar daca [a,b]=1 ; restul solutiilor (x,y) au forma x=x0+kb , y=y0-ka, cu k intreg.

2. daca c>1 atunci exista solutiile (x0,y0) doar daca [a,b]|c; restul solutiilor se construiesc la fel;

prin [a,b] se intelege cmmdc(a,b)

Programul trebuie doar sa determine x0 si y0.


Program ax_plus_by_egal_c;

Var a,b,c,x0,y0,y:integer;

BEGIN

Write('a,b,c=');Readln(a,b,c);

x0:=0;

For y:=0 to a do

If abs(c-b*y) mod a=0 then begin

y0:=y;x0:=(c-b*y) div a;break;

end;

If x0<>0 then Writeln('Sol. (x,y) ale ec. ',a,'x+',b,'y=',c,' sint (',x0,'+k*',b,',',y0,'-k*',a,')')

else Writeln('Nu exista solutii pentru ecuatia ',a,'x+',b,'y=',c);

END.


/*Varianta C de solutionare:

1. daca c=1 atunci exista (x0,y0) a.i. ax0+by0=1 doar daca cmmdc[a,b]=1 ;

restul solutiilor (x,y) au forma x=x0+kb y=y0-ka, cu k intreg.

2. daca c>1 atunci exista solutiile (x0,y0) doar daca cmmdc[a,b] | c;

restul solutiilor se construiesc la fel.

3. exista posibilitatea ca, pornind de la perechi (x0,y0) distincte, sa se

obtina solutii noi diferite (multimi infinite de perechi distincte).

4. toate solutiile (multimi infinite de perechi) pleaca de la o pereche

(x0,y0) aflata in dreptunghiul (-b,-a)x(b,a).

Un bun exemplu este ecuatia 18x+42y=6.*/


#include <stdio.h>

#include <math.h>


int a,b,c,x0=0,y0=0,y,k;


void main(void)

}

if(!x0 && !y0 && c)printf('Nu exista solutii pentru ecuatia %ix+%iy=%i',a,b,c);


Se citeste n o valoare intreaga pozitiva. Sa se determine toate descompunerile in diferenta de patrate ale lui n.


Analiza problemei - elaborarea algoritmului:

Aratam in continuare cum se poate evita solutia 'banala'-capcana ce-ar consta in doua cicluri for imbricate. Solutia urmatoare efectueaza doar radical din n pasi, fata de n2 pasi ai solutiei 'la prima mina'.

-pentru a determina toate descompunerile in diferenta de patrate ale lui n pornim de la formula a2-b2=(a+b)(a-b)=n

-observam ca produsul termenilor a+b si a-b este produsul a doi dintre divizorii lui n,unul din termeni este divizor (d) a lui n celalalt este tot divizor a lui n si il aflam impartindu-l pe n la d (n div x)

-notam cu x primul divizor a lui n (x=d) si cu y=n div x si obtinem relatiile

a+b=x deci un sistem de doua ecuatii cu doua necunoscute ,pe care il rezolvam

a-b=y prin metoda reducerii ,si avem 2a=x+y => a=(x+y )/2 , b=(y-x)/2,

-pentru ca (x+y)/2 sa fie o solutie a ecuatiei a2-b2=(a+b)(a-b)=n trebuie ca x+y sa fie un numar par si y-x sa fie un numar par

-daca aceasta conditie este indeplinita afisam solutia care indeplineste conditia ceruta.


Program descompunere_patrate;

var n,d,a,b,x,y:integer;

BEGIN

write('n=');readln(n);

for d:=1 to trunc(sqrt(n)) do

if n mod d =0 then

begin

x:=d;

y:=n div x;

if (x+y) mod 2 =0 then

begin

a:=(x+y) div 2;

b:=(y-x) div 2;

writeln(n,'=',a*a,'-',b*b);

end;

end;

readln;

END.


Se citeste n si x1, x2, . , xn radacinile intregi ale unui polinom de gradul n. Se cere sa se determine pe baza relatiilor lui Viete coeficientii an, an-1, . , a1, a0.


Analiza problemei - elaborarea algoritmului;


Cea mai des intilnita rezolvare este cea de tip back-tracking, aparent mai usoara, dar in fapt extrem de ineficienta pentru n nu mare ci doar maricel ! Urmatoarea solutie de tip iterativ este o mica 'bijuterie' de program iterativ si de aceea va lasam placerea de a-l intelege singuri.


#include <stdio.h>


void main(void)

a[0]=1;a[n]=0;

for(k=1;k<=n;k++)

for(i=n;i>=0;i--) printf('a[%d]=%d ',i,a[i]);


Se citeste n. Sa se afiseze toate numerele de n cifre, formate numai cu cifrele 1 si 2, divizibile cu 2n.


Analiza problemei - elaborarea algoritmului:

Problema a fost data la olimpiada scolara de informatica. Abordarea 'in forta' a acestei probleme nu duce la nici un rezultat:

daca s-ar alege varianta de rezolvare 'la prima mina' ar trebui verificate toate cele 2n posibilitati, adica toate cele 2n numere de n cifre ce se pot forma numai cu cifrele 1 si 2 (cite 2 posibilitati pentru fiecare pozitie). In acest caz, programul avind o complexitate exponentiala, ar dura un timp exponential, pt. n=50 ar dura cit virsta sistemului nostru solar !

pt.n=1 avem unica solutie numarul 2;

pt. n=2 avem deasemenea unica solutie 12; observam ca 2-ul este 'folosit'

pt. n=3 avem deasemenea unica solutie 112; observam ca 12 este din nou 'folosit'

In general, se deduce ca numerele de n cifre, ce trebuie sa se divida cu 2n , se divid cu 2n-1; ele se pot scrie sub forma c*10(n-1)+M=c*2n-1*5n-1+M= Multiplu(2n-1)+M; inseamna ca M (cele n-1 cifre ramase) trebuie sa se divida cu 2n-1; inseamna ca M este unul din numerele gasite ca solutie la pasul n-1.

Daca exista o singura solutie M pt.cazul n-1 (M se divide cu 2n-1) acest nr.se poate scrie M=2(n-1)*par sau 2(n-1)*impar, rezulta ca M mod 2n=0 sau M mod 2n=2(n-1). Deci,in cazul a n cifre din cele doua posibilitati (1M sau 2M) se va alege astfel unica solutie:

daca M mod 2n=0 atunci solutia este 2M=2*10(n-1)+M=Multiplu(2n)

daca M mod 2n=2(n-1) atunci solutia este 1M=10(n-1)+M=2(n-1)*5(n1)+M=Multiplu(2n)!

Solutia propusa este una iterativa si face maximum n pasi !


Program 1_2_si_2_la_n;

Var

nr,zece_la_n:longint;

n,i:byte;

BEGIN

Writeln('Se citeste n. Sa se afiseze toate numerele de n cifre,');

Writeln('formate numai cu cifrele 1 si 2, si divizibile cu 2^n.');

Write('Introduceti n (max.10):');Readln(n);

nr:=2;zece_la_n:=1;

For i:=2 to n do begin

zece_la_n:=10*zece_la_n;

If nr mod (1 shl i)=0 then nr:=2*zece_la_n+nr

else nr:=zece_la_n+nr;

end;

Writeln('Solutia este:',nr);

readln;

END.



Se citeste n. Sa se determine o alegere a semnelor + si - astfel incit sa avem relatia n=0.


Analiza problemei - elaborarea algoritmului:

Problema a fost data la olimpiada scolara de informatica. Daca se incearca o abordare 'in forta' si 'la prima mina' vor trebui verificate 2n posibilitati de asezare a semnelor + si -. Adica se obtine un algoritm exponential, total ineficient. Solutia 'eleganta' ce rezulta printr-o analiza mai aprofundata:

-mai intai se va imparti suma in doua parti: cea cu plus si cea cu minus.

Privindu-se atent se observa ca se pot deosebi trei cazuri:

1. cind avem intre cele n numere un numar impar de numere impare (de ex.n=3,5,6) caz in care numerele impare nu pot fi repartizate in cele doua parti (plus si minus) decit astfel: un nr.par de numere impare intr-o parte si un nr.impar de nr impare in cealalta; implica ca cele doua parti au paritati diferite, deci suma lor nu poate fi 0 !

Acest caz apare cind n=4k+1, 4k+2.

2. cind n=4k atunci numerele de la 1 la n pot fi grupate cite patru astfel:

1-2-3+4, , (4i+1)-(4i+2)-(4i+3)+(4i+4), si vor avea suma 0 pe fiecare grupa de patru !

3. altfel, n=4k+3, putem grupa numerele asemanator ca la cazul dinainte cu exceptia primei grupe: -1-2+3, 4-5-6+7, , (4i)-(4i+1)-(4i+2)+(4i+3),reazultind din nou suma 0 pe fiecare grupa !


Program Plus_Minus;

Var

n,i,c:byte;

BEGIN

Writeln('Se citeste n. Sa se determine o alegere a semnelor + si - ');

Writeln('astfel incit sa avem relatia n=0.');

Write('n:');Readln(n);

c:=n mod 4;

case c of

1,2: Writeln('Nu exista solutie.');

0: For i:=1 to n div 4 do

write('+',4*(i-1)+1,'-',4*(i-1)+2,'-',4*(i-1)+3,'+',4*(i-1)+4);

3:begin

Write('-1-2+3');

For i:=1 to n div 4 do

write('+',4*i,'-',4*i+1,'-',4*i+2,'+',4*i+3);

end;

end;

Readln;

END.



Elemente de programare a PC - urilor


Oferim in continuare citeva exemple de programe, unele in Pascal, altele in C, pentru a permite celor pasionati sa-si insuseasca cunostintele minimale de programare a PC-urilor: lucrul cu tastatura, accesul direct la memorie, lucrul in modul grafic, etc. Pentru cei ce doresc sa aprofundeze acest subiect sau doresc cit mai multe detalii le recomandam, pe linga citirea atenta a help-ului Turbo Pascal-ului sau a Turbo C-ului, folosirea utilitarului TechHelp specializat in descrierea programarii PC-urilor.

Ideea care ar defini cel mai bine acest tip de cunostinte de programare este continuta in cunoscuta expresie : 'Secrete mici, efecte mari !'.


// Un simplu program muzical


#include <stdio.h>

#include <dos.h>

#include <conio.h>

main();

int i,j,nr_octava,i_nota,timp=500;

float masura,durata,durata_masura;

char *linia='42$2R2R4M4F2O2L1R2R2S2S4L4O2O2'; //$4D2D4$3S4L2';


do

break;

case 'D' : i_nota=0;break;

case 'd' : i_nota=1;break;

case 'R' : i_nota=2;break;

case 'r' : i_nota=3;break;

case 'M' : i_nota=4;break;

case 'F' : i_nota=5;break;

case 'f' : i_nota=6;break;

case 'O' : i_nota=7;break;

case 'o' : i_nota=8;break;

case 'L' : i_nota=9;break;

case 'l' : i_nota=10;break;

case 'S' : i_nota=11;break;

}

} else

sound(nr_octava*octava[i_nota]);

delay(durata*timp);

} /* else */

} /* for */

/* do */

while (!kbhit());

nosound();


Program Citite_Taste;

uses crt;

var c:char;

shift:byte absolute $40:$17;

begin

repeat

c:=readkey;

if (shift and $3>0) then

write(' shift ',c,':',Ord(c))

else write(' ',c,':',Ord(c));

until c=#27;

end.



// Program C pt. afisarea Tabelului codurilor ASCII;


#include <stdio.h>


void main();


Program Tenis;


Uses Crt;

Const viteza=1500;

Type Ecran=Record

car:char;

atrib:byte;

End;

Var

scr:array[1..25,1..80] of Ecran absolute $b800:$0;

x,y,x0,y0:byte;

i,d,s:integer;

u:real;

ok:boolean;

tasta:char;

yP1:array[1..5]of byte;

yP2:array[1..5]of byte;

uP:array[1..5]of real;


Procedure Paleta1(tip:char);

Begin 

for i:=1 to 5 do

scr[yP1[i],76].car:=tip;

end;

Procedure Paleta2(tip:char);

Begin 

for i:=1 to 5 do

scr[yP2[i],5].car:=tip;

End;

Procedure Mutapaleta1;

Begin

Paleta1(' ');

if (tasta=#80) and (yP1[i]<24) then

for i:=1 to 5 do Inc(yP1[i]);

if (tasta=#72) and (yP1[i]>6) then

for i:=1 to 5 do Dec(yP1[i]);

End;

Procedure Mutapaleta2;

Begin

Paleta2(' ');

if (tasta=#122) and (yP2[i]<24) then

for i:=1 to 5 do Inc(yP2[i]);

if (tasta=#119) and (yP2[i]>6) then

for i:=1 to 5 do Dec(yP2[i]);

End;

procedure cantec;

begin sound(400);delay(800);

sound(500);delay(800);

sound(600);delay(800);

sound(650);delay(800);

sound(600);delay(800);

sound(700);delay(800);

sound(650);delay(1000);

end;

Begin

Clrscr;

d:=0;s:=0;


clrscr;

For x:=1 to 80 do begin

scr[1,x].car :=#219;

scr[25,x].car:=#219;

end;

For y:=2 to 9 do begin

scr[y,1].car :=#219;

scr[y,80].car:=#219;

end;

For y:=17 to 24 do begin

scr[y,1].car :=#219;

scr[y,80].car:=#219;

end;

x0:=40;

y0:=13;

u:=20*PI/180;

x:=x0;

y:=y0;

for i:=1 to 5 do begin

yP1[i]:=10+i;

yP2[i]:=10+i;

uP[i]:=(i/3*PI-PI)/15;

end;

tasta:=' ';

repeat

if ((u>=0) and (u<PI/2) or (u > 3*PI/2) and (u<2*PI)) then inc(x)

else dec(x);

y:=y0+Trunc(Abs(x-x0) * Sin(u)/Cos(u));

if scr[y,x].car<>' ' then begin

if (y=1)or(y=25) then begin

u:=2*PI-u;x0:=x;

if y=1 then y0:=2 else y0:=24;

end;

if (x=1)or(x=80) then begin

u:=PI+u;if u>2*Pi then u:=u-2*PI;

y0:=y;

if x=1 then x0:=2 else x0:=79;

end;

if x=76 then begin

for i:=1 to 5 do

if y=yP1[i] then begin

sound(1000);

u:=PI+u+uP[i];

if u>2*Pi then u:=u-2*PI;

x0:=x;y0:=y;

end;

nosound;

end;

if x=5 then begin

for i:=1 to 5 do

if y=yP2[i] then begin

sound(600);

u:=PI+u+uP[i];

if u>2*Pi then u:=u-2*PI;

x0:=x;y0:=y;

end;

nosound;

end;

end

else if not (((x=1)or(x=80)) and((y<17)and(y>8))) then

begin

scr[y,x].car:='0';

i:=1;

ok:=false;

repeat

ok:=keypressed;

inc(i);

until (i=viteza)or ok;

if ok then begin

tasta:=readkey;

if tasta = #0 then tasta:=readkey;

mutapaleta1;

mutapaleta2;

end;

Paleta1(#219);

Paleta2(#219);

scr[y,x].car:=' ';

scr[y,x].car:=' ';

end

else begin

sound(800);

if (x>=80)and(y>9)and(y<17) then d:=d+1;

if (x<=1)and(y>9)and(y<17) then s:=s+1;

textcolor(2);

textbackground(7);

gotoxy(39,2);

write('SCOR');

gotoxy(38,3);

write(' ',d,' : ',s);

if (d=5)or(s=5) then begin

gotoxy(35,10);

write(' G A M E O V E R ');

cantec; nosound;

halt;

end;

delay(1500);

paleta1(' ');

paleta2(' ');

x0:=40;

y0:=13;

u:=20*PI/180;

x:=x0;

y:=y0;

for i:=1 to 5 do begin

yP1[i]:=10+i;

yP2[i]:=10+i;

uP[i]:=(i/3*PI-PI)/5;

end;

tasta:=' ';

nosound;

end;

until tasta=#27;

End.



Program Biliard;

uses Graph,Crt;

Const nr_obiecte=10;

raza=25;

pasx=3;pasy=2;

viteza=10;

var

grDriver,grMode,ErrCode: Integer;

i,xMax,yMax,xtmp,ytmp:word;

x,y:Array[1..nr_obiecte] of word;

sensx,sensy:Array[1..nr_obiecte] of shortint;


Procedure Deseneaza(x,y,color:word);

Const bucati=12;

Var x1,y1,unghi,Xasp,Yasp:word;

Begin

SetWriteMode(XORPut);SetColor(color);

GetAspectRatio(Xasp, Yasp);

unghi:=0;

x1:=x+Trunc(raza*cos(unghi*2*PI/bucati));

y1:=y+Trunc(raza*sin(unghi*2*PI/bucati)*Xasp/Yasp);

For unghi:=1 to bucati do begin

xtmp:=x+Trunc(raza*cos(unghi*2*PI/bucati));

ytmp:=y+Trunc(raza*sin(unghi*2*PI/bucati)*Xasp/Yasp);

Line(x1,y1,xtmp,ytmp);Line(x,y,x1,y1);

x1:=xtmp;y1:=ytmp;

end;

End;


begin

grDriver := Detect;

InitGraph(grDriver, grMode,'');

ErrCode := GraphResult;

if ErrCode = grOk then

begin

xMax:=GetMaxX;yMax:=GetMaxY;

Rectangle(0,0,xMax,yMax);

Randomize;

For i:=1 to nr_obiecte do begin

x[i]:=raza+Random(xMax-2*raza);y[i]:=raza+Random(yMax-2*raza);

sensx[i]:=-1+(i mod 2)*2;sensy[i]:=-sensx[i];

Deseneaza(x[i],y[i],i);

end;

Repeat

For i:=1 to nr_obiecte do begin

Deseneaza(x[i],y[i],i);

xtmp:=x[i]+pasx*sensx[i];ytmp:=y[i]+pasy*sensy[i];

If (xtmp>raza) and (xtmp<xMax-raza) then x[i]:=xtmp

else sensx[i]:=-sensx[i];

If (ytmp>raza) and (ytmp<yMax-raza) then y[i]:=ytmp

else sensy[i]:=-sensy[i];

Deseneaza(x[i],y[i],i);

Delay(100-10*viteza);

end;

Until KeyPressed;

Readln;

CloseGraph;

end

else

Writeln('Graphics error:', GraphErrorMsg(ErrCode));

end.


// Program C de umplere a ecranului text prin acces direct la memoria ecran

#include <dos.h>

#include <conio.h>


struct scrcar far *ecran;


int lin,col;

int culoare=BLUE,fundal=LIGHTGRAY;


void main(void)

getch();


Program Acces_direct_ecran_grafic320_200;


Uses crt;

Const maxl=200-1;

maxc=320-1;

mijl=maxc div 2;

Type Matrice=array[0..maxl,0..maxc] of byte;

var

scr:Matrice absolute $A000:0;

i,j,k,l,c,x:integer;

ok:char;

BEGIN

asm 

mov ah,0

mov al,13h

int 10h;

end;

randomize;x:=random(maxc);

for k:=1 to 2 do

for i:=0 to maxl do

for j:=0 to mijl do

scr[i,j+k*mijl]:=random(maxc) ;

k:=0;

repeat

repeat

for i:=0 to maxl do

for j:=0 to mijl do begin

l:=i;c:=j+k*mijl;

if (scr[(l-1)mod maxl,c]<scr[l,c])and

(scr[l,(c-1)mod mijl]<scr[l,c]) then

scr[i,j+((k+1)mod 2)*mijl]:=(scr[(l-1)mod maxl,c]+scr[l,(c-1)mod mijl]+ x)div 3-1

else if (scr[l,(c+1)mod mijl]>scr[l,c])and

(scr[(l+1)mod maxl,c]>scr[l,c]) then

scr[i,j+((k+1)mod 2)*mijl]:=(scr[(l+1)mod maxl,c]+scr[l,(c+1)mod mijl]+ x) div 3+1

else scr[i,j+((k+1)mod 2)*mijl]:=scr[l,c]+1;

end;

k:=(k+1) mod 2;

until keypressed;

ok:=readkey;x:=random(maxc);

if ok<>#27 then ok:=readkey;

until ok=#27;


asm 

mov ax,0

int 10h

end;

END.



Program Mouse;

uses Crt,Graph,Dos;

var

grDriver,grMode,ErrCode : Integer;

mfunc,buton,mx,my,xf,yf,x,y:word;

xi,yi:integer;

s1,s2,s3:string[5];

P : pointer;

Size : Word;



procedure MouseAsm;ASSEMBLER;

ASM

MOV AX,mfunc

MOV BX,buton

MOV CX,mx

MOV DX,my

INT $33

MOV mfunc,AX

MOV buton,BX

MOV mx,CX

MOV my,DX

end;


Begin

grDriver := Detect;

InitGraph(grDriver,grMode,'');

ErrCode := GraphResult;

if ErrCode = grOk then

begin

if mem[memW[0:$cc+2]:memW[0:$cc]]=$cf then

begin

outtext('Mouse-ul nu este instalat!');

readln;closegraph;halt;

end;

mfunc:=0;mouseasm;

mfunc:=1;mouseasm;

mfunc:=3;

mouseasm;xi:=mx;yi:=my;

setactivepage(1);

rectangle(xi,yi,mx,my);

Size := ImageSize(xi,yi,mx,my);

GetMem(P, Size);

GetImage(xi,yi,mx,my,P^);

putimage(xi,yi,P^,XORput);

setactivepage(0);

PutImage(100, 100, P^, ORPut);

repeat

mouseasm;

xi:=mx;yi:=my;

while buton=1 do

begin

PutImage(100, 100, P^,XORPut);

mouseasm;

setactivepage(1);

rectangle(xi,yi,mx,my);

Size := ImageSize(xi,yi,mx,my);

GetMem(P, Size);

GetImage(xi,yi,mx,my,P^);

putimage(xi,yi,P^,XORput);

setactivepage(0);

PutImage(100, 100, P^, ORPut);

end;

until keypressed;

mfunc:=2;mouseasm;

CloseGraph;

end

else

WriteLn('Graphics error:',GraphErrorMsg(ErrCode));

end.



// Program C de generare a efectului grafic-plasma-prin utilizarea unor functii ale modului grafic

#include <graphics.h>

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

#include <math.h>

#include <dos.h>


int MX,MY;

int p1,p2,p3,p4,r1,r2,r3,r4;


void plasma(int x1,int x2,int y1,int y2)


int gdriver = VGA, gmode = VGAHI, errorcode,i;

double red=20,green=30,blue=40;


struct palettetype pal;


void main(void)


/* grab a copy of the palette */

getpalette(&pal);


for (i=0; i<pal.size; i++)

setrgbpalette(pal.colors[i], red+i, green+i, blue+i);


randomize();

MX=getmaxx();MY=getmaxy();

putpixel(0,0,MAXCOLORS/2);

putpixel(0,MY,MAXCOLORS/2);

putpixel(MX,0,MAXCOLORS/2);

putpixel(MX,MY,MAXCOLORS/2);

plasma(0,MX,0,MY);

// rotate palette

while(!kbhit())

closegraph();



Program Sarpe;


Uses Crt;

Const

sc=#219;

lungmax=95;

maxnext=10;

xlimit=[1,80];

ylimit=[1,25];

Var

sx,sy:array[1..95] of byte;

c:char;

i,primul,ultimul,next,tdelay,idelay:integer;

xnext,ynext:byte;

Begin

clrscr;

randomize;

for i:=1 to 79 do begin gotoxy(i,1);write(sc);gotoxy(i,25);write(sc);end;

for i:=1 to 24 do begin gotoxy(1,i);write(sc);gotoxy(80,i);write(sc);end;

primul:=2;ultimul:=1;

for i:=primul downto ultimul do begin sx[i]:=40;sy[i]:=13;end;

next:=0;idelay:=100;

for i:=primul downto ultimul do begin

gotoxy(sx[i],sy[i]);write(sc);

end;

c:=readkey;

while next<maxnext do

begin

xnext:=2+random(78);ynext:=2+random(23);

inc(next);gotoxy(xnext,ynext);write(next);

repeat

if keypressed then begin

c:=readkey;tdelay:=idelay;

if c=#0 then c:=readkey;

end

else tdelay:=tdelay*97 div 100;

case c of

'1'..'9':

idelay:=100+100 div (ord(c)-ord('1')+1);

#75:

begin

gotoxy(sx[ultimul],sy[ultimul]);write(' ');

if primul=lungmax then begin

sx[1]:=sx[primul]-1;sy[1]:=sy[primul];

primul:=1

end

else begin

inc(primul);

sx[primul]:=sx[primul-1]-1;sy[primul]:=sy[primul-1];

end;

if ultimul=lungmax then ultimul:=1

else inc(ultimul);

end;

#77:

begin

gotoxy(sx[ultimul],sy[ultimul]);write(' ');

if primul=lungmax then begin

sx[1]:=sx[primul]+1;sy[1]:=sy[primul];

primul:=1

end

else begin

inc(primul);

sx[primul]:=sx[primul-1]+1;sy[primul]:=sy[primul-1];

end;

if ultimul=lungmax then ultimul:=1

else inc(ultimul);

end;

#72:

begin

gotoxy(sx[ultimul],sy[ultimul]);write(' ');

if primul=lungmax then begin

sx[1]:=sx[primul];sy[1]:=sy[primul]-1;

primul:=1

end

else begin

inc(primul);

sx[primul]:=sx[primul-1];sy[primul]:=sy[primul-1]-1;

end;

if ultimul=lungmax then ultimul:=1

else inc(ultimul);

end;

#80:

begin

gotoxy(sx[ultimul],sy[ultimul]);write(' ');

if primul=lungmax then begin

sx[1]:=sx[primul];sy[1]:=sy[primul]+1;

primul:=1

end

else begin

inc(primul);

sx[primul]:=sx[primul-1];sy[primul]:=sy[primul-1]+1;

end;

if ultimul=lungmax then ultimul:=1

else inc(ultimul);

end;

end;

if primul > ultimul then

for i:=primul downto ultimul do begin

gotoxy(sx[i],sy[i]);write(sc);

if (sx[primul]=sx[i]) and (sy[primul]=sy[i]) and (i<>primul) then

c:=#27;

end

else

begin

for i:=ultimul to lungmax do begin

gotoxy(sx[i],sy[i]);write(sc);

if (sx[primul]=sx[i]) and (sy[primul]=sy[i]) and (i<>primul) then

c:=#27;

end;

for i:=1 to primul do begin

gotoxy(sx[i],sy[i]);write(sc);

if (sx[primul]=sx[i]) and (sy[primul]=sy[i]) and (i<>primul) then

c:=#27;

end;

end;

if (sx[primul] in xlimit)or(sy[primul] in ylimit) then c:=#27;

delay(tdelay);

until (c=#27) or ((sx[primul]=xnext)and(sy[primul]=ynext));

sound(next*30);

if c=#27 then next:=maxnext

else

if ultimul-next <= 0 then begin

for i:=lungmax+ultimul-next to lungmax do begin

sx[i]:=sx[ultimul];sy[i]:=sy[ultimul];

end;

for i:=1 to ultimul do begin

sx[i]:=sx[ultimul];sy[i]:=sy[ultimul];

end;

ultimul:=lungmax+ultimul-next;

end

else begin

for i:=ultimul-next to ultimul do begin

sx[i]:=sx[ultimul];sy[i]:=sy[ultimul];

end;

ultimul:=ultimul-next;

end;

delay(tdelay);

nosound;

end;

End.



Program Scan_Taste;


Uses Crt,Dos;

Var

tasta:byte;

KbdIntVec:procedure;


Procedure KeyClick; interrupt;

begin

Port[$20]:=$20;

end;


Begin

GetIntVec($9,@KbdIntVec);

SetIntVec($9,Addr(KeyClick));

tasta:=0;

repeat

repeat until tasta<>Port[$60];

tasta:=Port[$60];

gotoxy(20,2);write(tasta:3);

until tasta=129;

SetIntVec($9,@KbdIntVec);

End.



Program Taste_muzicale_V2;


Uses Crt,Dos;

Const

Nota_Do:array[1..4] of integer=(33,66,132,264);

Raport:array[1..10]of real=(24/24,27/24,30/24,32/24,36/24,40/24,45/24,

48/24,51/24,54/24);

Nota:array[1..10]of string[3]=('Do','Re','Mi','Fa','Sol','La','Si',

'Do','Re','Mi');

CodT:array[1..4]of byte=(44,30,16,2);


Type Pixel=Record

atrib:byte;

car:char;

end;

Var

tasta:byte;i:integer;

KbdIntVec:procedure;

ecran:array[1..25,1..80]of Pixel absolute $b800:0000;


Procedure KeyClick; interrupt;

begin

Port[$20]:=$20;

end;

Begin

ClrScr;

GetIntVec($9,@KbdIntVec);

SetIntVec($9,Addr(KeyClick));

tasta:=0;

repeat

repeat until tasta<>Port[$60];

tasta:=Port[$60];

if (tasta>=CodT[1])and(tasta<CodT[1]+10) then

begin

gotoxy(5*(tasta+1-CodT[1]),24);write(Nota[tasta+1-CodT[1]]);

sound( Trunc( Raport[ tasta+1-CodT[1] ] * Nota_Do[1] ) )

end

else

if (tasta>=CodT[2])and(tasta<CodT[2]+10) then

begin

gotoxy(5*(tasta+1-CodT[2]),22);write(Nota[tasta+1-CodT[2]]);

sound( Trunc( Raport[ tasta+1-CodT[2] ] * Nota_Do[2] ) )

end

else

if (tasta>=CodT[3])and(tasta<CodT[3]+10) then

begin

gotoxy(5*(tasta+1-CodT[3]),20);write(Nota[tasta+1-CodT[3]]);

sound( Trunc( Raport[ tasta+1-CodT[3] ] * Nota_Do[3] ) )

end

else

if (tasta>=CodT[4])and(tasta<CodT[4]+10) then

begin

gotoxy(5*(tasta+1-CodT[4]),18);write(Nota[tasta+1-CodT[4]]);

sound( Trunc( Raport[ tasta+1-CodT[4] ] * Nota_Do[4] ) )

end

else nosound;

until tasta=129;

SetIntVec($9,@KbdIntVec);

End.



Program Testare_VESA;



uses dos;

type tmoduri=array[1..256] of word;


var imod,vseg,x,y:word; cbank,c:longint; rg:registers;

ntbanks:longint; opt:char;

vesabuf:record sign:longint; vers:word; oem:pchar;

capab:longint; list:^tmoduri;

reserv:array[1..512] of byte end;

vesamod:record attr:word; wina,winb:byte;

gran,winsiz,sega,segb:word; pagfun:pointer;

bytes,width,height:word;

charw,charh,planes,bits,nbanks,model,sbank,

nrimpg,reservb,rms,rfp,gms,gfs,bms,bfs:byte;

reserv:array[1..512] of byte end;


function hexa(v:word):string;

const s:string[16]='0123456789abcdef';

function hexb(b:byte):string;

begin

hexb:=s[b div 16+1]+s[b mod 16+1];

end;

begin

hexa:=hexb(hi(v))+hexb(lo(v));

end;


procedure setbank(b:longint);

begin

vseg:=$a000;

if b<>cbank then with rg,vesamod do begin

cbank:=b; ax:=$4f05; bx:=0;

dx:=b*64 div gran; intr(16,rg);

end;

end;


procedure putpixel(x,y:word; cul:longint);

var l:longint; m,z:word;

begin

with rg,vesamod do case bits of

4: begin

l:=longint(bytes)*y+x div 8;

port[$3ce]:=3; port[$3cf]:=0;

port[$3ce]:=5; port[$3cf]:=2;

port[$3ce]:=8; port[$3cf]:=128 shr (x and 7);

setbank(l shr 16);

z:=mem[vseg:word(l)]; mem[vseg:word(l)]:=cul;

end;

8: begin

l:=longint(bytes)*y+x; setbank(l shr 16);

mem[vseg:word(l)]:=cul;

end;

15,16: begin

l:=longint(bytes)*y+x*2; setbank(l shr 16);

memw[vseg:word(l)]:=cul;

end;

24: begin

l:=longint(bytes)*y+x*3;

z:=word(l); m:=l shr 16; setbank(m);

if z<$fffe then move(cul,mem[vseg:z],3)

else begin

mem[vseg:z]:=lo(cul);

if z=$ffff then setbank(m+1);

mem[vseg:z+1]:=lo(cul shr 8);

if z=$fffe then setbank(m+1);

mem[vseg:z+2]:=cul shr 16;

end;

end;

end;

end;


begin

with rg, vesabuf, vesamod do begin

ax:=$4f00; es:=seg(vesabuf); di:=ofs(vesabuf);

sign:=$41534556; intr(16,rg);

if al<>$4f then begin

writeln('Standardul VESA nu e implementat');

exit end;

imod:=1;

while list^[imod]<>$ffff do begin

ax:=3; intr(16,rg); ax:=$4f01; cx:=list^[imod];

es:=seg(vesamod); di:=ofs(vesamod);

intr(16,rg);

if attr and 16<>0 then begin

writeln(oem,' VESA Versiune ',hi(vers),'.',lo(vers));

writeln(hexa(list^[imod]),

' Rezolutie: ',width,' x ',height,

' Culori: ',longint(1) shl bits);

write('Doriti testare (D/N)? '); readln(opt);

end else opt:='N';

if upcase(opt)='D' then begin

ax:=$4f02; bx:=list^[imod];

intr(16,rg); cbank:=-1;

ntbanks:=longint(bytes)*height div gran div 1024;

for x:=0 to ntbanks do begin

setbank(x); mem[$a000:$ffff]:=0;

fillchar(mem[$a000:0],$ffff,0);

end;

case bits of

4,8: c:=15;

15: c:=32767;

16: c:=65535;

24: c:=longint(1) shl 24-1;

end;

for x:=0 to width-1 do begin

putpixel(x,0,c); putpixel(x,height-1,c);

end;

for y:=0 to height-1 do begin

putpixel(0,y,c); putpixel(width-1,y,c);

end;

for x:=0 to 191 do for y:=0 to 191 do begin

case bits of

4: c:=(y div 48)*4+x div 48;

8: c:=(y div 12)*4+x div 12;

15,16: c:=(y div 6)*(1 shl rfp)+x div 6;

24: c:=longint(x)*65536+y;

end;

putpixel(x+4,y+4,c);

end;

readln;

end;

inc(imod);

end;

ax:=3; intr(16,rg);

end;

end.


Nu se poate descarca referatul
Acest document nu se poate descarca

E posibil sa te intereseze alte documente despre:


Copyright © 2024 - Toate drepturile rezervate QReferat.com Folositi documentele afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul document pe baza informatiilor de pe site.
{ Home } { Contact } { Termeni si conditii }