正整数n的加法组合的最大乘积的超快算法

http://www.diybl.com/course/3_program/c++/cppjs/2008912/142137.html
题目：
                          
                          
给定一个正整数n，则在n所有的分解式中，求因子乘积最大的一个分解及此乘积。
n=5时，有如下分解式：
5=5
5=4+1
5=3+2
5=3+1+1
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1 
在这些分解式中，3*2=6最大，这就是所要求的结果。 
若n = 12，最大为3*3*3*3 = 81。 



解法：

这一题冒失需要穷尽所有的分解式，其实不然，通过分析数据可得出如下假设：

对任意一个正整数x>3，有i=x/3,j=x%3, 设S为分解式乘积最大的数
当 j=0 时  s=3的i次方
当 j=1 时  s=3的(i-1)次方*4
当 j=2 时  s=3的i次方*2


证明：
首先我们证明将x分为3和2的组合得到的s最大

1）首先证明当3<x<10时满足
x=4  2*2=4
x=5  3*2=6
x=6  3*3=9
x=7  3*2*2=12
x=8  3*3*2=18
x=9  3*3*3=27
x=10 3*3*2*2=36

2）
假设x>10，且x=a[0]+...a[k]时s最大，且a[i]不等于2和3

若a[i]>10,假设a[i]=10*l+m (m<10),明显可知 若将a[i]分解为 l个10相加再加上m 得到的乘积为(10的l次方*m)不小于 a[i]。所有a[]中不可能存在大于10的数
若0<a[i]<10 由（1）可知 将a[i]分解为 2,3的组合得到的s'>=s

由此可以证明 将整数x 分解为2,3的组合 得到的s最大


又因为
3+3=2+2=2
3*3=9 > 2*2*2=8
所有若出现3个2就应该转换为两个3


代码如下：

public static long calculate(long value) {
		long result = -1;
		if (value == 1 || value == 0)
			result = 0;
		else if (value == 2)
			result = 1;
		else if (value >= 3) {
			long i = value / 3;
			long j = value % 3;

			switch ((int)j) {
			case 0:
				result =  (long) Math.pow(3, i);
				break;
			case 1:
				result =  (long) (Math.pow(3, i - 1) * 4);
				break;
			case 2:
				result =  (long) (Math.pow(3, i) * 2);
			}
		}
		return result;
	}

运行结果：

n=1,result=0

n=2,result=1

n=3,result=3

n=4,result=4

n=5,result=6

n=6,result=9

n=7,result=12

n=8,result=18

n=9,result=27

n=10,result=36

n=11,result=54

n=12,result=81

n=13,result=108

n=14,result=162

n=15,result=243

n=16,result=324

n=17,result=486

n=18,result=729

n=19,result=972

n=20,result=1458

n=21,result=2187

n=22,result=2916

n=23,result=4374

n=24,result=6561

n=25,result=8748

n=26,result=13122

n=27,result=19683

n=28,result=26244

n=29,result=39366

n=30,result=59049

n=31,result=78732

n=32,result=118098

n=33,result=177147

n=34,result=236196

n=35,result=354294

n=36,result=531441

n=37,result=708588

n=38,result=1062882

n=39,result=1594323

n=40,result=2125764

n=41,result=3188646

n=42,result=4782969

n=43,result=6377292

n=44,result=9565938

n=45,result=14348907

n=46,result=19131876

n=47,result=28697814

n=48,result=43046721

n=49,result=57395628

n=50,result=86093442

n=51,result=129140163

n=52,result=172186884

n=53,result=258280326

n=54,result=387420489

n=55,result=516560652

n=56,result=774840978

n=57,result=1162261467

n=58,result=1549681956

n=59,result=2324522934

n=60,result=3486784401

n=61,result=4649045868

n=62,result=6973568802

n=63,result=10460353203

n=64,result=13947137604

n=65,result=20920706406

n=66,result=31381059609

n=67,result=41841412812

n=68,result=62762119218

n=69,result=94143178827

n=70,result=125524238436

n=71,result=188286357654

n=72,result=282429536481

n=73,result=376572715308

n=74,result=564859072962

n=75,result=847288609443

n=76,result=1129718145924

n=77,result=1694577218886

n=78,result=2541865828329

n=79,result=3389154437772