Probleme 4
Dintr-o cusca trebuie scosi n lei si m tigrii (m<=n). Sa se afiseze toate posibilitatile de a scoate animalele din cusca astfel incat sa nu iasa doi tigrii unul dupa altul.
De exemplu:
n=5 si m=2 se va afisa:
leu leu leu leu tigru leu tigru
leu leu leu tigru leu leu tigru
leu leu leu tigru leu tigru leu
leu leu tigru leu leu leu tigru
leu leu tigru leu leu tigru leu
leu leu tigru leu tigru leu leu
leu tigru leu leu leu leu tigru
leu tigru leu leu leu tigru leu
leu tigru leu leu tigru leu leu
leu tigru leu tigru leu leu leu
tigru leu leu leu leu leu tigru
tigru leu leu leu leu tigru leu
tigru leu leu leu tigru leu leu
tigru leu leu tigru leu leu leu
tigru leu tigru leu leu leu leu
Vom codifica cu 0 leii si cu 1 tigrii. Acest mod de codificare nu este unic!
Observam ca:
- valoarea minima este 0 iar valoarea maxima este 1
- avem solutie daca numarul de tigrii este m si numarul de lei este n
- x[k] poate face parte din solutie daca:
* in cazul in care x[k] reprezinta codul unui tigru x[k-1] trebuie sa reprezinte codul unui leu
*din cusca nu se pot scoate mai multi de n lei si mai multi de m tigrii.
var x:array[1..50]of integer;
k,n,m:integer;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i,tig,lei:integer;
begin
valid:=true; /*numaram leii si tigrii din solutie*/
tig:=0;lei:=0;
for i:=1 to k do
if(x[i]=0) then lei:=lei+1
else tig:=tig+1;
if(tig>m)or(lei>n) then valid:=false; /*nu putem scoate din cusca mai multi de n lei si mai multi de m tigrii*/
if(k>1)and(x[k-1]=1)and(x[k]=1) then valid:=false; /*nu putem scoate din cusca 2 tigrii unul dupa altul*/
end;
function solutie(k:integer):boolean;
var i,tig,lei:integer;
begin /*avem solutie daca in vectorul solutie numarul de tigrii este m si numarul de lei este n*/
tig:=0;lei:=0;
for i:=1 to k do
if(x[i]=0) then lei:=lei+1
else tig:=tig+1;
if(tig=m)and(lei=n) then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i,j:byte;
begin /*Afisam solutia gasita*/
for i:=1 to k do
if(x[i]=0) then
write(f,'leu ')
else write(f,'tigru ');
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=-1;/*initializam cu valoarea minima=0 -1*/
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<1) do /*valoarea maxima este 1*/
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]:=-1;/*initializam cu valoarea minima -1*/
end;
end;
end;
begin
write('nr lei=');readln(n);
write('nr tigrii=');readln(m);
if(m>n) then begin write('eroare');halt;end; /*daca avem mai multi tigrii decat lei rezolvarea problemei este imposibila*/
assign(f,'leitig.txt');
rewrite(f);
back;
close(f);
end.
Sa se afiseze toate posibilitatile de a inchide corect n paranteze.
Codificam parantezele astfel:
( cu 0
si
) cu 1.
Pentru n=6 solutiile sunt:
((()))
(()())
(())()
()(())
()()()
Observam ca valoarea minima este 0 si valoarea maxima este 1.
Avem solutie daca numarul de paranteze inchise este n/2 si numarul de paranteze deschise este n/2.
Adaugam elementul x[k] la solutie daca:
- in cazul in care este primul element din sir trebuie sa fie (
- numarul de paranteze deschise trebuie sa fie mai mare sau egal cu numarul de paranteze inchise
- numarul de paranteze inchise si numarul de paranteze deschise nu pot depasi n>2.
Observatie: pentru a putea construi sirul de paranteze n trebuie sa fie numar par.
var x:array[1..50]of integer;
k,n,m:integer;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i,pd,pi:integer;
begin
valid:=true;
pd:=0;pi:=0;
for i:=1 to k do
if(x[i]=0) then pd:=pd+1
else pi:=pi+1;
if(pd>n div 2)or(pi>n div 2) then valid:=false;/*numarul de paranteze inchise si numarul de paranteze inchise nu pot depasi n/2*/
if(pd<pi) then valid:=false;/*numarul de paranteze deschise trebuie sa fie mai mare sau egal cu numarul de paranteze inchise*/
if(k=1) then if(x[k]=1) then valid:=false;/*prima paranteza trebuie sa fie deschisa*/
end;
function solutie(k:integer):boolean;
var i,pi,pd:integer;
begin /*avem solutie daca numarul de paranteze inchise si numarul de paranteze deschise este n/2*/
pd:=0;pi:=0;
for i:=1 to k do
if(x[i]=0) then pd:=pd+1
else pi:=pi+1;
if(pd=n div 2)and(pi=n div 2) then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i,j:byte;
begin /*afisam solutia*/
for i:=1 to k do
if(x[i]=0) then
write(f,'(')
else write(f,')');
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=-1;/*initializam x[k] cu valoarea minima-1*/
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<1) do /*valoarea maxima este 1*/
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]:=-1;/*initializam cu valoarea minima -1*/
end;
end;
end;
begin
write('n=');readln(n);
assign(f,'paran.txt');
rewrite(f);
if(n mod 2=1) then begin write('imposibil');halt;end;
back;
close(f);
end.
Pentru n cuburi se cunosc dimensiunea laturii si culoarea.
Sa se afiseze toate posibilitatile de a construi turnuri din catem cuburi stiind ca:
- doua cuburi de aceasi culoare nu pot fi puse unul langa altul
- un cub cu latura mai mare nu poate fi pus peste un cub cu latura mai mica.
Exemplu:
n=4 si m=3
Avem 4 cuburi. Pentru fiecare citim culoarea si dimensiunea laturii.
rosu 4
galben 3
rosu 2
verde 3
Se va afisa:
1(rosu 4) 2(galben 3)
1(rosu 4) 4(verde 3)
2(galben 3) 3(rosu 2)
2(galben 3) 4(verde 3)
4(verde 3) 2(galben 3)
4(verde 3) 3(rosu 2)
dupa modelul numar_cub(culoare dimensiune)
Observam ca:
- valoarea minima este 1 si valoarea maxima este n (cuburile sunt numeroate de la 1...n)
- avem solutie cand in vectorul solutie avem m cuburi
- respectam conditiile din enunt. In plus, un cub nu poate fi pus de doua ori in acelasi turn.
var x:array[1..50]of integer;
k,n,m:integer;valid:boolean; f:text;
cul:array[1..50]of string;
dim:array[1..50]of byte;
procedure posibil(k:integer;var valid:boolean);
var i,pd,pi:integer;
begin
valid:=true; /*cuburile nu se repeta*/
for i:=1 to k-1 do
if(x[i]=x[k]) then valid:=false;
if(k>1) then if(cul[x[k-1]]=cul[x[k]]) then valid:=false;/*nu pot fi puse unul peste altul 2 cuburi de aceiasi culoare*/
if(k>1) then if(dim[x[k-1]]<dim[x[k]]) then valid:=false;/*un cub cu latura mai mare nu poate fi pus peste un cub cu dimensiunea laturii mai mica*/
end;
function solutie(k:integer):boolean;
var i,pi,pd:integer;
begin /*avem solutie cand am pus in turn m cuburi*/
if k=m then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i,j:byte;
begin
for i:=1 to k do
write(f,x[i],'(',cul[x[i]],' ',dim[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;
procedure citire;
var i:byte;
begin
write('n=');readln(n);
write('m=');readln(m);
for i:=1 to n do begin
write('culoarea cubului ',i,':');readln(cul[i]);
write('dimensiunea laturii pentru cubul ',i);readln(dim[i]);
end;
end;
begin
citire;
assign(f,'turn.txt');
rewrite(f);
if(n mod 2=1) then begin write('imposibil');halt;end;
back;
close(f);
end.
Sa se afiseze numerele toate numerele cu cel mult n cifre care sunt formate numai din cifre pare care nu se repeta.
Exemplu:
pentru n=3 se va afisa:
2
2 0
2 0 4
2 0 6
2 0 8
2 4
2 4 0
2 4 6
2 4 8
2 6
2 6 0
2 6 4
2 6 8
2 8
2 8 0
2 8 4
2 8 6
4
4 0
......
Observam:
- valoarea minima este 0 si valoarea maxima este 9.
- avem solutie daca numarul de elemente din solutie este cel mult n, prin urmare, dupa ce afisam o solutie cautam urmatoarele elemente pe care le putem adauga solutiei pentru a gasi si alte solutii.
- x[k] face parte din solutie daca:
* prima cifra din numar nu trebuie sa fie 0 (acest caz poate fi optimizat in rezolvarea problemei)
* cifrele sunt numere pare
*cifrele nu se repeta
var x:array[1..50]of integer;
k,n,m:integer;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i,pd,pi:integer;
begin
valid:=true; /*cifrele nu se repeta*/
for i:=1 to k-1 do
if(x[i]=x[k]) then valid:=false;
if(x[k]mod 2=1) then valid:=false; /*cifrele sunt numere pare*/
if(k=1)and(x[k]=0) then valid:=false;/*prima cifra e diferita de 0*/
end;
function solutie(k:integer):boolean;
var i,pi,pd:integer;
begin /*Avem solutie daca in vectorul solutie avem cel mult n cifre*/
if k<=n then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i,j:byte;
begin
for i:=1 to k do
write(f,x[i],' ');
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=-1;/*initializam cu valoarea minima -1*/
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<9) do
begin
x[k]:=x[k]+1;
posibil(k,valid);
end;
if(not valid) then k:=k-1
else if(solutie(k)) then begin afisare(k); /*trecem la cautarea unei alte solutii pornind de la cea gasita*/
k:=k+1;
x[k]:=-1;
end
else begin /*trecem la urmatorul element din vectorul solutie*/
k:=k+1;
x[k]:=-1;
end;
end;
end;
begin
write('n=');readln(n);
assign(f,'nr.txt');
rewrite(f);
back;
close(f);
end.
