c语言 有一个整数N,N可以分解成若干个整数之和,问如何分解能使这些数的乘积最大
答案:2 悬赏:50
解决时间 2021-03-08 23:11
- 提问者网友:饮鸿
- 2021-03-08 18:50
请编程,由键盘输入一个整数N(N<100),将N分解成若干个整数,输出这些数的乘积,且要保证M是最大的。
最佳答案
- 二级知识专家网友:万千宠爱
- 2021-03-08 19:07
最优化问题,尽量都分成3,不足部分就分成2。
对于 n < 4,可以验证其分解成几个正整数的和的乘积是小于 n 的。
对于 n >= 4, 能证明其能分解成几个数的和使得乘积不小于 n。
如果分解成 1 和 n - 1,那么对乘积是没有帮助的,因此,假设 n
分解成 a 和 n - a,2 <= a <= n - 2,那么
a * (n - a) - n
= (a - 1) * n - a * a + a - a
= (a - 1) * (n - a) - a
>= (a - 1) * 2 - a
= a - 2
>= 0
如果 a, n - a 仍然 >= 4,那么继续分解,直至 a, n - a < 4。因为每次分解都能使乘积
增加,所以最优解必是最终分解结果,也即分解出的数全是 2 或 3 。
(1)
假设 n 是偶数,且分解成 a 个 2 和 b 个 3,即 n = 2 * a + 3 * b,则乘积为 2a * 3b。
注意到 23 < 32 且 2 * 3 = 3 * 2 = 6,所以每 3 个 2 换成 2 个 3 会使乘积更大,因此,
最优方案是分解成 n/6*2 个 3 和 n%6/2 个 2,乘积为 3n/6*2 * 2n%6/2。
(2)
假设 n 是奇数,则一定需要分出一个 3,然后 n - 3 就是偶数。因此最优方案是分解出
(n-3)/6*2+1 个 3 和 (n-3)%6/2 个 2,乘积为 3(n - 3)/6*2+1 * 2(n-3)%6/2。
对于 n < 4,可以验证其分解成几个正整数的和的乘积是小于 n 的。
对于 n >= 4, 能证明其能分解成几个数的和使得乘积不小于 n。
如果分解成 1 和 n - 1,那么对乘积是没有帮助的,因此,假设 n
分解成 a 和 n - a,2 <= a <= n - 2,那么
a * (n - a) - n
= (a - 1) * n - a * a + a - a
= (a - 1) * (n - a) - a
>= (a - 1) * 2 - a
= a - 2
>= 0
如果 a, n - a 仍然 >= 4,那么继续分解,直至 a, n - a < 4。因为每次分解都能使乘积
增加,所以最优解必是最终分解结果,也即分解出的数全是 2 或 3 。
(1)
假设 n 是偶数,且分解成 a 个 2 和 b 个 3,即 n = 2 * a + 3 * b,则乘积为 2a * 3b。
注意到 23 < 32 且 2 * 3 = 3 * 2 = 6,所以每 3 个 2 换成 2 个 3 会使乘积更大,因此,
最优方案是分解成 n/6*2 个 3 和 n%6/2 个 2,乘积为 3n/6*2 * 2n%6/2。
(2)
假设 n 是奇数,则一定需要分出一个 3,然后 n - 3 就是偶数。因此最优方案是分解出
(n-3)/6*2+1 个 3 和 (n-3)%6/2 个 2,乘积为 3(n - 3)/6*2+1 * 2(n-3)%6/2。
全部回答
- 1楼网友:强势废物
- 2021-03-08 19:23
我不写完整程序,提一下思路: 我们要编写一个函数,这个函数把一个数分为两个数之和,并且这两个数的乘积最大,这样的函数是不是很好编写,代码如下: 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 $ -----------------
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