首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

大家给个思路,该怎么解决

2012-03-07 
大家给个思路SampleInput302SampleOutput5251+51302275+27302276+26302281+21302301+01302不能穷举的

大家给个思路
Sample   Input
302
Sample   Output
5
251   +   51   =   302
275   +   27   =   302
276   +   26   =   302
281   +   21   =   302
301   +   01   =   302
不能穷举的

[解决办法]
问题是什么?
[解决办法]
有点意思,可能只由穷举了,中间还要用到字符串匹配。
[解决办法]
问题相当于求解方程:(11a+b)10^n+2c=Input。其中都是整数,把abc连起来看,就是Output中较大的数,ac连起来是那个较小的数,b是要去掉的哪一位,n表示去掉哪一位后面一共有多少位,也就是c的位数。假定Input一共有m位,那么n的取值范围是0到m-1。因此我们的思路是:确定n,同时确定c,求出a和b。步骤如下:
1、当Input为奇数时,n=0,c=空(因为它是0位的),也就是说去掉的只能是最后一位,这样11a+b=Input,所以a=Input/11的商,b为余数,如果b=10,也就是说b不是一位,就把这组解舍去,其他情况,就产生一组解。
2、当Input为偶数时,n=0 to m-1,因此我们for(n=0;n <=m-1;n++)。当n=0时,解法和上面1中提到的完全一致。当n> 0时,一般有两组解,c=Input的后n位/2或c=Input的后n位再在最前面加上1然后除以2;11a+b=Input去掉后n位的数,我们把它(和它减1)除以11,商是a,余数是b,然后检查b是不是一位数。
借楼主的例子说明一下:
Input=302
n=0时,c=null,a=302/11=27,b=302%11=5,Output=275;
n=1时,c=2/2=1,a=30/11=2,b=30%11=8,Output=281;
c=12/2=6,a=29/11=2,b=29%11=7,Output=276;
n=2时,c=02/2=01,a=3/11=0,b=3%11=3,Output=301;
c=102/2=51,a=2/11=0,b=2%11=2,Output=251;
这样就得到楼主要求的解。

热点排行