Probelma 1. Creaţi un program care afişează următoarea funcţie.

Program P2.1;

uses crt;

var i,n,s : integer;

f : boolean;

begin

clrscr;

repeat

write(‘Introduceţi un număr natural n=’);

readln(n);

until n>2;

if n mod 2=0 then f:=false else f:=true;

write(‘s=’);

for i:=1 to n-2 do

if(not f) and (i mod 2 =0)then write(‘*’,i)

else

if f and (i mod 2<>0)then write(‘*’,i);

writeln(‘*’,n);

readkey;

end.

Se dă un număr natural n. Verificaţi daca acest număr este prim sau nu.

Program P2.2;

uses crt;

var i,n,f : integer;

begin

clrscr;

repeat

write(‘Introduceţi un număr natural n=’);

readln(n);

until n>2;

f:=0;

for i:=2 to n div 2 do

if n mod i=0 then f:=1;

if f=0 then

writeln(‘Numărul’,n:6,’ este prim’)

else

writeln(‘Numărul’,n:6,’ nu este prim’);

readkey;

end.

Este dat intervalul numerelor naturale de la n pina la m. Determinati toate numerele naturale din acest interval.

Program P2.3;

uses crt;

var i,n,f,j,r,m : integer;

begin

clrscr;

repeat

write(‘Introduceţi limita de jos a intervalului n=’);

read(n);

write(‘Introduceţi limita de sus a intervalului m=’);

readln(m);

until (n>0) and(m>0) and(n<m);

writeln(‘Introduceţi intervalul de la’,n:6,’pina la’,m:6′);

r:=0;

for j:=n to m do

begin

f:=0;

for i:=2 to j div 2 do

if j mod i=0 then f:=1;

if f=0 then

begin r:=1;

writeln(‘Numărul’,j:6,’ este prim’)

end;

end;

if r=0 then writeln(‘Numărul nu este prim’);

readkey;

end.

Se da un număr natural n. Determinaţi toate numerele prime, inclusiv n.

Program P2.4;

uses crt;

var i,n,f,j,r,m : integer;

begin

clrscr;

repeat

write(‘Introduceţi un număr natural n=’);

readln(n);

until n>0;

writeln(‘Introduceţi intervalul de la 1 pînă la’,n:6′);

r:=0;

for j:=1 to n do

begin

f:=0;

for i:=2 to j div 2 do

if j mod i=0 then f:=1;

if f=0 then

begin r:=1;

writeln(‘Numarul’,j:6,’ este prim’)

end;

end;

if r=0 then writeln(‘Numărul nu este prim’);

readkey;

end.

Introduceţi doua numere naturale m si n. Determinaţi împărţitorul lor comun NOD.

Program p2_5;

uses crt;

var i,m,n,k,nod:integer;

begin

clrscr;

repeat

write(‘Introduceţi numărul natural n=’);

readln(n);

write(‘Introduceţi numărul natural m=’);

readln(m);

until (n>0) and (m>0);

if n>m then k:=m else k:=n;

for i:=1 to k do

if (n mod i=0) and (m mod i=0) then nod:=i;

writeln(‘Împărţitorul numărului comun ‘,n, ‘şi’, m,

‘nod=’,nod);

readkey;

end.

Tema 3:

Sunt date următoarele n numerele naturale. Găsiţi suma tuturor numerelor naturale negative.

Program P3.1;

uses crt;

var n,x,sum,i : integer;

begin

clrscr;

repeat

write(‘Introduceţi lungimea următoarelor numere n=’);

readln(n);

until n>0;

sum:=0;

for i:=1 to n do

begin

writeln(‘introdu x=’);

readln(x);

if x<0 then sum:=sum+x;

end;

if sum=0 then writeln(‘Numărul negativ nu exisţă’)

else

writeln(‘Suma numerelor negative este sum=’,sum);

end.

Sunt date următoarele n numere naturale. Găsiţi numărul maximal.

Program P3.2;

uses crt;

var n,x,max,i : integer;

begin

clrscr;

repeat

write(‘Introduceţi lungimea următoarelor numere n=’);

readln(n);

until n>0;

writeln(‘introdu x=’);

readln(x);

max:=x;

for i:=2 to n do

begin

writeln(‘introdu x=’);

readln(x);

if (x>max) then max:=x;

end;

writeln(‘Numărul maximal este max=’,max);

end.

Sunt date următoarele n numere naturale. Găsiţi numărul maximal din numerele negative.

Program p3_3;

uses crt;

var n,x,max,i:integer;

begin

clrscr;

repeat

write(‘Introduceţi lungimea numărul natural n=’);

readln(n);

until n>0;

max:=0;

repeat

write(‘Introduceţi x=’);

readln(x);

n:=n-1;

until (x<0) o

r (n<=1);

if x<0 then max:=x;

for i:=1 to n do

begin

write(‘Introduceţi x=’);

readln(x);

if (x<0) and (x>max) then max:=x;

end;

if max=0 then write(‘Numărul negativ nu există’)

else

writeln(‘Numărul maximal din numerele negative max:=’,max);

readkey;

end.

Întroduceţi următoarele n numere naturale. Determinaţi de cîte ori alternează şirul din numărul dat.

Program P3_4;

uses crt;

var old,new,f:real;

k,i,n:integer;

begin

clrscr;

repeat

write(‘Introduceţi lungimea numărul natural n=’);

readln(n);

until n>0;

write(‘Introduceţi x=’);

readln(old);

f:=old;

k:=0;

for i:=2 to n do

begin

write(‘Introduceţi x=’);

readln(new);

if (new<>0) and (f=0) then f:=new;

if new*f<0 then

begin

f:=new;

k:=k+1;

