最大的最小公倍数
问题描述：正整数n(n<=250),例如n，n可以被分解成几个（或者很多个）正整数的和，求这些正整数的最小公倍数中的最大一个公倍数，并且输出这个最大的最小公倍数，例如n=5时,5=2+3时，最小公倍数k最大，k=2*3=6，又例如n=8时，8=3+5时最小公倍数最大，k=3*5=15，求用C，C++写的代码，最好写一些注释，谢谢！in: out:
2 2
3 3
4 4
5 6
6 6
7 12
8 15
9 20
10 30
11 30
12 60
17 210
18 210
19 420
20 280
21 420
33 4620
45 60060
51 180180
52 180180
53 360360
75 6846840
90 58198140
98 157477320
99 232792560
100 232792560
119 2677114440
150 82990547640
200 24067258815600
220 178097715235440
0
以上是测试数据（没错的）
----------------解决方案--------------------------------------------------------
数据有错误
19 420
20 280
21 420
２０的数据不可能比１９小
因为２０＝１９＋１，最起码=19
----------------解决方案--------------------------------------------------------
/*
本题可用算法；
1.普通回溯法+HASH
DFS到所有数据（时间复杂度为O(N!)），由于数据规模为250，
较小，完全可以先将所有数据算出后交”表“，交表程序复
杂度为O(1) ，可以AC
2.DP（动态规划）
定义2维数组，记录状态 d[k,x] k为数据大小，x为分量（将
原数分的数的个数，既k=k1+k2+...+kx,d[k,x]记录当前最大
可能.
状态转移: d[k,x]=max{最小公倍数(d[k-1,1],d[1,x-1]),
最小公倍数(d[k-1,2],d[1,x-2]),...最小公倍数(d[k-1,x d
iv 2 +1],d[1,x div 2 -1]),最小公倍数(d[k-2,1],d[2,x-1]
),...,最小公倍数(d[k div 2+1,x div 2 +1],d[k div 2-1,x
div 2 -1]),k}
(1) 记忆化搜索，利用以上规划法优化原普通回溯法，时间复
杂度降低为O(N^3)
(2) 正推递推，利用以上规划法重新实现递推算法，时间复杂
度为 O(N^3)
*/
DP的时间复杂度已经允许直接交纯算法,在很短时间内出解
/*由于本人时间问题，仅实现普通DFS，同时给出其它更好算法（DP
)的思想和转移方程，状态，用此思路完全可以实现.*/
/*算法艺术！ 让思维绽放! */
/* BY 卧龙孔明 */
/*时间仓促,提供思想,以下实现程序可能出现小问题,但程序核心算法没有错误*/
#include<stdio.h>
#include<math.h>
#include<conio.h>
/*算法1 普通回溯法（深度优先搜索(DFS))*/
/*
目前信息学竞赛中禁止使用64位长整型变量
因此本程序不使用long long，取而代之使用double(精确17位数)
如果数据规模继续增大，请改为高精度，具体高精度运算程序不提供
*/
double max=0;
int n;
double g(double a,double b)
{
double x=a;
if(a<b)
{
x=b; b=a; a=x;
}
while(fmod(x,b)) x+=a;
return x;
}
int dfs(int left,int c,double now)
{
int i;
if(left>=c)
for(i=c;i<=left;i++) dfs(left-i,i+1,g(now,(double)i));
else
{
if(left!=0) now=g(now,(double)left);
if(now>max) max=now;
return;
}
}
int main(void)
{
int i,j,k;
int flag=0;
int count=0;
scanf("%d",&n);
dfs(n,1,1.0);
printf("%.0lf\n",max);
getch();
return 0;
}
[[it] 本帖最后由 卧龙孔明 于 2008-1-31 08:33 编辑 [/it]]
----------------解决方案--------------------------------------------------------