Probleme 3
Sa se scrie un numar n ca suma de numere naturale.
Exemplu:
pentru n=6 se va afisa
1 1 1 1 1 1
1 1 1 1 2
1 1 1 2 1
1 1 1 3
1 1 2 1 1
1 1 2 2
1 1 3 1
1 1 4
1 2 1 1 1
1 2 1 2
1 2 2 1
1 2 3
1 3 1 1
1 3 2
1 4 1
1 5
2 1 1 1 1
2 1 1 2
2 1 2 1
2 1 3
2 2 1 1
2 2 2
2 3 1
2 4
3 1 1 1
3 1 2
3 2 1
3 3
4 1 1
4 2
5 1
6
Observam ca:
- valoarea minima este 1 si valoarea maxima este n
- avem solutie cand suma elementelor din vectorul solutie este egala cu n
- adaugam elementul x[k] la solutie daca suma elementelor din solutie nu depaseste n.
Observatie: Algoritmul urmator poate fi imbunatatit
- sa nu se repete multimile de elemente
- daca x[k] nu este valid nici urmatoarele elemente de la x[k]+1...n nu sunt valide.
var x:array[1..50]of byte;
k,n:byte;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i,s:integer;
begin
valid:=true; /*x[k] poate fi adaugat la solutie doar daca prin adaugarea lui suma elementelor din vectorul solutie nu depaseste n*/
s:=0;
for i:=1 to k do s:=s+x[i];
if s>n then valid:=false;
end;
function solutie(k:integer):boolean; /*avem solutie daca suma elementelor din solutie este egala cu n*/
var i,s:integer;
begin
s:=0;
for i:=1 to k do s:=s+x[i];
if(s=n) then solutie:=true else solutie:=false;
end;
procedure afisare(k:integer);/*afisam solutia*/
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,'suma.txt');
rewrite(f);
back;
close(f);
end.
Sa se afiseze n ca suma de m numere naturale.
Spre deosebire de problema precedenta avem solutie daca suma elementelor din solutie este n si numarul de elemente din solutie este m.
Exemplu:
pentru n=7 si m=3 se va afisa:
1 1 5
1 2 4
1 3 3
1 4 2
1 5 1
2 1 4
2 2 3
2 3 2
2 4 1
3 1 3
3 2 2
3 3 1
4 1 2
4 2 1
5 1 1
var x:array[1..50]of byte;
k,n,m:byte;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i,s:integer;
begin
valid:=true;/*adaugam pe x[k] la solutie daca si numai daca prin adaugare suma elementelor din solutie nu depaseste n*/
s:=0;
for i:=1 to k do s:=s+x[i];
if s>n then valid:=false;
end;
function solutie(k:integer):boolean;/*avem solutie daca numarul de elemente din solutie este m si suma elementelor din solutie este n*/
var i,s:integer;
begin
s:=0;
for i:=1 to k do s:=s+x[i];
if(s=n)and(k=m) then solutie:=true else solutie:=false;
end;
procedure afisare(k:integer);/*afisam solutia*/
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);
write('m=');readln(m);
assign(f,'suma.txt');
rewrite(f);
back;
close(f);
end.
Sa se scrie n ca suma de numere prime.
Exemplu:
pentru n=10 se va afisa:
2 2 2 2 2
2 2 3 3
2 3 2 3
2 3 3 2
2 3 5
2 5 3
3 2 2 3
3 2 3 2
3 2 5
3 3 2 2
3 5 2
3 7
5 2 3
5 3 2
5 5
7 3
observam ca valoarea minima este 1 si valoarea maxima poate fi n (daca n este numar prim). Aceast rationament poate fi optimizat.
Avem solutie daca suma elementelor din vectorul solutie este n.
Putem adauga elementul x[k] la solutie daca este prim si daca prin adaugarea lui suma elementelor din vectorul solutie nu depaseste valoarea n. (puteti modifica algortimul astfel: in cazul in care x[k] este numar sa se verifice daca prin adaugarea lui la vectorul solutie suma elementelor din vectorul solutie nu depaseste n.
var x:array[1..50]of byte;
k,n,m:byte;valid:boolean; f:text;
function prim(n:integer):boolean;/*functia pentru a verifica daca un numar este prim - functia poate fi optimizata*/
var i:integer;
begin
prim:=true;
if(n<=1) then prim:=false;
for i:=2 to n div 2 do
if n mod i=0 then prim:=false;
end;
procedure posibil(k:integer;var valid:boolean);
var i,s:integer;
begin
valid:=true;
if not prim(x[k]) then valid:=false;/*verificam daca x[k] este numar prim*/
s:=0;
for i:=1 to k do s:=s+x[i];
if s>n then valid:=false;/*adaugam pe x[k] la solutie daca prin adaugarea lui x[k] suma elementelor din vectorul solutie nu depaseste n*/
end;
function solutie(k:integer):boolean;
var i,s:integer;
begin /*avem solutie daca suma elementelor din vectorul solutie este egala cu n*/
s:=0;
for i:=1 to k do s:=s+x[i];
if(s=n)then solutie:=true else solutie:=false;
end;
procedure afisare(k:integer);/*afisam solutia*/
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,'suma.txt');
rewrite(f);
back;
close(f);
end.
