给定一个整数M,求2个整数a,b,使得 sub = a*b-M 最小 (100分)

T

tdKno

Unregistered / Unconfirmed
GUEST, unregistred user!
给定一个整数M,求2个整数a,b,使得 sub = a*b-M 最小
其中 sub为未知,sub>=0, a-b绝对值最小.
例如: M=20,则a =4,b=5.(当然ab可以互换).


 
答案是不是有很多呀
procedure TForm1.Button1Click(Sender: TObject);
VAR
num,num1,num2:integer;
i,j,sub:integer;
begin
num:=StrToIntDef(edit1.Text,0);
sub:=num;
for i:=1 to numdo
for j:=1 to numdo
if ((i*j-num)<=sub) and (i*j-num>=0) then
begin
sub:=i*j-num;
num1:=i;
num2:=j;
if sub=0 then
break;
end;
Edit2.Text:=IntToStr(num1);
Edit3.Text:=IntToStr(num2);
end;
 
似乎缺少条件,按题的意思只要:
a=M,b=1即可。
 
漏一个条件: a-b 的绝对值最小.而且sub不是已知的.
 
那意思就是说要取M的平方根了,最好是M可以直接开方,这样结果也就出来了
如果不是的话就要左右移动了
 
还是缺少条件,按题的意思仍然只要:
a=M,b=1即可。
例如 M=20 a=20 b=1 a*b-m=0
 
其实你的条件很矛盾
你只有两个条件,一是sub最小,一个是|a-b|最小,这两个没有本质的关联的
比如M=21,那么A=5,B=5时sub=4,|a-b|=0
A=3,B=7时sub=0,|a-b|=4
你想要的是哪一个呢?
 
a-b 的绝对值最小 同时又 使得 sub = a*b-M 最小 这个条件有问题
 
不好意思,表达不够清晰.
1 .a-b 的绝对值最小 
2. sub = a*b-M 最小
条件1优先

 
呵呵,那a=b不就可以啦
 
我理解你的意思了,但是条件仍然不全。例如:
M=20 a=5 b=4 |a-b|=1 a*b-M=0
M=20 a=5 b=5 |a-b|=0 a*b-M=5
应该取哪一个?
 
|a-b|=0
a*a=m
m=sqrt(a)
在取整数值
 
绝对值最小优先(且a<>b,a>0,b>0)
算法如下
var x:real;
y:integer;
x:=M的平方跟
y:=x取整
if y*(y+1)>=M then
begin
a:=y;
b:=y+1;
end
else
begin
a:=y+1;
b:=y+2;
end;

很简单的啊
 
sub最小优先:
procedure TForm1.Button1Click(Sender: TObject);
var
i,n,m,k,min,d:Integer;
begin
n:=SpinEdit1.Value;
Memo1.Text:=Format('Aim:%6d'#13#10#13#10,[n]);
m:=Trunc(Sqrt(n));
min:=n;
i:=m;
k:=0;
while i>=1do
begin
k:=n div i;
d:=n-i*k;
if d<min then
begin
min:=d;
Memo1.Lines.Add(Format('a:%6d b:%6d sub:%3d',[i,k,d]));
if d=0 then
break;
end;
Dec(i);
end;
Memo1.Lines.Add(Format(#13#10'Result: a:%6d b:%6d',[i,k]));
end;

eg:
Aim:2345671
a: 1531 b: 1532 sub:179
a: 1495 b: 1569 sub: 16
a: 1286 b: 1824 sub: 7
a: 1206 b: 1945 sub: 1
a: 191 b: 12281 sub: 0
Result: a: 191 b: 12281

综合方案:
sub+|a-b| 最小。
procedure TForm1.Button2Click(Sender: TObject);
var
i,n,m,k,min,d1,d2,d,mi,mk:Integer;
begin
n:=SpinEdit1.Value;
Memo1.Text:=Format('Aim:%6d'#13#10#13#10,[n]);
m:=Trunc(Sqrt(n));
min:=n;
i:=m;
mk:=0;
mi:=0;
while i>=1do
begin
k:=n div i;
d1:=n-i*k;
d2:=k-i;
if d2>min then
break;
d:=d1+d2;
if d<min then
begin
min:=d;
mi:=i;
mk:=k;
Memo1.Lines.Add(Format('a:%6d b:%6d sub:%3d a-b:%3d sum:%3d',[i,k,d1,d2,d]));
end;
Dec(i);
end;
Memo1.Lines.Add(Format(#13#10'Result: a:%6d b:%6d',[mi,mk]));
end;

eg:
Aim:234567
a: 484 b: 484 sub:311 a-b: 0 sum:311
a: 471 b: 498 sub: 9 a-b: 27 sum: 36
Result: a: 471 b: 498
 

Similar threads

D
回复
0
查看
2K
DelphiTeacher的专栏
D
D
回复
0
查看
2K
DelphiTeacher的专栏
D
D
回复
0
查看
1K
DelphiTeacher的专栏
D
S
回复
0
查看
962
SUNSTONE的Delphi笔记
S
顶部