求助：用C++编程，且要求程序里要有类 - 编程论坛

#2

liudw22012-06-23 09:50

不要老想别人会帮你将代码写出来，别人也是要学习或者工作的，下面将思路给出来，自己好好想想。
要想乘机最大，乘号后面的数字就要最大。
添加n个*的步骤以6571792为例:
先添第一个，找到最大的数字--9，在前边添上*，变成65717*92了

然后添第二个，找到第二大的数字--7有两个，怎么办？就要这样看了：
（从做到右）第五个7，后面就是*了，所以这个7可以看作是7.0,（从做到右）而第三个7后面有17，然后才是*，所以这个7相当于7.17,因为7.17> 7所以要在第三个7前加

以后就类推了。

#3

pangding2012-06-23 21:33

回复 2楼 liudw2

没看懂第二个，比如是 9999，只加一个乘号。
是不是按的说法应该在第一个9后面分，因为后面的相当于 9.99。
但其实 9 * 999 = 8991 < 99 * 99 = 9801。

#4

pangding2012-06-23 22:08

不会耶，我在 c 那边发帖问了。应该有人会答的，楼主可以去关注一下：
https://bbs.bccn.net/thread-372126-1-1.html

#5

zhuanjia02012-06-23 23:05

我想到一个解决办法，你可以参考下。
先将数字串放到整型数组里，然后对数组进行排序，再取最大数，最后再乘以剩下的有序数列，例如9*954321

#6

pangding2012-06-23 23:23

回复 5楼 zhuanjia0

肯定不能排序呀。数的顺序必须还是原来的顺序。

#7

duoaizhu2012-06-24 01:16

要用动态规划做。
问题中只有乘号插入的位置是变化的，取数字串中的任意一段（i到j）来考虑，若能求出在其中插入K-1个乘号的最大乘积，则只需穷举第K个乘号的插入位置t（t从初始的i+K-1开始插入，最多插入到j-1后）。该乘号把数字串分成了两段，前半段包含K-1个乘号（其最大值已经算出），将它的值与后半段的值相乘得到第K个乘号在位置t时的最大乘积。选出t在各个位置时得到的最大乘积即为问题的解。
    依此类推，把K-1的问题归结为K-2的情况，……，直到求在任意一段中插入1个乘号的最大乘积时，需预先算出在任意一段中插入0个乘号时的最大乘积。而此时的值是已知的（即为该段的数值）。假设DP[i,j,K]表示在长为N的数字串中，从第i个数字到第j个数字之间插入K个乘号的最大乘积，动态转移方程如下：
DP[i,j,k] = MAX {DP[i,t,0] * DP[t,j,k-1] | i<t<j}

#8

pangding2012-06-24 10:51

c 那边最先讨论出的方法也是动态规划，那边给的描述比楼主的还稍微简洁一点，不过思想是一样的。这肯定是一个可行的算法。

基于 2楼的提法（虽然是错的）。确实也有人在考虑类似的贪心算法。不过这种思想，还有很多基础问题没有解决。而且也可能本身就不对。楼主如果着急实现，就用动太规划做就行了。

#9

jiantiewen2012-06-30 02:34

程序就是用来为人们做那些重复繁琐数量又很多的计算。这样才是最简单直接又正确的方法。