RUC_JudgeOnline 1004 整数分解问题

整数分解问题

Description

有一个整数n，n可分解成若干个整数之和，问如何分解能使这些数的乘积最大。请编程，输入一个整数n（n<50），将n分解成若干个整数，输出这些数的乘积m，且要保证m是最大的。

Input

共一行，为整数n。

Output

最大的乘积m。

Sample Input

 

10

 

Sample Output

 

36

 

Source

习题6-3

 

问题分析：

对于一个整数，我们首先要知道，分解成怎样的形式才能使乘积最大。得到的结论是分成尽可能多的3，剩下的都分成2，这样可以得到最大的乘积。所以，我们程序的目的就是将输入的数N分成很多个3进行累乘。当N小于等于4时，我们就可以直接乘以N了。这是因为如果是1，2或者3显然它本身是最大的，不能把2分成1和1，或者把3分成1和2.对于4，最好的分解方法显然是2和2.但是2*2就等于4，所以，当N小于等于4的时候，我们就可以不用再分了。

解决方案：

总的来说，有两种解题思路。一个正着退，一个倒着来。也就是一个用递推，一个用递归。现在在这个程序中用递推的效率明显高于递归。详见参考程序。

参考程序（递推）：

 

#include<stdio.h>

int main()
{
	int N;
 	scanf("%d",&N);
 
 	int m=1;                                  //用m表示乘积
 	while(N>4)
 	{
  		m=m+m+m;	//用加法替代乘法
  		N=N-3;
 	}
 	m=m*N;
 	printf("%d\n",m);
 	return 0;
}

 参考程序（递归）：

#include<stdio.h>

int calc(int N);
int main()
{
	int N;
 	scanf("%d",&N);

 	printf("%d\n",calc(N));

 	return 0;
}

int calc(int N)
{
	if(N<=4)
	return N;
	else
	return 3*calc(N-3);
}