end;

old:=new;

end;

if k>0 then

writeln(‘Următorul îsi schimba semnul’, k, ‘odată’)

else

writeln(‘Urmatorul nu-si schimba semnul’);

readkey;

end.

Întroduceţi următoarele numere nenule, 0-sfirsitul enumerării. Determinaţi este oare enumerarea schimbătoare de semn sau nu.

Program P3_5;

uses crt;

var old,new,x:real;

f :boolean;

begin

clrscr;

write(‘Introduceţi x=’);

readln(old);

write(‘Introduceti x=’);

read(new);

f:=true;

repeat

if new*old>0 then f:=false;

old:=new;

write(‘Introduceti x=’);

readln(new);

until new=0;

if f then

writeln(‘Este enumerare schimbătoare de semn’)

else

writeln(‘Nu este enumerare de semn’);

readkey;

end.

Tema 4

Extrageţi intr-un rînd abbccc … zz … z.

Program P4_1;

uses crt;

var i : char;

k,j : integer;

begin

clrscr;

k:=1;

for i:= ‘a’ to ‘z’ do

begin

for j:=1 to k do

write(i);

k:=k+1;

end;

writeln;

readkey;

end.

Extrageţi triunghiul  abc…  z

bc…  z

……   z

Program P4_2;

uses crt;

var i,l : char;

j : integer;

begin

clrscr;

l:=’a';

for j:=1 to 26 do

begin

for i:=’a’ to l do

write(”);

for i:=l to ‘z’ do

write(i);

write;

l:=succ(l);

end;

writeln;

readkey;

end.

Este dat un şir de simboluri. De înlocuit din ’a’ prin ‘aaa’.

Program P4_3;

uses crt;

var str : string;

l,i : integer;

begin

clrscr;

writeln(‘Introduceţi text’);

readln(str);

l:=length(str);

writeln(‘Textul transformat este’);

for i:=1 to l do

