定义：
数组的跨度：如一个数组中最小的那个数是x。则这个数组的跨度L=n-x+1，注意n并非这个数组中最大的那个数，而是所有数组中最大的数。
令tl为跨度和，定义加速比：s=(n+1)*n/2 /tl
对于我的应用,加速比是最重要的一个指标，加速比越大越好，加速比相同的情况下，拆出来的数组的越小越好。
三种算法实验结果；
N
算法
数组个数
加速比
100
Lbc 算法一
6
16.503268
Lbc 算法二
5
16.237942
Gxq 改进算法
6
11.85
1024
Lbc 算法一
104
10.555746
Lbc 算法二
72
11.848908
Gxq 改进算法
86
8.362281
综上所述，算法2得到的结果是目前最好的。
老兄的评判标准是第一优先级为加速比越大越好，第二优先级才是分组组数越少越好。（怎不早说啊？:lol ）
就第一点来说，加速比实则仅与分组后各数组的最小数之和相关，
所以应尽量将小数字相对集中。
感觉 Lbc 算法二已经比较优化了，
但不排除可以将结果人工局部调整，以提高进一步加速比的可能。
言之有理，仔细看了下算法2的运行结果，应该可以进一步调整/优化。不过人工调整比较麻烦，目前正考虑如何调整算法。等新的算法出来后，我将给出代码和运行结果。
想了好久，一直没有找到令自己满意的算法，目前总算找到一个比较满意的，算法复杂度也较低。但还没有动手写程序，当然采用这个算法的程序也是最复杂的。
这个问题题确实很复杂，现在的方案都是找到一个相对好的解，要找到最优解或者更优解确实很难。
仍在思考中......
这类问题找到最优解本身就有很大难度，好比成绩从98提到99一样。
一般出于应用，优化解基本可以达到目的，最优解可再提高的程度比较有限。
不过，对你的新算法还是非常期待的。。。
设要将1到n这n个数分组.
将n!写成素数相乘的形式, n!=p_{1}^{c_{1}}*...p_{k}^{c_{k}}。
对p_{1},p_{2},...,p_{k}取以2为底的对数.
得到一个序列LOG[]:
log_{2}{p_{1}},...,log_{2}{p_{1}},log_{2}{p_{2}},...,log_{2}{p_{2}},...,log_{2}{p_{k}}.
对LOG[]中的数从大往小取数,放进大小为32的背包.对已经放东西的背包,维持这些背包按剩余空间的大小降序排列.
假设当前处理到LOG[ i ].
i)、如果已经放东西的背包序列中的第一个包的剩余空间大于LOG[ i ],则把LOG[ i ]放入,并且按剩余空间的大小,调整已经有东西的背包的顺序.
ii)、如果不是,则把LOG[ i ]放入新的背包,并且按剩余空间的大小,调整已经有东西的背包的顺序.
media2005你测试下你的想法吧
这个题目他们除了两个
还没别人参与过呢
27# 的做法能够保证每个数组的最小公倍数尽可能大，却不能保证数组尽可能少。
$3491888400=16xx27xx25xx7xx9xx11xx13xx17xx19$
$3087564480=49xx64xx81xx5xx11xx13xx17$
$3171168000=121xx125xx128xx9xx7xx13xx2$
49*64*81*121*125 = 3841992000
49*64*81*121*5*23= 3534632640
49*64*23*29*31*5*9 = 2917938240
32*49*23*29*31*37*3= 3598790496
2
3
4
5
7
8
9
11
13
16
17
19
23
25
27
29
31
32
37
41
43
47
49
53
59
61
64
67
71
73
79
81
83
89
97
[ 本帖最后由 liangbch 于 2009-2-4 15:03 编辑 ]