问题:给定一个自然数N,求n1,n2……nx,使N = n1 + n2 + …… + nx,并使n1*n2……*nx最大。
解法:将N分解为若干个2和3,且2的个数最多为两个。
具体来说:若N = 3*k,则分解为k个3;
若N = 3*k + 1,则分解为(k - 1)个3和两个2;
若N = 3*k + 2,则分解为k个3和一个2。
证明:
不妨设n1<=n2<=……<=nx,且此时n1*n2……*nx最大
(1).若n1=1,则n1*n2……*nx = n2*n3……*nx < (n1 + n2)*n3*……*nx,这与n1*n2……*nx最大矛盾,故n1>=2,同理,n1、n2……nx都满足大于等于2。
(2)若n1>4,则n1 = (n1 - 2) + 2,此时(n1 - 2)*2 > n1,n1*n2……*nx < (n1 -2)*2*n2*……*nx,这又与n1*n2……*nx最大矛盾,故n1<=4,同理n1、n2……nx都满足小于等于4。
若n1 = 4,则n1 = 2 + 2,其积不变,故可认为n1、n2……nx不含4。
综上所述,2<=n1,n2,n3……nx<=3。
若2的个数超过两个,即至少有3个2,可取其中3个2换成2个3,由于3*3 > 2*2*2,因此超过两个2的分解均不为最大,即最大积分解中最多有两个2.
证毕。
参考资料:《自然数的一种有趣的“最大积” 分解》,作者:马卫民
分享到:
相关推荐
问题描述:设n是一个正整数,将n分解为若干互不相同的自然数之和,且使这些自然数的乘积最大。 本讲义提供该问题的正确算法的自然语言描述及其严格证明。
(1)现在将n分解为若干个互不相同的自然数之和,且使这些自然数的乘积最大。 (2)现在将n分解为若干个自然数之和,且使这些自然数的乘积最大。 编程任务:对于给定的正整数n,编程计算问题(1)和(2)的最优分解...
自然数分解.c
C语言程序设计-求一个n位自然数的各位数字的积;(n 是小于10的自然数).c
java代码-例子3-6 求前20个自然数的积。
题目1:设 n 为一自然数,n 可以分解成若干个不同的自然数的和,这样的分法有很多种,比如 n=10, 10 可以分解为:10=5+4+1; 10=5+3+2; 10+9+1; 10=8+2; 10=7+3; 10=6+4;10=7+2+1; 10=6+3+1;…。在所有这些分法中,各...
设n是一个正整数,现在要将n分解为若干个互不相同的自然数的和,且使这些数的乘积最大。
设n是一个正整数。现在要求将n分解为若干互不相同的自然数的和,且使这些自然数的乘积最大。
C语言编写。求自然数的前n项和与积。使用递归的方法编写。
1.设一背包可容物品的最大质量为m,现有n件物品,质量为(w1, w1,…,wn),wi均为整数,从n件物品中挑选若干件,使放入背包的质量之和正好为m。 2.对于任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和:...
用C#编程求两个自然数的最大公约数和最小公倍数
编写一个程序。要求将一个自然数拆分成任意个自然数相加,要求这几个数的乘积是最大的 自然数n拆分成m个自然数,要求这几个数的乘积是最大的,必为n/m及其临近数.
最大公约数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。
求100之内自然数中最大的能被17整除的数.doc
C语言程序设计-计算出k以内最大的10个能被13或17整除的自然数之和;(k〈3000);
c++ 实现一个自然数表示成几个自然数的和,输出所有自然数和的表示方式
一个自然数拆分成N个自然数之和的所有情况
可以生成任意两间所有的素数,同时也可以用于自动计算非素数的所有除法计算。
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如,第6 页用数字6 表示,而不是06 或006 等。数字计数问题要求对给定书的总页码n,计算出书的全部...
编写一个方法,求两个自然数的最大公约数和最小公倍数 c#