有一个整数N，N可以分解成若干个整数之和，问如何分解能使这些数的乘积最大。(c语言)
发布网友
发布时间：2022-04-14 15:38
共1个回答
热心网友
时间：2022-04-14 17:07
我们要编写一个函数，这个函数把一个数分为两个数之和，并且这两个数的乘积最大，这样的函数是不是很好编写，代码如下：
void f1(int a, int *x,int *y){
*x=a/2;
*y=a-*x;
}
知道为什么这样分吗，原理很简单：两个数都最大的时候，乘积才最大。也就是各取一半，如果a是奇数就让y多1。
要完成把N分为多个数，使其乘积最大，我们就先分为两个数，然后分别对这两个数进行各自进行拆分（递归调用），直到分开的两个数乘积比分前小，那就取消这次拆分。
基于以上说明，我们对f1函数进行修改，增加递归调用部分：
void f1(int n){
int x,y;
x=n/2;
y=n-x;
if (n>=x*y) printf("%d ",n);
else {f1(x);f1(y);}
}
添加计算乘积m的代码，以及主程序，完成的如下：
－－－－－－－－－－－－－－－－－
int m;
void f1(int n){
int x,y;
x=n/2;
y=n-x;
if (n>=x*y) {printf("%d ",n);m*=n;}
else {f1(x);f1(y);}
}
main(){
int n;
m=1;
scanf("%d",&n);
f1(n);
printf("\n%d",m);
}
－－－－－－－－－－－－－－－－－
程序在SCO UNIX上运行通过，结果如下：
－－－－－－－－－－－－－－－－－
$ cc a.c
$ a.out
9
4 2 3
24
$ a.out
10
2 3 2 3
36
$ a.out
12
3 3 3 3
81
$
－－－－－－－－－－－－－－－－－
