主题:[原创]求一个数值分解的算法
题目:
把1000——100万之内的任意一个数值分解成如下数值的和:858、300、240、120、90、85、60、30、25、21、17、12、8、7、6、5、4
可以是以上这些数任意一个或几个的组合,要求要尽量少的加数项,比如:3000 分解成858+858+858+300+120+6而不能分解成300+300……+300,更不能分解成30+30+……30
要求:
1、用字符串把数值组合输出
关于这个问题小黑同志已经给出Delphi代码了,但是因为我对Delphi了解不深加上他在算法中用了递归,所以我脑袋一团浆糊,无论如何也搞不懂了。
他的Delphi代码如下:
procedure TForm1.Button1Click(Sender: TObject);
const
cBaseNumbers: array[0..16] of Integer = (858, 300, 240, 120, 90, 85, 60, 30,
25, 21, 17, 12, 8, 7, 6, 5, 4);
var
vMinCount: Integer;
vPath: string;
procedure pScan(
ADest: Integer;
ALevel: Integer;
ACount: Integer;
APath: string
);
var
I: Integer;
begin
if ALevel > High(cBaseNumbers) then Exit;
if ADest = 0 then
begin
if ACount < vMinCount then
begin
vMinCount := ACount;
vPath := APath;
end;
end
else
begin
I := ALevel;
while I <= High(cBaseNumbers) do
begin
if ADest >= cBaseNumbers then
pScan(ADest mod cBaseNumbers, ALevel + 1,
ACount + ADest div cBaseNumbers,
APath + Format('+%d*%d', [ADest div cBaseNumbers,
cBaseNumbers]));
Inc(I);
end;
end;
end;
begin
vMinCount := MaxInt;
vPath := '';
pScan(SpinEdit1.Value, 0, 0, '');
Delete(vPath, 1, 1);
Memo1.Lines.Add(vPath);
end;
下面这个是我用C#写的代码:
class Count
{
public int[] BaseNumbers = new int[] {858,300,240,120,90,85,60,
30,25,21,17,12,8,7,6,5,4};
public string[] NumberStrings = new string[] { "858","300","240","120","90","85","60","30","25","21","17","12","8","7","6","5","4"};
public StringBuilder strb = new StringBuilder("目标数分解为:\r\n\r\n", 64);
public void Scan(int target) {
for (int i = 0; i < BaseNumbers.Length; i++)
{
if (target >= BaseNumbers) {
int level = (int)(target/BaseNumbers);
target = target % BaseNumbers;
strb.AppendFormat("{0}次{1}\r\n", level.ToString(), NumberStrings);
}
}
}
}
我的代码有问题就是:比如如果输入26的话就会分解成25然后1没法分解,但是小黑同志的代码可以把26分解成21+5,我无论如何看不懂他的代码是如何实现跳过25然后取21的。
请高手指点一下。
把1000——100万之内的任意一个数值分解成如下数值的和:858、300、240、120、90、85、60、30、25、21、17、12、8、7、6、5、4
可以是以上这些数任意一个或几个的组合,要求要尽量少的加数项,比如:3000 分解成858+858+858+300+120+6而不能分解成300+300……+300,更不能分解成30+30+……30
要求:
1、用字符串把数值组合输出
关于这个问题小黑同志已经给出Delphi代码了,但是因为我对Delphi了解不深加上他在算法中用了递归,所以我脑袋一团浆糊,无论如何也搞不懂了。
他的Delphi代码如下:
procedure TForm1.Button1Click(Sender: TObject);
const
cBaseNumbers: array[0..16] of Integer = (858, 300, 240, 120, 90, 85, 60, 30,
25, 21, 17, 12, 8, 7, 6, 5, 4);
var
vMinCount: Integer;
vPath: string;
procedure pScan(
ADest: Integer;
ALevel: Integer;
ACount: Integer;
APath: string
);
var
I: Integer;
begin
if ALevel > High(cBaseNumbers) then Exit;
if ADest = 0 then
begin
if ACount < vMinCount then
begin
vMinCount := ACount;
vPath := APath;
end;
end
else
begin
I := ALevel;
while I <= High(cBaseNumbers) do
begin
if ADest >= cBaseNumbers then
pScan(ADest mod cBaseNumbers, ALevel + 1,
ACount + ADest div cBaseNumbers,
APath + Format('+%d*%d', [ADest div cBaseNumbers,
cBaseNumbers]));
Inc(I);
end;
end;
end;
begin
vMinCount := MaxInt;
vPath := '';
pScan(SpinEdit1.Value, 0, 0, '');
Delete(vPath, 1, 1);
Memo1.Lines.Add(vPath);
end;
下面这个是我用C#写的代码:
class Count
{
public int[] BaseNumbers = new int[] {858,300,240,120,90,85,60,
30,25,21,17,12,8,7,6,5,4};
public string[] NumberStrings = new string[] { "858","300","240","120","90","85","60","30","25","21","17","12","8","7","6","5","4"};
public StringBuilder strb = new StringBuilder("目标数分解为:\r\n\r\n", 64);
public void Scan(int target) {
for (int i = 0; i < BaseNumbers.Length; i++)
{
if (target >= BaseNumbers) {
int level = (int)(target/BaseNumbers);
target = target % BaseNumbers;
strb.AppendFormat("{0}次{1}\r\n", level.ToString(), NumberStrings);
}
}
}
}
我的代码有问题就是:比如如果输入26的话就会分解成25然后1没法分解,但是小黑同志的代码可以把26分解成21+5,我无论如何看不懂他的代码是如何实现跳过25然后取21的。
请高手指点一下。