首页
社区
课程
招聘
[求助]求一个数值分解的算法
发表于: 2007-12-5 18:47 5209

[求助]求一个数值分解的算法

2007-12-5 18:47
5209
题目:
    把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的。

请高手指点一下。

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 0
支持
分享
最新回复 (11)
雪    币: 486
活跃值: (13)
能力值: ( LV9,RANK:430 )
在线值:
发帖
回帖
粉丝
2
strb.AppendFormat("{0}次{1}\r\n", level.ToString(), NumberStrings);
看不懂这句是什么意思。
不知道楼主想要的是C#,还是其它的呢?小弟不太懂C#。
2007-12-5 18:55
0
雪    币: 207
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
谢谢楼上的

可以是C/C#、Java、Delphi,但请把算法写的清晰一些不要使用递归,最好能加上注释
2007-12-5 19:32
0
雪    币: 207
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
等了这么久,咋就没人帮帮我呢
2007-12-6 09:23
0
雪    币: 207
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
大牛们救救小弟啊,真的都不屑解答么
2007-12-6 14:19
0
雪    币: 1852
活跃值: (504)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
6
动态规划,时间复杂度O(n),不需要用递归。
下面是具体实现,具体思路懒的写了,要睡觉了。
自己先研究下,如果看不懂再说。

#include <iostream.h>

#define MAX_VALUE 1000000
// value[i]的值表示到达i值的最大步长
unsigned short value[MAX_VALUE+5] = {0} ;
// array[i]的值表示表示步长
unsigned short array[17] = { 858,300,240,120,90,85,60,30,25,21,17,12,8,7,6,5,4 } ;

int main()
{
	int i, j ;  
	for ( i = 0; i < 17; i++ )
		value[array[i]] = array[i] ;

	for ( i = 0; i < MAX_VALUE; i++ )
	{
		if ( value[i] == 0 )
			continue ;

		for ( j = 0; j < 17; j++ )
		{
			if ( i + array[j] < MAX_VALUE && value[i+array[j]] == 0 )
				value[i+array[j]] = array[j] ;
		}
	}
	
	// 下面是输出部分
	int target = 0;
	while ( cin >> target )
	{
		if ( target <= 4 || target >= MAX_VALUE )
			cout << "input error!" << endl ;
		else if ( value[target] == 0 )
			cout << "no slove!" << endl ;
		else
		{
			cout << "[ " ;
			while ( target )
			{
				cout << value[target] << ' ' ;
				target -= value[target] ;
			}
			cout << "]" << endl ;
		}
	}
	
	return 0;
}

/*
//测试示例
3000
[ 858 858 858 300 120 6 ]
432
[ 300 120 12 ]
654
[ 300 300 30 17 7 ]
54335
[ 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 85
8 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 85
8 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 858 85
8 858 858 858 240 30 7 4 ]
*/
2007-12-7 01:29
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
你想获得一个解还是获得所有解呢?
2007-12-7 08:06
0
雪    币: 207
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
版主的代码我还是很难理解,而且迭代的次数非常之多,感觉比较影响效率
我终于想到了比较简单而且思路清晰的函数实现,只需在原来的基础上加上一条判断即可,真是恍然大悟啊
    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 && (target%BaseNumbers[i]>4 || target%BaseNumbers[i]==0)) {
                    int level = (int)(target/BaseNumbers);
                    target = target % BaseNumbers;
                    strb.AppendFormat("{0}次{1}\r\n", level.ToString(), NumberStrings);

                }
            }
        }
    }

非常感谢北极星版主的答复,我在琢磨琢磨,希望可以理解版主代码的思路
2007-12-7 10:26
0
雪    币: 1852
活跃值: (504)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
9
针对这个数组858,300,240,120,90,85,60,30,25,21,17,12,8,7,6,5,4
默认情况已经保证了每个值都可以被拆分,因而你的方法也只有在这种情况下有效
而我当前考虑的时候就认为不一顶每个值都能被拆分,因而我写的算法具有通用性

把题目稍微修改下:858, 329, 120, 32, 10, 6
2007-12-7 23:21
0
雪    币: 207
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
10
我数学不好,对于版主您的算法理解起来实在困难。如果可以的话,可否略做一些注释帮助我理解一下

主要是下面这句,实在不知道啥思路

      if ( i + array[j] < MAX_VALUE && value[i+array[j]] == 0 )
        value[i+array[j]] = array[j] ;
2007-12-8 00:05
0
雪    币: 1852
活跃值: (504)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
11
思路是当value[i]的值不为0时,表示i可以被拆分
如果i可以被拆分,那么i+4,i+5……i+858这些数也都是可以被拆分的。
此时就设置value[i+4]=4,value[i+5]=5……value[i+858]=858,
value[i]的值表示拆分中的最大数据
如果现在到了i+854,它也可以通过加4到达i+858,
然而此时的i+858已经有效,因而不更新array[i+858]的数据
上传的附件:
2007-12-8 19:15
0
雪    币: 207
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
理解了,谢谢版主
2007-12-11 08:46
0
游客
登录 | 注册 方可回帖
返回
//