1.问题描述
把2010分解为若干个互不相同的正整数之和,使这些互不相同的正整数之积最大。
2.设计要点
进行一般化处理,把指定正整数n分解为若干个互不相同的正整数之和,使这些互不相同的正整数之积最大。
设使积最大的化零分解中,最小零数为c,最大零数为d。
⑴c>1。若c=1,去掉零数1,把1加至最大零数,显然积会增大。
⑵零数按由小到大排列,从c到d的零数序列中,中间的空数(不在零数序列中的数)不能多于1个。
设序列中有两个空数x、y,满足a(i)<x<y<a(j),其中a(i)、a(j)为零数序列中的项(i<j),x=a(i)+1,y=a(j)-1。因a(i)+a(j)=x+y,而
a(j)>a(i)+1 => x*y = (a(i)+1)*(a(j)-1) > a(i)*a(j)
即把a(i)、a(j)两个零数分别换成x、y后,和不变而积增加,与所设各人最大矛盾。
⑶c<4,即c只能取2、3。
若c=4,此时若5在序列中,把5化为2+3,积增加;若5不在序列中而6在序列中,把4、6化为2、3、5,显然和不变而积增加;若5、6都不在序列中,与上述⑵矛盾。
若c>4,把c化为2与c-2,显然2(c-2)>c,积增加。
因此,把指定的n转化为以2或3开始的连续的或至多一个空数的正整数序列,相应的积达最大。
3.代码实现
#include "stdafx.h" #include <math.h> // 积最大的整数分解程序设计 int main(void) { int a, c, d, h, k, n, s; double t; printf("把正整数n分解为若干个互不相同的正数数之和,使积最大。/n"); printf("请输入正整数n:"); scanf("%d", &n); s = 0; h = 0; a = 1; while (s <= n) { // 此时s-n可能为1,2,...,a a++; s += a; } if (s - n == a) { // n分解为2至a-1的连续序列 c = 2; d = a - 1; } else if (s - n == 2) { // n分解为3至a的连续序列 c = 3; d = a; } else if (s - n == 1) { // n分解为3至a+1(不含a) c = 3; d = a + 1; h = a; } else { // n分解为2至a(不含s-n) c = 2; d = a; h = s - n; } printf("%d分解为:%d--%d", n, c, d); if (h > 0) printf("(不包含其中的数%d)", h); printf("/n其积最大为:"); t = 1; for (k = c; k <= d; k++) t *= k; if (h > 0) t /= h; printf("%.0f/n", t); return 0; }