整数拆分有关问题

整数拆分问题
给一个数n，你可以将这个数拆成任意个整数，现在我们想知道在所有的拆分方式中 拆出来的所有的数的积 的最大值。
如 n = 6, 可以拆成 
3 * 3 = 9
2 * 4 = 8
2 * 2 * 2 = 8
1 * 1 * 4 = 4
1 * 1 * 2 * 2 = 4
...
最大值为9


怎么进行拆分啊？



[解决办法]
我的基本结论是(没有证明),对于数n,如果可拆成几个相等的数，当每个数为3时，其乘积最大。

1个基本的事实，在边长相等的情况下，正方形体积最大。故拆分的几个数应该尽量大小相同。
例如：
6=2×3，可拆成几个2或者几个3，拆成几个3其乘积最大。
60是2，3，4，5，6的公倍数，可拆成30个2，或者20个3，15个4，或者12个5，或者10个6.计算可知，拆成20个3，其乘积最大。
容易看出，若1个数是n=4K， 则这个数可以拆成 2K个2，或者K个4，其乘积总是相同的，因为2^(2k)=4^k,
推测，若一个数是m-1,m,m+1的倍数，且拆分为K个m时，其乘积最大，则m为峰值，m-1和m+1都没有m好。
因为 2^2k=4^k,其峰值应该是3。

请数学好的同学来证明。

 

[解决办法]

探讨

我的基本结论是(没有证明),对于数n,如果可拆成几个相等的数，当每个数为3时，其乘积最大。

1个基本的事实，在边长相等的情况下，正方形体积最大。故拆分的几个数应该尽量大小相同。
例如：
6=2×3，可拆成几个2或者几个3，拆成几个3其乘积最大。
60是2，3，4，5，6的公倍数，可拆成30个2，或者20个3，15个4，或者12个5，或者10个6.计算可知，拆成20个3……

[解决办法]
高中都学过的函数可以证明，设 其中一个数为x，总和为a，
则，拆分的另一个数为a-x，则所得乘积y=x(a-x)
讨论函数的增减性，画图，是个倒着的抛物线，交x轴于0,和a，则最高点为a/2
涉及到取整数问题，选取最接近a/2的数
[解决办法]
顺便写了一个，见笑了

C/C++ code

/**给一个数n，你可以将这个数拆成任意个整数，现在我们想知道在所有的拆分方式中 拆出来的所有的数的积 的最大值。如 n = 6, 可以拆成  3 * 3 = 92 * 4 = 82 * 2 * 2 = 81 * 1 * 4 = 41 * 1 * 2 * 2 = 4...最大值为9 */#include <iostream>using namespace std;#define M 5/*要划分的整数*/#define N 11/*要划分成的整数*/static int a[M] = {1,2,5,7,9};/*根据上面的给值得到划分后最大的乘积*/int get_max_product(){    int max_num = 0;    int dp[N + 1] = {0};    for (int i = 0;i < N + 1;i++)    {        dp[i] = 1;    }    for (int i = 0;i < M;i++)    {        for (int j = a[i];j < N + 1;j++)        {            dp[j] = dp[j - a[i]] * a[i];        }        if (max_num < dp[N])        {            max_num = dp[N];        }    }    return max_num;}int main(){    cout << get_max_product() << endl;    /**     * 2 * 2 * 2 * 2 * 2 * 1 = 32     * 5 * 5 * 1 = 25     * 7 * 2 * 2 = 28     * 得证，最大为32     */    return 0;}
[解决办法]
算法的优化版本，不采用动态规划空间
C/C++ code
int get_max_product_2(){    int max_num = 0;    for (int i = 0;i < M;i++)    {        int temp_n = N;        int temp_num = 1;        for (int j = i;j >= 0;j--)        {            temp_num *= int(pow(a[j],temp_n / a[j] * 1.0));            temp_n %= a[j];        }        if (temp_num > max_num)        {            max_num = temp_num;        }    }    return max_num;} 

 

查看更多 下一篇