if (str[i]=’a') then write(‘aaa’)

else write(str[i]);

writeln;

readkey;

end.

Este dat un şir de simboluri. Ştergeţi din ia toate semnele de punctuaţie.

Program P4_4;

uses crt;

var str : string;

l,i : integer;

m : set of char;

begin

clrscr;

m:=['.',',','!',':',';','?','-'];

writeln(‘Introduceţi text’);

readln(str);

l:=length(str);

writeln(‘Textul transformat este’);

for i:=1 to l do

if not(str[i] in m) then write(str[i]);

writeln;

readkey;

end.

Este dat un şir de simboluri. De schimbat pe toate semnele exclamării pe puncte.

Program P4_5;

uses crt;

var str : string;

l,i : integer;

begin

clrscr;

writeln(‘Introduceţi text’);

readln(str);

l:=length(str);

writeln(‘Textul transformat este’);

for i:=1 to l do

if (str[i]=’!') then write(‘.’);

writeln;

readkey;

end.

Tema 5

Este dat un şir de simboluri. De ividenţiat sub sirul dintre primul si al doilea punct.

Program P5_1;

uses crt;

var s1,str : string;

l,i : integer;

begin

clrscr;

writeln(‘Introduceţi textul’);

readln(str);

s1:=str;

l:=pos(‘.’,s1);

if i<>0 then

begin

delete(s1,1,l);

i:=pos(‘.’,s1);

if i<>0 then

begin

s1:=copy(s1,1,i-1);

writeln(‘Evidenţiaţi şirul dintre primul si al doilea

numar’);

writeln(s1);

end

else

writeln(‘In text este doar un singur punct);

end

else

wrireln(‘In text nu exista punct’);

writeln;

readkey;

end.

Este dat un şir de simboluri. De evidenţiat sub şirul dintre primul si ultimul punct.

Program P5_1;

uses crt;

var s1,str : string;

l,i,j : integer;

begin

clrscr;

writeln(‘Introduceţi textul’);

readln(str);

s1:=str;

l:=pos(‘.’,s1);

j:=i; l:=0;

if i<>0 then

begin

while i<>0 do

begin

delete(s1,1,l);

i:=pos(‘.’,s1);

end;

if i<>0 then

begin

s1:=copy(str,j+1,l-j-1);

writeln(‘Evidentiati sirul primului numar’);

writeln(s1);

end

else

writeln(‘In text este doar un singur punct);

end

else

wrireln(‘In text nu exista punct’);

readkey;

end.

Este dat un şir de simboluri. De evidenţiat sub şirul dintre primul si ultimul punct.

Program P5_2;

uses crt;

var s1,str : string;

l,i,j : integer;

begin

clrscr;

writeln(‘Introduceti text’);

readln(str);

s1:=str;

l:=pos(‘.’,s1);

j:=i; l:=0;

if i<>0 then

begin

while i<>0 do

begin

delete(s1,1,l);

l:=l+i;

i:=pos(‘.’,s1);

end;

if l<>j then

begin

s1:=copy(str,j+1,l-j-1);

writeln(‘Evidentiati sirul primului numar’);

writeln(s1);

end

else

writeln(‘In text este doar un singur punct);

end

else

wrireln(‘In text nu exista punct’);

readkey;

end.

Este dat un şir de caractere până la un punct. Grupul de simboluri intre spatii se scot. De găsit câte cuvinte se încep cu una si aceeaşi litera.

Program P5_3;

uses crt;

var   s1 : string;

k,i,j : integer;

x : char;

begin

clrscr;

writeln(‘Introduceti text’);

readln(s1);

i:=pos(‘.’,s1);

s1:=copy(s1,1,j-1)+”;

k:=0;

repeat

if s1[1]<>”then x:=s1[1];

i:=pos(‘.’,s1);

if i>1 then if x=s1[-1] then k:=k+1;

delete(s1,1,l);

until l=0;

writeln(‘Evidentiati numarul de cuvinte k=’,k’);

readkey;

end.

Este dat un şir de caractere până la un punct. Grupul de simboluri intre spatii se scot. De găsi câte cuvinte conţine trei litere din l.

Program P5_4;

uses crt;

var m,k,l,j : integer;

s1 : string;

begin

clrscr;

writeln(‘Introduceti text’);

readln(s1);

j:=pos(‘.’,s1);

s1:=copy(s1,1,j-1)+”;

m:=0;

repeat

j:=pos(”,s1);

if l>1 then begin

k:=0;

for j:=1 to l-1 do

if s1[j]=’e'then k:=k+1;

if k=3 then m:=m+1;

end;

delete(s1,1,l);

until l=0;

writeln(‘Numarul de cuvinte este k=’,k);

readkey;

end.

Este dat un şir de caractere până la un punct. Grupul de simboluri intre spatii se scot. De verificat daca ea este de la un număr real.

Program P5_5;

uses crt;

var l,k : integer;

s1 : string;

begin

clrscr;

writeln(‘Introduceti text’);

readln(s1);

k:=0; l:=1;

repeat

case s1[l] of

’0′..’9′ :k:=k+(ord(s1[l])-ord(’0′));

”:;

else k:=-1;

end;

i:=i+1

until (s1[l]==’.')or(k<0);

if k mod 5 = 0 then

writeln(‘Esre o cifra zecimala,reala 5′);

readkey;

end.

Tema 6

Se dată o mulţime de numere. De găsit elementul maximal dacă sînt careva elemente maximale. De evidenţiat câte elemente sunt.

Program P6_1;

uses crt;

var mas:array[1..10] of integer;

i,max,k,n : integer;

begin

clrscr;

writeln(‘Introduceţi mărimea şirului n=’);

readln(N);

writeln(‘Introduceţi elementele şirului’);

readln(mas[1]);

max:=mas[1];

k:=1;

for i:=2 to n do

begin

write(‘Introduceţi elementele şirului’);

readln(mas[1]);

if max<mas[i] then

begin

max:=mas[i];

k:=1

end

else

if max = mas[i] then k:=k+1;

end;

writeln(‘Max=’,max, ‘Aceste elemente’, k);

readkey;

end.

Este dată o mulţime de numere. De găsit câte perechi de elemente vecine identice sunt în ea.

Program P6_2;

const m=100;

var mas : array[1..m] of integer;

i,k,n : integer;

begin

readln(n);

k:=0;

for i:=1 to n do

begin

write(‘Introduceţi elementele şirului’);

readln(mas[1]);

end;

for i:=1 to n-1 do

if mas[i]=mas[i+1] then k:=k+1;

writeln(‘Perechile asemenea in şirul elementului este ‘,k);

end.

Este dată o mulţime de numere. De găsit cel mai mare element şi să-l plasăm pe primul loc.

Program P6_3;

const m=100;

var mas : array[1..m] of integer;

i,k,new,n : integer;

begin

write(‘Introduceţi mărimea şirului n=’);

readln(n);

writeln(‘Introduceţi’, n, ‘Şirul elementului’);

for i:=1 to n do

read(mas[i]);

writeln;

new:=mas[n];

k:=n;

for i:=n downto 1 do

if mas[i]>new then

begin

k:=i;

new:=mas[i]

end;

mas[k]:=mas[1];

mas[1]:=new;

for i:=1 to n do

write(mas[i]:4);

writeln

end.

Se cunosc datele despre reuşita a nu mai mult de 27 grupe de studiu(în procente). De evidenţiat cu cît trebuie de ridicat reuşita în cea mai rămasă grupă pentru a atinge nivelul mediu.

Program P6_4;

const m=100;

var mas : array[1..m] of integer;

i,n : integer;

min,sum : real;

begin

write(‘Introduceţi mărimea şirului n=’);

readln(n);

repeat

writeln(‘Introduceţi elementului şirului(%)’);

readln(mas[1]);

until (mas[1]<101)and(mas[1]>0);

min:=mas[1];sum:=min;

for i:=2 to n do

begin

sum:=sum+mas[i];

if min>mas[i] then min:=mas[i];

end;

writeln(‘Dea ridica cea mai înalta grupa’);

writeln(‘Din cel mai jos nivel pe’,(sum/n)-min);

end.

Sunt cunoscute datele despre temperatura medie lunară pe an. De evidenţiat care temperatură a fost cea mai înaltă vara şi cea mai joasă iarna.

Program P6_5;

const m=12;

var mas : array[1..m] of real;

i,n : integer;

min,max : real;

begin

for i:=1 to 12 do

begin

write(‘Introduceţi mărimea şirului’);

readln(mas[i]);

end;

max:=mas[6];min:=mas[12];

for i:=7 to 8 do

if max<mas[i] then max:=mas[i];

for i:=1 to 2 do

if min>mas[i] then min:=mas[i];

writeln(‘Cea mai înalta temperatura vara’, max);

writeln(‘Cea mai joasa temperatura iarna’, min);

end.

Tema 7

Este dată matricea N x M, formată din numere naturale. De găsit cel mai mic element şi poziţia lui dacă sunt mai multe de aceste elemente, de afişat pe ecran poziţiile fiecăruia.

Program P7_1;

Const t;100; s;100;

Var A:array [1..t,1..s] of integer;

n,m,im,jm,i,j,min,k : integer;

begin

write(‘Introduceţi mărimea şirului’);

readln(n);

writeln(‘Introduceţi mărimea şirului’);

readln(m);

for i:=1 to n do

begin

writeln(‘Introduceţi’, m, ‘şiru’l);

for j:’1 to m do

read(a[i,j]);

end;

min:=a[1,1];

im:=1;jm:=1;k:=0;

for i:=1 to n do

for j:=1 to m do

if min>a[i,j] then

begin

k:=1;im:=i;jm:=j;

min:= a[i,j]

end

else

if min= a[i,j] then k:=k+1;

if k=1 then

begin

writeln(’Cel mai mic element este min=’,min);

writeln(’În’, im, ’În rînd’, jm, ’Coloniţă’);

end

else

begin

writeln(’Î n matricea’,k, ’Elementul minimal min =’,min);

for i:=im to n do

for j:=1 to m do

if min=a[i,j] then writeln(’În rând’, i, ’În coloniţaâ,j)

end

end.

Este dată matricea N x M, formată din numere naturale. De a găsi în şiruri cele mai mici elemente din dreapta şi de a găsi poziţia lor.

Program P7_2;

Const t;100; s;100;

Var A:array [1..t,1..s] of integer;

n,m,jm,i,j,min : integer;

begin

write(‘Introduceţi mărimea şirului’);

readln(n);

writeln(‘Introduceţi mărimea şirului’);

readln(m);

for i:=1 to n do

begin

writeln(‘Introduceţi’, m, ‘şirul’);

for j:’1 to m do

read(a[i,j]);

end;

for i:=1 to n do

begin

min:= (a[i,m]);

jm:=m;

for j:=m downto 1 do

if min>a[i,j] then

begin

jm:=j;

min:= a[i,j]

end;

writeln(’În rîndul i=’, i, ’Din dreapta min=’,min);

writeln(’În coloniţa’, jm);

end;

end.

Este dată matricea N x M, formată din numere naturale. De găsit cele mai mici elemente din stânga şi a le pune în prima coloniţă.

Program P7_3;

Const t;100; s;100;

Var A:array [1..t,1..s] of integer;

n,m,jm,i,j,min : integer;

begin

write(‘Introduceţi mărimea şirului n=’);

readln(n);

writeln(‘Introduceţi mărimea şirului m=’);

readln(m);

for i:=1 to n do

begin

writeln(‘Introduceţi’, m, ‘şirul’);

for j:=1 to m do

read(a[i,j]);

end;

for i:=1 to n do

begin

min:= (a[i,1]);

jm:=1;

for j:=1 to m do do

if min>a[i,j] then

begin

jm:=j;

min:= a[i,j]

end;

a[i,jm]:= a[i,1]

a[i,1]:=min

end;

for i:=1 to n do

begin

for j:=1 to m do

write(a[i,j]:4);

writeln

end;

end.

Este dată matricea N x M, alcătuită din litere latine. De aranjat fiecare şir în ordine alfabetică.

Program P7_4;

Const t;100; s;100;

Var A:array [1..t,1..s] of integer;

n,m,i,j,k : integer;

temp:char;

begin

write(‘Introduceţi mărimea şirului n=’);

readln(n);

writeln(‘Introduceţi mărimea şirului m=’);

readln(m);

writeln(’Introduceţi’,m*n, ’litere’);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

for i:=1 to n do

begin

for k:=1 to m-1 do

for j:=k to m do

if a[i,k]>a[i,j] then

begin

temp:= a[i,k]

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

a[i,j]:=temp;

end;

end;

fpr i:=1 to n do

begin

for j:=1 to m do

write(a[i,j]);

writeln

end;

end.

Este dată matricea pătrată N x M, alcătuită din numere naturale, de a o întoarce la 90 de grade împotriva acelor ceasornice şi a extrage rezultatele pe ecran.

Program P7_5;

Const t;100; s;100;

Var A:array [1..t,1..s] of integer;

m,i,j,k : integer;

temp:char;

begin

write(‘Introduceţi lungimea matricei m=’);

readln(m);

writeln(‘Matricea de ieşire’);

k:=1;

for i:=1 to m do

for j:=1 to m do

begin

a[i,j]:=k;

k:=k+1;

if j<m then write(a[i,j]:4)

else writeln(a[i,j]:4)

end;

writeln(’Matricea după întoarcere la 90 de grade’’);

for i:=1 to m do

for j:=1 to m do

begin

b[i,j]:=a[j,m+1-i];

if j<m then write(b[i,j]:4)

else writeln(b[i,j]:4)

end;

end.

Tema 8

Dgukoolfju

Program P8_1;

Var f1,f2 : text;

X : char;

Begin

assign(f1,’c\e\one’);

reset(f1);

assign(f2,’’);

while not eof(f1) do

begin

read(1,x);

write(f2,x+’’+x)

end;

writeln;

close(f1);

close(f2)

end.

Mhfzkrdfdf

Program P8_2;

Var f1 : text;

x : char;

k : integer;

Begin

k:=0;

assign(f1, ’two’);

reset(f1);

while not eof(f1) do

begin

read(f1,x);

if (x=’a’) or (x=’A’) then k:=k+1;

end;

writeln(‚Numărul de litere A:’, K);

closes(f1);

end.

Dtjuetdlofz

Program P8_3;

Var f1 : file of char;

f2 : text;

x : char;

i : integer;

begin

assign(f1, ’two’);

reset(f1);

assign(f2, ’’);

rewrite(f2);

for i:=1 to 2 do

begin

while not eof(f1) do

begin

read(f1,x);

write(f2,x);

end;

writeln;

seek(f1,0)

end;

writeln;

closes(f1);

closes(f2);

end.

K,tzibnhggg

Program P8_4;

Var f1 : file of char;

f2 : text;

x : char;

l,i : integer;

begin

assign(f1, ’two’);

reset(f1);

assign(f2, ’’);

rewrite(f2);

l:=filesize(f1);

while not eof(f1) do

begin

read(f1,x);

write(f2,x)

end;

writeln;

for i:=l-1 downto 0 do

begin

seek(f1,i);

read(f1,x);

write(f2,x)

end;

writeln;

closes(f1);

closes(f2);

end.

Khfkdhztswreh

Program P8_5;

f2 : text;

x : char;

l,i : integer;

begin

assign(f1, ’two’);

reset(f1);

assign(f2, ’’);

rewrite(f2);

k:=-1;

while note of(f1) do

begin

k:=k+1;

read(f1,x);

if x<>’.’ then write(f2,x)

else

begin

seek(f1,k+1);

write(f2,x);

trunca(f1)

end;

end;

writeln;

closes(f1);

closes(f2);

end.

Tema 9

Jhdkzustz

Program P9_1;

const u=100;

Var n,m : integer;

t : array of integer;

procedure tab_in(var l,k : integer);

var i,j : integer;

begin

for i:=1 to l do

beginn

for j:=1 to k do

begin

’);

read(t)

end;

writeln

end

end;

procedure tab_out(var l,k : integer);

var i,j : integer;

begin

for i:=1 to l do

begin

for j:=1 to k do

write(t);

writeln

end

end;

begin

writeln(’Introduceţi mărimea matricii N x M’);

write(’n=’);

read(n);

write(’m=’);

read(m);

tab_in(n,m);

writeln(’Matricea’,m,’x’,m);

tab_out(n,m)

end.

Jhzdddddd

Program P9_2;

var n,m : integer;

function min(i,j : integer) : integer;

begin

if i<j then min:=i;

else min:=j;

end;

begin

writeln(’Introduceţi două numere întregi’);

readln(i,j);

writeln(’min=’,min(i,j));

end.

Fgjjjjjjjj

Program P9_3;

var n : longing;

k : integer;

function min(i,j : longing) : integer;

var s : integer;

begin

s:=0;

repeat

s:=s+n mod 10;

n:=n div 10

until n=0;

num:=s;

end;

begin

write(’Introduceţi un număr intreg n=’);

readln(n);

k:=num(n);

writeln(’Suma cifrelor lor asemănătoare lui’,k);

end.

Ffjjjjjjjjj

Program P9_4;

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

function min(i,j : longing) : integer;

begin

if if i<j then min:=i;

else min:=j;

end;

function min(i,j : longing) : integer;

begin

if if i<j then max:=i;

else max:=j;

end;

begin

repeat

write(’Introduceţi două numere intreg ’);

readln(a,b);

until (a>0) and (b>0);

k:=1;

x:=min(a,b);

y:=max(a,b);

while x<>y do

begin

k:=k+1;

d:=y-x;

y:=max(d,x);

x:=min(d,x);

end;

writeln(’Numărul la pătrat căutat :’,k);

end.

Jhgggggggg

Program P9_5;

var i : integer;

function fib(i,j : integer) : integer;

begin

if i=j then fib:=0;

if (i=1) or (i=2) then fib:=1

else

fib:=fib(i-1)+fib(i-2)

end;

begin

repeat

write(’Introduceţi în ordine numerele întregi i=’);

readln(i);

until i>=;

writeln(i:5,’-Numărul fib corect’,fib(i));

end.

Tema 10

Fjjjjjjjjjjjj

Program P10_1;

uses crt;

var i : integer;

begin

textbackground(2);

clrscr;

delay(1000);

textcolor(0);

for i:=1 to 11 do

begin

textcolor(i+4);

writeln;

write(’’:2*i);

write(’One moment,please…’);

delay(1500);

end;

readln;

textbackground(1);

clrscr

end.

Ddddtttttttt

Program P10_2;

uses crt;

var i,x : integer;

begin

textbackground(1);

clrscr;

x:=1;

delay(1000);

textcolor(0);

for i:=1 to 11 do

begin

if (i<>1) and (i<>9) then textbackground(i);

else textbackground(i+4);

window(x,9,x+5,14);

clrscr;

writeln;

writeln(’?’);

delay(1500);

x:=x+7;

end;

readln;

textbackground(1);

clrscr

end.

Kkkkkkkkkkkkk

Program P10_3;

uses crt;

var i : integer;

begin

textbackground(2);

clrscr;

delay(1000);

for i:=1 to 15 do

begin

textcolor(1+random(15));

window(2*i,i,80-2*i,26-i);

clrscr;

delay(1500);

end;

readln;

textbackground(2);

clrscr

end.

Lllllllll

Program P10_4;

uses crt;

var x,y,i : integer;

begin

textbackground(2);

clrscr;

x:=5;

y:=10;

delay(1000);

for i:=1 to 15 do

begin

x:=x+2;

textcolor(9);

window(x,y,x+18,y+7);

clrscr;

sound(300);

nosound;

delay(500);

nosound;

textcolor(2);

clrscr;

delay(300);

end;

readln;

clrscr

end.

Ttttttttt

Program P10_5;

uses crt;

var x,y,i : integer;

begin

textbackground(2);

clrscr;

x:=30;

y:=2;

delay(1000);

for i:=1 to 15 do

begin

y:=y+1;

textcolor(9);

window(x,y,x+18,y+7);

clrscr;

sound(300);

delay(500);

nosound;

textcolor(2);

clrscr;

delay(300);

end;

readln;

clrscr

end.

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 r²=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,xR,  eps>0 şi x0}

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 r²=x.

Precizăm că-l vom calcula pe r rezolvând ecuaţia r²=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.

PNĂCND 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 (a²-x)*(m²-x)<0. Se ajunge la următoarea variantă finală:

ALGORITMUL RADICAL ESTE:                                                       {Calculează radical din x}

DATE eps,x;                                                                                                     {eps,xR, eps>0 şi x0}

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Ă (a²-x)*(m²-x)<0 ATUNCI b:=m                                                   {rădăcina în stânga}

ALTFEL a:=m                                                                       {rădăcina în dreapta}

SF-DACĂ

PNĂCND 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;                                                                               {nN; pentru n<12 nu există triplete}

REZULTATE toate tripletele de numere pitagorice (a,b,c) cu proprietatea

0<a<b<c şi a+b+cn.

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;                                                                                                {nN; 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,                                                                                                                             {    nN;  a+b+cn        }

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

Un sistem de numeraţie poziţional este caracterizat de baza sa. Numărul cifrelor defineşte baza sistemului de numeraţie. Pentru un sistem de numeraţie poziţional este justă următoarea egalitate:

X(q)=a_nqⁿ+a_n-1q^n-1+…+a₁q¹+a₀q⁰+a_-1q^-1+…+a_-mq^-m,          (1)

unde q – baza sistemului poziţional de numeraţie, un număr întreg; X(q) – un număr arbitrar reprezentat în sistemul de numeraţie poziţional cu baza q; a_i – coeficienţii şirului (cifrele sistemului de numeraţie); n, m – numărul de clase întregi şi fracţionare. În practică se utilizează forma prescurtată de reprezentare a numerelor, adică X(q)=a_na_n-1…a₁a₀a_-1…a_-m.

Egalitatea (1) se utilizează şi pentru conversia numerelor reprezentate într-un sistem poziţional de numeraţie cu baza q în echivalentul său zecimal.

Conversia numărului zecimal X₁₀ în echivalentul său în baza q se efectuează conform următoarelor reguli:

Întrucât 8=2³, conversia binar – octală şi octal – binară se poate face direct. Orice cifră octală se reprezintă prin trei cifre binare, numită triadă:

0 = 000           4 = 100

1 = 001           5 = 101

2 = 010           6 = 110

3 = 011           7 = 111.

Dacă se consideră un număr octal, pentru conversia în binar se va scrie fiecare cifră octală prin trei cifre binare.

Dacă se consideră un număr binar, pentru conversia în octal se vor grupa cîte trei cifre binare, pornind de la poziţia virgulei spre stînga pentru partea întreagă, respectiv dreapta pentru partea fracţionară, găsind corespondentul octal. Pentru completarea unui grup de trei cifre binare, zerourile din faţa numărului, respectiv după ultima cifră a părţii fracţionare nu modifică semnificaţia numărului.

Într-un mod similar se procedează şi în cazul sistemului hexazecimal, baza căruia 16=2⁴. Orice cifră hexazecimală se reprezintă prin 4 cifre binare, numită tetradă:

0 = 0000               8 = 1000

1 = 0001               9 = 1001

2 = 0010               A = 1010

3 = 0011               B = 1011

4 = 0100               C = 1100

5 = 0101               D = 1101

6 = 0110               E = 1110

7 = 0111               F = 1111.

teza_sisteme

3 Þ 4

Notăm cu n numărul de vîrfuri şi cu m numărul de muchii din graf.

Pentru a demonstra că orice graf conex minimal are n-1 muchii vom demonstra prin inducţie completă după n că  m £ n-1. Cum în orice graf conex m ³ n-1, deducem m = n-1.

P(1)                 Dacă n = 1, atunci m = 0 Þ  m = n-1.

P(2)                 Dacă n = 2, atunci  m =1 Þ  m = n-1.

P(n)                 Presupunem că într-un graf conex minimal cu cel mult n vîrfuri numărul de muchii este strict mai mic decît numărul de vîrfuri.

P(n+1)             Demonstrăm că într-un graf conex minimal cu n+1 vîrfuri, numărul de muchii este cel mult egal cu n.

Fie G conex minimal cu n+1 vîrfuri şi m muchii. Eliminînd o muchie oarecare din graf obţinem un graf G’ cu m-1 muchii şi două componente conexe C₁ şi C₂ cu n₁, respectiv n₂ vîrfuri (n₁+n₂ = n+1) şi m₁, respectiv m₂ muchii (m₁+m₂ = m-1). Subgrafurile C₁ şi C₂ sînt conexe minimale, altfel graful G nu ar fi conex minimal. Din ipoteza inductivă rezultă că m₁ £ n₁-1, m₂ £ n₂-1; dar m₁+m₂ = m-1 £ n₁+n₂ = n-2 Þ m £ n-1. Deci G conex minimal implică G conex cu n-1 muchii.

4 Þ 5

Fie G un graf conex cu n-1 muchii. Să demonstrăm că G este aciclic.

Presupunem prin reducere la absurd, că graful G conţine un ciclu C format din  vîrfurile v₁, v₂, …, v_k.

Să considerăm subgraful parţial G_k = (V_k, U_k) constînd  din ciclul C. Deci V_k = {v₁, v₂ ,…, v_k}, iar U_k = {[v₁,v₂)], [v₂,v₃],…,[v_k-1,v_k], (v_k,v₁]} (½V_k½=½U_k½= k). Dacă  ½V_k½<½V½, atunci  $v_iÎV_k şi v_k+1ÎV-V_k astfel încît [v_i, v_k+1]ÎU, graful G fiind conex.

Construim G_k+1 = (V_k+1, U_k+1) în modul următor: V_k+1 = V_k È{v_k+1};     U_k+1=U_kÈ{[v_i,v_k+1]} şi ½U_k+1½=½V_k+1½=k+1.

Cît timp k+1 < n, aplicăm acelaşi procedeu pînă cînd obţinem un graf  G_n = (V, U_n), cu ½U_n½= n, U_n Í U; deci ½U½ ³ n, contradicţie cu ipoteza ½U½= n-1.

5 Þ 6

Presupunem că graful G este aciclic cu n-1 muchii, să demonstrăm că G este aciclic maximal.

Fie C₁, C₂,…, C_p cele p componentele conexe ale grafului G, avînd respectiv n₁, n₂,…, n_p vîrfuri şi m₁, m₂,…, m_p muchii fiecare. Evident că n₁+n₂+…+n_p = n  şi m₁+m₂+…+m_p = n-1.

Cum graful G este aciclic, deducem că fiecare componentă conexă este un arbore. Deoarece am demonstrat că 1 Þ 5, rezultă că m _i= n_i-1, “iÎ{1, 2, …, p}. Înlocuind în relaţia de mai sus, obţinem  n-p = n-1 Þ  p = 1, deci G conex. Dacă G este conex şi aciclic, conform definiţiei G este arbore. Dar am demonstrat că 1 Þ 2, deci oricare două vîrfuri din G sînt unite printr-un lanţ simplu. Astfel, adăugînd orice muchie obţinem un ciclu.

6 Þ 1

Presupunem că graful G este aciclic, dar dacă am mai adăuga o muchie s-ar obţine un ciclu. Să demonstrăm că G este conex.

Fie u şi v două vîrfuri neadiacente din graf, arbitrar alese. Deoarece adăugînd muchia [u, v] se obţine un ciclu, rezultă că u şi v sînt unite printr-un lanţ ale cărui muchii aparţin grafului G. Cum u,v au fost alese arbitrar, deducem că graful G este conex.

Q.E.D.

Teorema 2

Numerele întregi 0 < d₁ £ d₂ £ …£ d_n (n ³ 2) sînt gradele vîrfurilor unui arbore dacă şi numai dacă d₁+d₂+…+d_n = 2n-2.

Demonstraţie:

Necesitatea Condiţia este necesară, deoarece orice arbore cu n vîrfuri are n-1 muchii, iar suma gradelor vîrfurilor oricărui graf este de două ori numărul de muchii. Deci d₁+d₂+…+d_n = 2n-2.

Suficienţa Fie 0 < d₁ £ d₂ £…£ d_n astfel încît d₁+d₂+…+d_n = 2n-2.

Să demonstrăm că există un arbore cu gradele vîrfurilor d₁, d₂,…, d_n. Vom proceda prin inducţie.

P(2)                 Dacă d₁+d₂ = 2, atunci d₁ = d₂ = 1 , arborele fiind cel din figura de mai jos:

Fig. 3

P(n)                 Presupunem acum că proprietatea este adevărată pentru orice secvenţă de n numere naturale 0 < d₁ £ d₂ £ …£ d_n, astfel încît d₁+d₂+…+d_n = 2n-2.

P(n+1)             Să demonstrăm că pentru orice secvenţă 0 < d’₁ £ d’₂ £…£ d’_n £ d’_n+1 astfel încît d’₁+d’₂+…+d’_n+1 = 2n, există un arbore cu n+1 vîrfuri cu secvenţa gradelor d’₁, d’₂, …, d’_n+1.

Observăm că există măcar un nod terminal x₁ cu gradul d’₁=1, altfel dacă  d_i ³ 2,”iÎ{1, 2,…, n+1} Þ d’₁+d’₂+…+d’_n+1 ³ 2(n+1), ceea ce contrazice ipoteza. În mod analog, observăm că există măcar un nod neterminal  x_n+1, cu gradul d’_n+1 > 1, altfel dacă d’_i = 1,”iÎ{1, 2, …, n+1} Þ d’₁+d’₂+…+d’_n+1 = n+1 < 2n .

Să considerăm următoarea secvenţă de n numere întregi d’₂,…, d’_n, d’_n+1-1 cu proprietatea că d’₂+…+d’_n+d’_n+1 = 2n-2. Din ipoteza inductivă există un arbore A_n cu n vîrfuri şi secvenţa gradelor d’₂,…, d’_n, d’_n+1-1. Adăugăm la arborele A_n un vîrf pe care îl unim printr-o muchie cu vîrful avînd gradul d’_n+1-1. Obţinem un arbore A_n+1 cu gradele vîrfurilor d’₁, d’₂,…, d’_n+1.

Q.E.D.

Demonstraţia acestei teoreme oferă şi o soluţie constructivă pentru obţinerea unui arbore cu secvenţa gradelor dată.

Vom reţine gradele vîrfurilor într-un vector d de dimensiune n, ordonat crescător, cu suma componentelor egală cu 2n-2.

Arborele va fi reprezentat prin matricea muchiilor, o matrice a cu două linii şi n-1 coloane, în care pentru fiecare muchie din arbore vom reţine extremităţile.

Spre deosebire de ideea din demonstraţie, pentru a conserva ordinea în vectorul d, la fiecare pas al algoritmului gradul care va fi decrementat va fi primul grad mai mare ca 1 şi nu ultimul.

Capit1

Capit2_partea1

Capit2_partea2

Să considerăm, una din cele mai simple probleme. Se dă un vector cu n componente. Se cere sa se calculeze maximul dintre componentele sale.

Reamintim, pe scurt algoritmul:

Timpul de calcul depinde, în primul rînd, de lungimea(mărimea) datelor de  intrare, pe care o vom nota cu n.

Exemple:

Pentru a calcula timpul de calcul ar trebui inventariem toate instrucţiunile programului şi să ştim d cîte ori se execută fiecare din ele(în funcţie de n).Mai mult, ar trebuie să cunoaştem cît durează execuţia fiecărui tip de instrucţiune.

Observaţie 1.

Exemplu. Pentru calculul maximului, nu putem şti de cîte ori se execută atribuirea max:=v[i]. Cu toate acestea putem considera că există o proporţionalitate între valoarea n şi numărul de execuţii.

Observaţia 2.

Datorită acestor considerate vom proceda astfel.

Se alege o operaţie numită operaţie de bază, şi se vede de cîte ori se execută aceasta. Cerinţa pentru operaţia de bază este ca aceasta să se execute de un număr de ori, numărul care să poată calcula de la început pornind de la n.

Exemplu.

În astfel de cazuri(cînd avem de ales între mai multe operaţii de bază), vom alege acea operaţie care corespunde cît mai bine scopului propus.

Astfel, dacă analizăm un algoritm de generare a permutării comparativ cu altele de aceeaşi natură vom alege ca operaţie de bază comparaţia.

În cazul în care analizăm un algoritm oarecare, în care soluţia este sub formă de permutare, putem considera ca operaţie de bază permutarea. Problema se spune în felul următor: dacă căutăm soluţia printre toate permutările pe care se pot genera vom avea n! căutări(un număr imens !), oare nu se poate altfel?

Exemple de probleme la care se foloseşte un astfel de raţionament: problema comis voiajorului, problema celor n dame.

Timpul estimat de calcul se trece sub formă aproximativă astfel:

O(număr estimat de execuţii ale operaţiei de bază)

Exemplu de exprimare a timpului.

Dacă un algoritm efectuiază 3n²+7n+5 operaţii de bază, vom spune că aceasta este un algoritm cu O(n²).

Exemple.

În cazul de faţă operaţia aleasă este cea de comparare. Pentru un vector cu n componente se fac n-1 comparaţii. Aceasta înseamnă că dacă vectorul are o sută de componente se fac 99 de comparaţii ş.a.m..d.. Se poate demonstra faptul că un algoritm mai bun nu există!

2.  Pentru generarea permuntărilor(în cazul în care se consideră ca operaţie de bază generarea unei permutări) timpul estimat de calcul este O(n!).

În anumite cazuri nu putem preciza nici macar numărul de execuţie ale operaţiilor de bază.

Exemplu. Sortarea prin interschimbare(vezi 6.2.1). În cazul în care vectorul este sortat se execută n-1 comparaţii (se parcurge vectorul o singură dată), dacă vectorul este sortat invers se execută n(n-1)/2 operaţii de bază (se parcurge vectorul de n ori).

În astfel de cazuri se poate considera:

De fiecare dată cînd se trece timpul estimat se precizează despre care este vorba (minim, mediu, maxim). În practică, prezintă interes timpul madiu sau maxim.

Dacă timpul estimat este sub forma O(n^k), k=N*, spunem că algoritmul este în timp polinomial.

Exemlu. Sortarea prin interschimbare are timpul (mediu, maxim) polinomial şi anume O(n²).

Un algoritm în O(n) se numeşte algoritm liniar.

Dacă un algoritm are un timp estimat O(2ⁿ), O(3ⁿ).. spunem că algoritmul este în timp exponenţial.

Un algoritm în timp O(n!) este asimilat unui algoritm în timp exponenţial.

n!=1x2x…n<2x2x….x2=2^n-1.

În practică nu sunt admişi decît algoritm în timp polinomial, deşi nu este deloc indiferent gradul polinomului.

Şi totuşi pentru ce tot acest efort de estimare a timplui de calcul? Oare viteza de lucru a unui calculator nu este atît de mare, în cît abstracţie făcînd de cîteva minute de calcul, în plus sau în minus, să renunţăm la estimarea lui? Răspunsul la această la această întrebarea este categoric negativ. Mai mult timpul de calcul este esenţial dacă este prea mare algoritmul nu are nici un fel de valoare practică. Să ne imaginăm un algoritm care are un timp de calcul O(2ⁿ). Dacă n este de 10, calculatorul va efectua aproximativ 1024 operaţii elementare. Dacă n este 100 acesta va trebui să efectueze 1024^*1024^*…^*1024 operaţii elementare, adică un număr mai mare decît 1000^*1000^*…^*1000 adică 1000000…0000 (de treizeci de ori). Aceasta este un număr imens. Dar dacă n este 1000? pentru un n nu foarte mare, nici cel mai modern calculator din lume nu scoate rezultatul decît în sute sau în mii de ani. De astfel ce înseamnă în asemenea cazuri un calculator modern? Să presupunem că un sistem PENTIUM are o viteză de circa 25 de ori mai mare decît un sistem XT. Să presupunem că avem un program care are un timp de calcul de ordinul O(2ⁿ). Se cere să rezolvăm o problemă pentru n=30. Fie că timpul necesar rulării acestei probleme pe un XT. Această problemă va fi rulată pe PENTIUM în timpul t/25. Dorim să rezolvăm problema pe PENTRIUM pentru n=35 (n a crescut numai cu 5). Dar 2³⁵=2^30*2⁵=32^*2³⁰. Deci dacă n a crescut cu 5, vom avea nevoie de mai mult timp de lucru să rezolvăm problema pe PENTIUM decît timpul pentru rezolvarea ei pentru n=30 pe XT.

Vă daţi seama ce înseamnă un timp de calcul de ordinul O(2ⁿ)? Sporul lui n cu o singură unitate duce la dublarea timpului de calcul.

Ce concluzie tragem de aici? De cîte ori avem de rezovat o problemă căutăm pentru aceasta un algoritm în timp polinomial (polinomul va avea gradul minim). Mai mult căutăm un algoritm care să rezovle problema în timp polinomial de grad minim.

analiza timpului de calcul