回 帖 发 新 帖 刷新版面

主题:[原创]求一个数值分解的算法

题目:
    把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的。

请高手指点一下。

回复列表 (共1个回复)

沙发

这不就是缺少一个递归么。你没有值判断的递归,直接一条直线下来,当然是这种结果

我来回复

您尚未登录,请登录后再回复。点此登录或注册