作者：Hongquan_Yang | 来源：互联网 | 2023-05-19 05:01
1．编程实现在一个9位数的正整数n中插入4个乘号，使分得的5个整数的乘积最大；2．输入n3．输出被分得的5个整数、得到的最大乘积4．例如：输入734019862
1． 编程实现在一个9位数的正整数n中插入4个乘号，使分得的5个整数的乘积最大；
2． 输入 n
3． 输出 被分得的5个整数、得到的最大乘积
4． 例如：输入 734019862
输出 73*401*9*8*62=130674672
算法上怎么实现，或者给点思路吧，谢谢！
22 个解决方案
如果只是9位数，如果只是插入4个乘号，其实复杂度不是很高的
8个位置上插入4个乘号，组合数C4/8 = 70
计算70次 ， 然后取最大的
穷举效率低是低了，不过是最简单的实现
首先将9位数的每位数组放入一个数组
然后根据乘号的不同位置分别计算
貌似是4层的循环……
分解n为9个数字存入数组的第0--第8个元素中
最大乘积设为max=0
五个整数全设为0
第一个乘号的位置p1在第1--第5元素前(循环)
｛p1前的元素连乘拼合第一个整数
第二个乘号的位置p2在p1+1--第6元素前（循环）
｛p2前的元素拼合为第二个整数
第三个乘号的位置p3在p2+1--第7元素前(循环)
｛p3前的元素拼合为第三个整数
第四个乘号的位置p4在p3+1--第8元素前(循环)
｛p4前的元素拼合为第四个整数
p4前的元素拼合为第五个整数
五个整数的乘积记为product
若product>max
{max<=product
并记录五个整数
｝
｝
｝
｝
｝
输出max和记录的五个整数
从八个位置里选四个，然后分别计算取最大的，这个还不简单？这是最笨的方法，也是唯一的方法，这种问题除了遍历没有其他的方法！
简单啊，9位数分成5份，将9位数依大至小排列，取前5位数为首进行分割即可。
就算不是插入，你的算法显然也不对，如果9位数中有一个0，那么你的算法结果就为0，显然0不是最大的！
就算没有0，如果是9个1，你的算法结果为11111*1*1*1*1显然小于11*11*11*11*1，也是不对的。
如果没有0也没有1，那么22222*2*2*2*2<22*22*22*22*2,也是不对的
只拿原题目中的数据做测试。
/*******************************************
1． 编程实现在一个9位数的正整数n中插入4个乘号，使分得的5个整数的乘积最大；
2． 输入 n
3． 输出 被分得的5个整数、得到的最大乘积
4． 例如：输入 734019862
输出 73*401*9*8*62=130674672
**********************************************/
#include
#include
int getInteger( int a[], int start, int last)
{
int k;
int product=a[start];
for( k=start+1; k product=product*10+a[k];
return product;
}
int main(int argc, char *argv[])
{
int a[9]={ 7, 3, 4, 0, 1, 9, 8, 6, 2 };//原题目数据
int b[5];
int product=1;
int max=0;
int maxb[5];
int p1,p2,p3,p4;
int k;
for(p1=1; p1<6; p1++)
{
b[0]= getInteger(a, 0, p1);
for(p2=p1+1; p2<7; p2++)
{
b[1]= getInteger(a, p1, p2);
for( p3=p2+1; p3<8; p3++ )
{
b[2]= getInteger(a, p2, p3);
for(p4=p3+1; p4<9; p4++)
{
b[3]=getInteger(a, p3, p4);
product=b[4]=getInteger(a, p4, 9);
for(k=0; k<4; k++)
product*=b[k];
if( product>max )
{
max=product;
for( k=0;k<5; k++ )
maxb[k]=b[k];
}
}
}
}
}
printf("\n Max is %d = %d",max,maxb[0]) ;
for( k=1; k<5; k++ )
printf(" * %d",maxb[k]);
printf("\n");
system("PAUSE");
return 0;
}
找出9个数中最大的5个数，作为5个数的首位将九位数截断
那个只是首位估算，首位相同的话，那就只能在估算次位了，那就比较麻烦了，但应该比穷举好一点吧
正如楼上诸位所述，穷举次数只有70次（8!/4!/(8-4)!）,代价不大了。也许设计一个生成nextCombination（）函数能使程序结构更好些。
457869032 => 9 8 7 6 5 4 3 2 0 => 45 *7 *8 *6 *9032 = 136563840
同数加权问题，3,2,1小数问题，按数论的规律，合并数比乘积数要大，111111111=> 11111*1*1*1*1 << 11*11*11*111；即逢0、1、2、3尽可能的合并
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号