[讨论]一个数分解的乘积问题。 - 编程论坛

#2

tcnf20042007-10-15 22:48

我和朋友想了一下，发现所有大于3的正整数，可以分解为：3*3*3……*[2（2个2或者1个2），3]，这样分解组成的乘积最大，也就是保持最后一个数是2或者3，其他要都是3才可以乘积最大。这样编程序就好编了，还有其他方法也有同样的结论么？

[此贴子已经被作者于2007-10-15 22:56:18编辑过]

#3

tcnf20042007-10-15 22:52

4=2*2
5=3*2
6=3*3
7=3*2*2
8=3*3*2
9=3^3
10=3*3*2*2
11=3^3*2
12=3^4
13=3^3*2*2
…………
24=3^8
…………

[此贴子已经被作者于2007-10-15 22:54:56编辑过]

#4

HJin2007-10-16 00:27

consider writing N as a sum of 2's and 3's.

You can mathematically prove that by using 2 and 3's, you get the maximum product.

#5

aipb20072007-10-16 12:35

直接DP，之前有人问过并有答案，在这版里

#6

nuciewth2007-10-16 15:08

1.一切大于1的数都可以用2,3的和来分解.

2.假设a=b+c,其中得到的b*c最大
同时,b,c也可以这样分解.(递归)

现在来证明用2,3分解得到的数最大
从4 (从4开始都是这样)分解当然是2,2,所有加数为4的都应该分解为2,2才可以得到最大.

反证:
假设任意一个数分解成若干数的和能得到最大的乘积(其中这些因子不包含3,2)
则这些加数一定可以分解成2,3的组合(根据第一条),再根据第二条,既然可以分解成2,3使得得到的乘积是最大的
那就证明了因子不是2,3是错误的.
所以每个数要分解成2,3的组合才能得到最大.

具体怎么样的组合才可以得到最大那就是贪心.
仅当被分解的数不小于2,就用3分解.直到0.

#7

nuciewth2007-10-16 15:13

k=num/3;
t=1;
if(num%3==1)
{
k--;
t++;
}
else if(num%3==0)
{
t--;
}

得到k个3 t个2

#8

HJin2007-10-16 20:33

no need of recursion or dp:

you only need to consider three cases:

n%3 == 0, 1, 2 // these determine how many 3's and how many 2's

then you can write a formula for the max-product.