Probleme 1
Se dau n multimi fiecare multime avand elementele 1...m. Sa se afiseze produsul cartezian a celor n multime. Afisarea sa se realizeze intr-un fisier.
Exemplu:
n=3 m=4
Solutii:
1 1 1
1 1 2
1 1 3
1 1 4
1 2 1
1 2 2
......
Observam ca valoarea elementului minim de pe fiecare coloana este 1 iar valoarea elementului maxim este m.
Elementul x[k] poate fi adaugat la solutie indiferent de elementele aflate pe pozitiile 1...k-1 din solutie.
Avem solutie daca numarul de elemente din vectorul solutie este egal cu numarul multimilor (n).
var x:array[1..50]of byte;
k,n,m:byte;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);{nu exista restrictii la adaugarea elementului x[k]}
begin
valid:=true;
end;
function solutie(k:integer):boolean;{avem solutie daca numarul de elemente din vectorul solutie este egal cu numarul multimilor (n)}
begin
if(k=n) then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);{afisarea vectorului solutie}
var i:byte;
begin
for i:=1 to k do write(f,x[i],' ');
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=0;{intializam cu valoarea elementului minim-1}
while(k>0) do begin
valid:=false; {x[k] nu e valid pentru a fi adaugat in solutie}
while(not valid)and(x[k]<m) do {cat timp nu s-a gasit un element x[k] valid pentru solutie si mai sunt valori pe care le poate avea x[k]}
begin
x[k]:=x[k]+1; {trecem la verificarea urmatoarei valori pentru x[k]}
posibil(k,valid);
end;
if(not valid) then k:=k-1 {daca s-au verificat toate valorile pe care le paote avea x[k] si nu am gasit un element valid ne intoarcem la pozitia elementului anterior si continuam cautarea de aici}
else if(solutie(k)) then afisare(k) {daca avem solutie o afisam}
else begin {daca am gasit un element x[k] valid si nu am ajuns la o solutie}
k:=k+1;
x[k]:=0;
end;
end;
end;
begin
write('numarul de multimi=');readln(n);
write('numarul de elemente din fiecare multime=');readln(m);
assign(f,'prod.txt');
rewrite(f);
back;
close(f);
end.
Sa se afiseze toate modalitatile de a aranja n obiecte numerotate 1...n. (Generarea permutarilor)
Exemplu:
n=3
Solutiile sunt:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Observam ca:- valoarea elementului minim este 1 iar valoarea elementului maxim este n
- elementul x[k] nu poate fi adaugat la solutie daca a mai aparut in solutie pe vreuna din pozitiile 1...k-1 (elementul nu se repeta)
- avem solutie cand am reusit sa asezam cele n obiecte
var x:array[1..50]of byte;
k,n:byte;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i:integer;
begin
valid:=true; {presupunam ca x[k] poate fi adaugat la solutie}
for i:=1 to k-1 do {verificam repetitia elementului x[k]: daca a mai aparut in sir x[k] nu poate fi adaugat la solutie}
if(x[k]=x[i])then valid:=false;
end;
function solutie(k:integer):boolean;
begin
if(k=n) then solutie:=true {avem solutie daca s-au adaugat la solutie n elemente}
else solutie:=false;
end;
procedure afisare(k:integer);
var i:byte;
begin {afisam vectorul solutie}
for i:=1 to k do write(f,x[i],' ');
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=0;
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<n) do
begin
x[k]:=x[k]+1;
posibil(k,valid);
end;
if(not valid) then k:=k-1
else if(solutie(k)) then afisare(k)
else begin
k:=k+1;
x[k]:=0;
end;
end;
end;
begin
write('numarul de obiecte=');readln(n);
assign(f,'perm.txt');
rewrite(f);
back;
close(f);
end.
Se dau n obiecte. Sa se gaseasca toate modalitatile de a aranja intr-un sir m dintre cele n obiecte (generarea aranjamentelor)
Exemplu:
n=4 m=3
Solutii:
1 2 3
1 2 4
1 3 2
1 3 4
1 4 2
1 4 3
2 1 3
2 1 4
2 3 1
2 3 4
2 4 1
2 4 3
3 1 2
3 1 4
3 2 1
3 2 4
3 4 1
3 4 2
4 1 2
4 1 3
4 2 1
4 2 3
4 3 1
4 3 2
Observam ca:- valoarea minima este 1 si valoarea maxima este n
- avem solutie daca aranjam m obiecte
- x[k] poate fi adaugat la solutie daca nu a mai fost adaugat (elementele din solutie nu se repeta)
var x:array[1..50]of byte;
k,n,m:byte;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i:integer;
begin
valid:=true; {elementele nu se repeta}
for i:=1 to k-1 do
if(x[k]=x[i])then valid:=false;
end;
function solutie(k:integer):boolean;
begin {avem solutie daca au fost aranjate m obiecte}
if(k=m) then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i:byte;
begin {afisam vectorul solutie}
for i:=1 to k do write(f,x[i],' ');
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=0;
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<n) do
begin
x[k]:=x[k]+1;
posibil(k,valid);
end;
if(not valid) then k:=k-1
else if(solutie(k)) then afisare(k)
else begin
k:=k+1;
x[k]:=0;
end;
end;
end;
begin
write('numarul de obiecte=');readln(n);
write('m=');readln(m);
assign(f,'aranj.txt');
rewrite(f);
back;
close(f);
end.
Se dau n obiecte numerotate de la 1...n. Sa se gaseasca toate posibilitatile de a aranja cate m obiecte din cele n astfel incat multimile de elemente sa nu se repete.
Exemplu:
n=4 m=3
solutii:
1 2 3
1 2 4
1 3 4
2 3 4
Observam ca:
- valoarea elementului minim este 1; valoarea elementului maxim este n
- elementele din solutie nu se repeta
- pentru a nu se repeta multimile de elemente (adica solutia 1 2 3 este aceiasi cu 2 1 3, 1 3 2...) elementele sunt introduse in solutie in ordine crescatoare/descrescatoare. Alegem varianta in care elementele sunt in ordine crescatoare.
- avem solutie cand am introdus in solutie m elemente
var x:array[1..50]of byte;
k,n,m:byte;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i:integer;
begin
valid:=true;
{elementele din solutie nu se repeta}
for i:=1 to k-1 do
if(x[k]=x[i])then valid:=false;
{multimile de solutii nu se repeta: elementele sunt in ordine crescatoare}
if(k>1) then if(x[k]<x[k-1]) then valid:=false;
end;
function solutie(k:integer):boolean;
begin {avem solutie daca au fost introduse in vectorul solutie m elemente}
if(k=m) then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i:byte;
begin {afisam vectorul solutie}
for i:=1 to k do write(f,x[i],' ');
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=0;
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<n) do
begin
x[k]:=x[k]+1;
posibil(k,valid);
end;
if(not valid) then k:=k-1
else if(solutie(k)) then afisare(k)
else begin
k:=k+1;
x[k]:=0;
end;
end;
end;
begin
write('numarul de obiecte=');readln(n);
write('m=');readln(m);
assign(f,'comb.txt');
rewrite(f);
back;
close(f);
end.
