乘积最大(分不够可以再加！)

问题描述:

    今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先
生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活
动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样
一道题目:

   设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种
分法，使得这K+1个部分的乘积能够为最大。

   同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

   有一个数字串: 312，当N=3，K=1时会有以下两种分法：

            1）3*12=36
            2）31*2=62

   这时，符合题目要求的结果是：  31*2=62

   现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

输入：
    程序的输入共有两行:
    第一行共有2个自然数N,K (6<=N<=40，1<=K<=6)
    第二行是一个K度为N的数字串。

输出:
    结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。

样例:

输入
4 2
1231

输出
62

想要完整的源码，分不够可以再加！！

40 个解决方案

#1

这不应该复杂吧，用暴力方法的话，大概这么做吧（假定涉及的乘积都小于int的最大数，否则的话，大概需要自己写大整数类或者使用.NET 3.5里的BigInteger类）：

using System;

class MyPath
{
    static int MaxProduct(int mulOpCount, char[] nums, int start, int length)
    {
if (length <= mulOpCount)
{
throw new ArgumentException("乘法算符数目太多了");
}

if (mulOpCount == 0) //如果乘法算符数目为0，则返回当前字符数组对应的整数值
return ConvertCharArrayToInt(nums,start,length);

int maxProduct = 0;

for (int i = 0; i < length-mulOpCount;i++)
{
int left = ConvertCharArrayToInt(nums,start,i+1);

int right = MaxProduct(mulOpCount-1,nums,start+i+1, length-i-1);

int p = left*right;
if (p > maxProduct)
maxProduct= p;

}

return maxProduct;
    }

    static int ConvertCharArrayToInt(char[] nums, int start, int length)
    {
string s = new string(nums,start, length);
return Convert.ToInt32(s);
    }

    static void Main(string[] args)
    {
if (args.Length < 2)
{
Console.WriteLine("{0} number-string multiplication-count", Environment.GetCommandLineArgs()[0]);
return;
}

char[] numChars = args[0].ToCharArray();
int mulOpCount = Convert.ToInt32(args[1]);

Console.WriteLine("{0}", MaxProduct(mulOpCount,numChars,0,numChars.Length));
    }
}

#2

更正，.NET 3.5 Beta 2中没包括System.Numeric.BigInteger

#3

有意思

#4

好像只有暴力方式。。。。。。

#5

厉害，mark

#6

学习

#7

收藏高手的方法

#8

学习

#9

如果用暴力破解，假设N=40,K=6,则总共有39*38*37*36*35*34=2349088560中分法，做这么多次的大整数乘法再比较，恐怖。。。。。。

我的感觉是分出来的所有的数的位数应尽量一样，不一样的话，留大数，拆小数。
不知道想法对不对。

#10

mark!!@

#11

我仔细想了想，觉得K应该为1是最好的，从中间分开，大家试试看是不.

#12

我觉得还是先用数学分析一下，再写个合适的算法

#13

因为你每拆一个'个位'数出来，所乘的数就少了一位，但是你乘于这个‘个位’数，肯定小于10，这样拆肯定得不到最大的。拆其他位数同理。

#14

N久不见“思归”

#15

恩，不错，
循环，递归，

期待...

#16

所以这个问题有2种情况，例如5位数，99899，是拆成998*99，还是拆成99*899呢，就只对前(n/2)位和后(n/2)位进行判断就可以了,
还有一种情况就是中间0太多的，例如:10001，这种情况，就从最中间的0开始数，如果右边还是0，就继续将*右移，一直移到右边的数不为0。
如果要是100000的话，那怎么算最大值都是0咯。

#17

顶

#18

啥是牛人啊，三个钻石就是牛人

#19

我已经5个三角裤了

#20

确实牛人。
是否可以引入平均值概念
例如 312，N=3,K=1那么(3+1+2)/(K+1)=2,任何小于2的数都不能看分开312里面的1就必须附于其他数上面。

#21

需要用到排列组合，N长度，那么就有N-1个空用来放*号，从这N-1个空中取出K个空来放*，只能循环比较解决吧

#22

發現二樓有三鉆

#23

有BigInt啦

#24

强贴留名

#25

思归还活着！！

#26

顶一下

#27

缺乏智力细胞研究 ....

#28

mark

#29

#30

应该是乘完一段数字后就除以一点否则是装不下的

#31

觉得先做一下数学分析比较好

#32

厉害，我不认识XZ啊

#33

saucer(思归)
好家伙，三个钻石！！

#34

搞竞赛的人都应该做过这道题（显然是2000年的题嘛）。

题目给出两个关键数值N和K对不对？假设F(N,K)就是对字符串前N位插入K个乘号后所能得到的最大值，考虑一下F(N,K)与F(N-1,K)、F(N-1,K-1)的关系？如果你也是搞竞赛的，点到即止。算法题应该到算法版问，你在ASP.NET版问，大家平常都不是研究这个的，你能得到的答案可能就不是那么优化。

#35

钻石恒久远,一个就破产

#36

附例子：

312：当N=3, K=1时，从N=1, K=0开始推导
F(1, 0) = 3
F(2, 0) = 31
F(3, 1) = max(F(1, 0)*12, F(2,0)*2) = max(36, 62) = 62

31245：N=5, K=2，还是从F(1, 0)开始推导
F(1, 0) = 3
F(2, 0) = 31
F(3, 0) = 312
F(2, 1) = 3*1 = 3
F(3, 1) = max(F(1, 0) * 12, F(2, 0) * 2) = max(36, 62) = 62
F(4, 1) = max(F(1, 0) * 124, F(2, 0) * 24, F(3, 0) * 4) = max(372, 744, 1248) = 1248
F(5, 2) = max(F(2, 1) * 245, F(3, 1) * 45, F(4, 1) * 5) = max(735, 2790, 6240) = 6240

因为题目仅需要求最后的值，不需要输出到底是如何插入乘号能得到这个最大值（通常竞赛题都这样），因此这样的计算方法获得最大值就足够了。如果你要追寻哪种插入方式得到了最大值，每次max时你都要把最大值的选择保存下来，最后根据这个选择确定原先进行了乘号插入的地方。

#37

裤衩，接分

#38

动态规划
  给你规划方程吧：
  设A[I，Num]   B[I,Num]   是第一个数字到第I个数字中加Num个乘号所得的最大值
      s[k，I]表示从第k位到第I位的一个数字
  那么
  B[I，Num]=max（A[k，Num-1]*S[k+1，I])
        1+Num-1<=k<=I;
不过细心一点还是比较好写的

#39

我上面的做法是比较简单的，虽然性能不是很好，当然还有其他的问题，譬如

1. 象在代码里提到的，没有使用大整数类，这样局限性很大
2. 没有验证输入数据
3. ConvertCharArrayToInt 应该用字符-'0'的方法来算

至于算法，没仔细研究，也许存在象Maximal Contiguous Subsequent Sum Problem解决方案那样的线性算法也未可知。但如果就竞赛而言，除非以前研究过，一般不大可能想出非常高明的算法的，所以使用暴力算法的居多吧

#40

谢谢大家！！！总算找到比较满意的答案啦！！

#1

#2