Probleme 5
Sa se afiseze toate posibilitatile de a construi drapele cu 3 culori stiind ca:
- avem culorile galben, portocaliu, rosu, visiniu, verde, albastru
- culorile nu se repeta
- culoarea din mijloc nu poate fi galben sau rosu.
Aceasta problema este un caz particular. Nu avem date pe care sa le citim de la tastatura.
O parte din solutii:
galben portocaliu rosu
galben portocaliu visiniu
galben portocaliu verde
galben portocaliu albastru
galben visiniu portocaliu
galben visiniu rosu
galben visiniu verde
galben visiniu albastru
galben verde portocaliu
galben verde rosu
galben verde visiniu
...............................
Codificam culorile:
1 galben
2 portocaliu
3 rosu
4 visiniu
5 verde
6 albatru
Observam ca valoarea minima este 1 si valoarea maxima este 6.
Avem solutie cand am reusit sa depunem 3 culori.
In procedura posibil tratam restrictiile din enunt.
var x:array[1..50]of integer;
k,n:integer;valid:boolean; f:text;s:string;
procedure posibil(k:integer;var valid:boolean);
var i,pd,pi:integer;
begin
valid:=true; /*culorile nu se repeta*/
for i:=1 to k-1 do
if(x[i]=x[k]) then valid:=false;
if(k=2) then if(x[k]=1)or(x[k]=3) then valid:=false; /*in mijloc nu poate fi galben sau rosu*/
end;
function solutie(k:integer):boolean;
var i,pi,pd:integer;
begin /*Avem solutie cand am reusit sa facem un steag cu 3 culori*/
if k=3 then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i,j:byte;
begin
for i:=1 to k do
if(x[i]=1)then write(f,'galben ')
else if(x[i]=2) then write(f,'portocaliu ')
else if(x[i]=3) then write(f,'rosu ')
else if(x[i]=4) then write(f,'visiniu ')
else if(x[i]=5) then write(f,'verde ')
else write(f, 'albastru ');
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=0;
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<6) 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
assign(f,'steaguri.txt');
rewrite(f);
back;
close(f);
end.
Sa se inscriptioneze pe un CD n melodii numerotate de la 1...n astfel incat:
- melodiile sa nu se repete
- melodia 2 sa nu apara inaintea melodii 1
De exemplu pentru n=5 se va afisa
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
1 2 5 4 3
1 3 2 4 5
1 3 2 5 4
1 3 4 2 5
1 3 4 5 2
1 3 5 2 4
1 3 5 4 2
...............
Observam ca valoarea minima este 1 (melodia cu numarul de cod 1) si valoarea maxima este n (melodia cu codul n).
Avem solutie cand am inscriptionat cele n melodii.
Cand inscriptionam, trebuie sa avem grije ca:
- melodia 2 sa nu fi fost inscriptionata inaintea melodii 1
- melodiile sa nu se repete
var x:array[1..50]of integer;
k,n:integer;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i,pd,pi:integer;
begin
valid:=true; /*melodiile nu trebuie sa se repete*/
for i:=1 to k-1 do
if(x[i]=x[k]) then valid:=false;
if (x[k]=1) then /*daca trebuie sa inscriptionam melodia 1 trebuie sa vedem da ca inainte a fost inscriptionata melodia 2*/
for i:=1 to k-1 do
if(x[i]=2) then valid:=false;
end;
function solutie(k:integer):boolean;
var i,pi,pd:integer;
begin /*avem solutie cand s-au inscriptionat cele n melodii*/
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]:=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('n=');readln(n);
assign(f,'melodii.txt');
rewrite(f);
back;
close(f);
end.
Se citeste de la tastatura un cuvant. Sa se afiseze toate anagramarile cuvantului.
De exmplu pentru s='abcb' se va afisa:
a b c d
a b d c
a c b d
a c d b
a d b c
a d c b
b a c d
b a d c
b c a d
b c d a
b d a c
b d c a
c a b d
c a d b
c b a d
c b d a
c d a b
c d b a
d a b c
d a c b
d b a c
d b c a
d c a b
d c b a
Problema se reduce la generarea permutarilor a n obiecte. In acest caz n este lungimea sirului iar elementele sirului sunt codificate cu numere de la 1..n, numere ce reprezinta pozitia initiala a elementelor in sir.
s[x[k]] - elementul aflat in sir pe pozitia x[k]; x[k] reprezinta pozitia elementului in sirul initial (observatie: in algoritmul pe care o sa-l prezentam o sa ne rezumam la afisare fara a schimba structura sirului).
Obsrvam ca:
- elementul maxim este 1 si cel minim este n (codurile=indicii elementelor din sir)
- elementele din solutie nu trebuie sa se repete
- vom afisa caracterul de pe pozitia corespunzatoare
- avem solutie cand s-au introdus in vectorul solutie toate cele n elemente
var x:array[1..50]of integer;
k,n:integer;valid:boolean; f:text;s:string;
procedure posibil(k:integer;var valid:boolean);
var i,pd,pi:integer;
begin
valid:=true; /*elementele nu trebuie sa se repete*/
for i:=1 to k-1 do
if(x[i]=x[k]) then valid:=false;
end;
function solutie(k:integer):boolean;
var i,pi,pd:integer;
begin /*avem solutie cand s-au introdus in vectorul solutie toate cele n elemente*/
if k=n then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i,j:byte;
begin /*Afisam caracterul corespunzator fiecare pozitii*/
for i:=1 to k do
write(f,s[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('dati sirul=');readln(s);
n:=length(s);
assign(f,'sir.txt');
rewrite(f);
back;
close(f);
end.
