Вася хочет представить число 2020 в виде суммы кубов натуральных чисел, содержащих наименьшее количество слагаемых. Помогите ему это сделать.
Answers & Comments
srzontmp
Если время выполнения не важно, то полный перебор. Любое число можно представить в виде суммы не более 9 кубов.
var i,j,k,n,m,p,r,s,u,v,nm,nmb: integer; a: array[0..400] of integer; b: array[1..9,1..3] of integer; begin write('число: '); readln(nm); r:=floor(power(nm,1/3))+1; a[0]:=0; // заполнение массива for i:=1 to r do a[i]:=i*i*i; // заполнение массива циклов // изначально 1 цикл b[1,1]:=1; b[1,2]:=0; b[1,3]:=r; nmb:=1; for i:=2 to 9 do begin b[i,1]:=0; b[i,2]:=0; b[ i,3]:=0; end; // полный перебор repeat for i:=b[1,1] to b[1,3] do for j:=b[2,1] to b[2,3] do for k:=b[3,1] to b[3,3] do for n:=b[4,1] to b[4,3] do for m:=b[5,1] to b[5,3] do for p:=b[6,1] to b[6,3] do for s:=b[7,1] to b[7,3] do for u:=b[8,1] to b[8,3] do for v:=b[9,1] to b[9,3] do if a[i]+a[j]+a[k]+a[n]+a[m]+a[p]+a[s]+a[u]+a[v]=nm then begin b[1,2]:=i; b[2,2]:=j; b[3,2]:=k; b[4,2]:=n; b[5,2]:=m; b[6,2]:=p; b[7,2]:=s; b[8,2]:=u; b[9,2]:=v; for nm:=1 to nmb do write(b[nm,2],' '); writeln; exit; end; inc(nmb); b[nmb,1]:=1; b[nmb,3]:=r; until false; end.
Answers & Comments
var i,j,k,n,m,p,r,s,u,v,nm,nmb: integer;
a: array[0..400] of integer;
b: array[1..9,1..3] of integer;
begin
write('число: '); readln(nm);
r:=floor(power(nm,1/3))+1;
a[0]:=0;
// заполнение массива
for i:=1 to r do a[i]:=i*i*i;
// заполнение массива циклов
// изначально 1 цикл
b[1,1]:=1; b[1,2]:=0; b[1,3]:=r;
nmb:=1;
for i:=2 to 9 do
begin
b[i,1]:=0; b[i,2]:=0; b[ i,3]:=0;
end;
// полный перебор
repeat
for i:=b[1,1] to b[1,3] do
for j:=b[2,1] to b[2,3] do
for k:=b[3,1] to b[3,3] do
for n:=b[4,1] to b[4,3] do
for m:=b[5,1] to b[5,3] do
for p:=b[6,1] to b[6,3] do
for s:=b[7,1] to b[7,3] do
for u:=b[8,1] to b[8,3] do
for v:=b[9,1] to b[9,3] do
if a[i]+a[j]+a[k]+a[n]+a[m]+a[p]+a[s]+a[u]+a[v]=nm then
begin
b[1,2]:=i; b[2,2]:=j; b[3,2]:=k; b[4,2]:=n; b[5,2]:=m;
b[6,2]:=p; b[7,2]:=s; b[8,2]:=u; b[9,2]:=v;
for nm:=1 to nmb do write(b[nm,2],' ');
writeln;
exit;
end;
inc(nmb);
b[nmb,1]:=1;
b[nmb,3]:=r;
until false;
end.
число: 2020
1 1 1 7 7 11
2020 = 1^3 + 1^3 + 1^3 + 7^3 + 7^3 + 11^3