数组拆分算法

northwolves · 发表于 2009-2-4 21:55:46

感觉好难好难。楼上最新进展怎样？

liangbch · 发表于 2009-2-5 10:51:05

目前，已经写了多个版本，均不理想，新版本正在编写中。

litaoye · 发表于 2009-2-5 13:37:27

恩，这题挺有意思的，但也挺复杂的。我也提供一个思路供大家参考吧！基本上就是用贪心，以1024个数为例，其实只需要计算513-1024就可以了，前面的1-512，都是后面的约数，不会成为限制条件找到513-1024中公约数最大的作为一对，并计算其最小公倍数m，然后再从剩余的数里找到同m公约数最大的数q，并计算m同q的最小公倍m1，以此类推，直到mi > 2^32，然后对剩余的数重复上面的办法，直到所有数都分组完毕。这种办法看起来效率比较低，但其实有些地方，有很大的优化空间，首先，1024个数的约数范围为1-1024/3，约数最大的一对为1023（341*3）和682（341 * 2），其次的一对为340*2和340*3...... 找到1023和682后，最小公倍为2046，找出2046小于341的最大约数，然后在剩余的数中找到其倍数，就应当是下一个要找的数。然后重新计算2046和该数的最小公倍（应该不用重新算，直接用2046 * 该数 / 约数就行），再找出小于341的最大约数（这个计算也可以优化），以此类推......

liangbch · 发表于 2009-2-5 15:46:51

22以内的数可分一组 within 22 lcm1=(16*27*25*7*11*13*17*19) =3,491,888,400 42以内的数可分2组 within 42 lcm1=(16*27*25*7*11*13*17*19) =3,491,888,400 lcm2= (23*29*31*32*37*41*3) =3,011,232,864 60以内的数可分3组 within 60 lcm1 (=16*27*25*7*11*13*17*19) lcm2 (=23*29*31*32*37*41*3 ) =3,011,232,864 lcm3 (=43*47*49*53*59*12) =3,715,964,196 78以内的数可分4组 within 78 lcm1= (=16*27*25*7*11*13*17*19)=3,491,888,400 lcm2= (=23*29*31*32*37*41*3 ) =3,011,232,864 lcm3= (=43*47*49*53*59*12) =3,715,964,196 lcm4= (=61*64*67*71*73) =1,355,706,944 100以内的数可分5组 within 100 lcm1= (=16*27*25*7*11*13*17*19)=3,491,888,400 lcm2= (=23*29*31*81*97*4 ) = 649,836,756 lcm3= (=37*64*79*83*89*3) = 4,145,702,592.00 lcm4= (=41*43*47*49*53*2) = 430,380,034 lcm5= (=59*61*67*71*73) = 1,249,792,339.00

shshsh_0510 · 发表于 2009-2-5 17:29:30

这个比较难，通用的肯定计算量巨大，就找个特例看看，比如1024 ifactors(factorial(1024))=[1, [[2, 1023], [3, 508], [5, 253], [7, 168], [11, 101], [13, 84], [17, 63], [19, 55], [23, 45], [29, 36], [31, 34], [37, 27], [41, 24], [43, 23], [47, 21], [53, 19], [59, 17], [61, 16], [67, 15], [71, 14], [73, 14], [79, 12], [83, 12], [89, 11], [97, 10], [101, 10], [103, 9], [107, 9], [109, 9], [113, 9], [127, 8], [131, 7], [137, 7], [139, 7], [149, 6], [151, 6], [157, 6], [163, 6], [167, 6], [173, 5], [179, 5], [181, 5], [191, 5], [193, 5], [197, 5], [199, 5], [211, 4], [223, 4], [227, 4], [229, 4], [233, 4], [239, 4], [241, 4], [251, 4], [257, 3], [263, 3], [269, 3], [271, 3], [277, 3], [281, 3], [283, 3], [293, 3], [307, 3], [311, 3], [313, 3], [317, 3], [331, 3], [337, 3], [347, 2], [349, 2], [353, 2], [359, 2], [367, 2], [373, 2], [379, 2], [383, 2], [389, 2], [397, 2], [401, 2], [409, 2], [419, 2], [421, 2], [431, 2], [433, 2], [439, 2], [443, 2], [449, 2], [457, 2], [461, 2], [463, 2], [467, 2], [479, 2], [487, 2], [491, 2], [499, 2], [503, 2], [509, 2], [521, 1], [523, 1], [541, 1], [547, 1], [557, 1], [563, 1], [569, 1], [571, 1], [577, 1], [587, 1], [593, 1], [599, 1], [601, 1], [607, 1], [613, 1], [617, 1], [619, 1], [631, 1], [641, 1], [643, 1], [647, 1], [653, 1], [659, 1], [661, 1], [673, 1], [677, 1], [683, 1], [691, 1], [701, 1], [709, 1], [719, 1], [727, 1], [733, 1], [739, 1], [743, 1], [751, 1], [757, 1], [761, 1], [769, 1], [773, 1], [787, 1], [797, 1], [809, 1], [811, 1], [821, 1], [823, 1], [827, 1], [829, 1], [839, 1], [853, 1], [857, 1], [859, 1], [863, 1], [877, 1], [881, 1], [883, 1], [887, 1], [907, 1], [911, 1], [919, 1], [929, 1], [937, 1], [941, 1], [947, 1], [953, 1], [967, 1], [971, 1], [977, 1], [983, 1], [991, 1], [997, 1], [1009, 1], [1013, 1], [1019, 1], [1021, 1]]] 接下来就看多贪心了

我们假设我们的方案使所有组都是满位(10位10进制），当然这比较难做到。于是，因子重数为1，2的那些先不管，重数为3的都是些3位数，如果都在一组，有可能给该组公倍数乘2，但不在一组则为另一组减少3位，所以一定放一组重数为4，5，6的也要放到一组重数为7的可能使该组多乘60，而重数为7的都是3位，也合算重数为8的就不好说了于是我们可用分步的贪心：先将重数为7以上的石头放好，再放那些沙子去调整

shshsh_0510 · 发表于 2009-2-6 08:36:49

上面光“大石头”就上百了，况且还要增加如31*31 ，29*29，31*29 ..等“大石头”，看来1024太大了，还是先找个小一点的

liangbch · 发表于 2009-2-6 11:40:30

回无心人，从我的实际应用来讲，n<65536,可用一个WORD类型表示。这个问题的实际应用。为方便起见，我做一些简化。有m个分数，m<=n, 通常m很接近于n. 这些分数全部真分数（分子小于分母），且分母互不相同且小于n，求这些分数的和并精确到R位。 R通常大于100而小于65535。如果按照通常的做法，复杂度为 m*r, 如果将这些分数分成几组，每一组的各个分数先通分并相加，再做除法则可以提高速度。当n较大时，实现一个优化的算法比较困看。详细的算法以后再讲，现在先贴出n<223时的分组做法，这个做法是半手工的，但应该是一个接近最佳答案的做法。下贴出程序运行结果： check numbers within 22 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, check numbers within 42 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42, LCM[1]=3011232864, bArray[1]=23,29,31,32,37,41, check numbers within 62 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60, LCM[1]=3011232864, bArray[1]=23,29,31,32,37,41,46,58, LCM[2]=3715964196, bArray[2]=43,47,49,53,59, check numbers within 78 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78, LCM[1]=3011232864, bArray[1]=23,29,31,32,37,41,46,58,62,69,74, LCM[2]=3715964196, bArray[2]=43,47,49,53,59, LCM[3]=2711413888, bArray[3]=61,64,67,71,73, check numbers within 100 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100, LCM[1]=2249244060, bArray[1]=23,29,31,37,46,49,58,62,69,74,87,92,93,98, LCM[2]=4215967680, bArray[2]=32,41,43,47,53,64,82,86,94,96, LCM[3]=2773511766, bArray[3]=59,61,67,71,81, LCM[4]=4132280413, bArray[4]=73,79,83,89,97, check numbers within 88 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88, LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87, LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86, LCM[3]=4140735876, bArray[3]=53,59,61,67,81, LCM[4]=203909586, bArray[4]=71,73,79,83, check numbers within 106 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105, LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98, LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94, LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106, LCM[4]=203909586, bArray[4]=71,73,79,83, LCM[5]=179618198, bArray[5]=89,97,101,103, check numbers within 124 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120, LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124, LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123, LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122, LCM[4]=203909586, bArray[4]=71,73,79,83, LCM[5]=179618198, bArray[5]=89,97,101,103, LCM[6]=318936398, bArray[6]=107,109,113,121, check numbers within 138 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136, LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138, LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129, LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134, LCM[4]=203909586, bArray[4]=71,73,79,83, LCM[5]=179618198, bArray[5]=89,97,101,103, LCM[6]=318936398, bArray[6]=107,109,113,121, LCM[7]=284908625, bArray[7]=125,127,131,137, check numbers within 162 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136,140,143,144,150,152,153,154,156, LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,145,147,155,160,161, LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129,141,148, LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134,159,162, LCM[4]=203909586, bArray[4]=71,73,79,83,142,146,158, LCM[5]=179618198, bArray[5]=89,97,101,103, LCM[6]=318936398, bArray[6]=107,109,113,121, LCM[7]=284908625, bArray[7]=125,127,131,137, LCM[8]=490995677, bArray[8]=139,149,151,157, check numbers within 178 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136,140,143,144,150,152,153,154,156,165,168,170,171,175,176, LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,145,147,155,160,161,174, LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129,141,148,164,172, LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134,159,162,177, LCM[4]=203909586, bArray[4]=71,73,79,83,142,146,158,166, LCM[5]=179618198, bArray[5]=89,97,101,103,178, LCM[6]=318936398, bArray[6]=107,109,113,121, LCM[7]=284908625, bArray[7]=125,127,131,137, LCM[8]=490995677, bArray[8]=139,149,151,157, LCM[9]=795860377, bArray[9]=163,167,169,173, check numbers within 196 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136,140,143,144,150,152,153,154,156,165,168,170,171,175,176,180,182,187,189,190,195, LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,145,147,155,160,161,174,184,186,192,196, LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129,141,148,164,172,185,188, LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134,159,162,177,183, LCM[4]=203909586, bArray[4]=71,73,79,83,142,146,158,166, LCM[5]=179618198, bArray[5]=89,97,101,103,178,194, LCM[6]=318936398, bArray[6]=107,109,113,121, LCM[7]=284908625, bArray[7]=125,127,131,137, LCM[8]=490995677, bArray[8]=139,149,151,157, LCM[9]=795860377, bArray[9]=163,167,169,173, LCM[10]=1194324337, bArray[10]=179,181,191,193, check numbers within 222 LCM[0]=3491888400, bArray[0]=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,30,33,34,35,36,38,39,40,42,44,45,48,50,51,52,54,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,99,100,102,104,105,108,110,112,114,117,119,120,126,130,132,133,135,136,140,143,144,150,152,153,154,156,165,168,170,171,175,176,180,182,187,189,190,195,198,200,204,208,209,210,216,220,221, LCM[1]=1945292160, bArray[1]=23,29,31,32,46,49,58,62,64,69,87,92,93,96,98,115,116,124,128,138,145,147,155,160,161,174,184,186,192,196,203,217, LCM[2]=183951420, bArray[2]=37,41,43,47,74,82,86,94,111,123,129,141,148,164,172,185,188,205,215,222, LCM[3]=4140735876, bArray[3]=53,59,61,67,81,106,118,122,134,159,162,177,183,201,212, LCM[4]=203909586, bArray[4]=71,73,79,83,142,146,158,166,213,219, LCM[5]=179618198, bArray[5]=89,97,101,103,178,194,202,206, LCM[6]=318936398, bArray[6]=107,109,113,121,214,218, LCM[7]=284908625, bArray[7]=125,127,131,137, LCM[8]=490995677, bArray[8]=139,149,151,157, LCM[9]=795860377, bArray[9]=163,167,169,173, LCM[10]=1194324337, bArray[10]=179,181,191,193, LCM[11]=1712269431, bArray[11]=197,199,207,211, 再给出代码：

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef unsigned short WORD;
typedef unsigned long DWORD;
/*
22以内的数可分一组
lcm1=(16*27*25*7*11*13*17*19) =3,491,888,400
42以内的数可分2组
lcm1=(16*27*25*7*11*13*17*19) =3,491,888,400
lcm2= (23*29*31*32*37*41*3) =3,011,232,864
60以内的数可分3组
lcm1 (=16*27*25*7*11*13*17*19) =3,491,888,400
lcm2 (=23*29*31*32*37*41*3 ) =3,011,232,864
lcm3 (=43*47*49*53*59*12) =3,715,964,196
78以内的数可分4组
lcm1= (=16*27*25*7*11*13*17*19)=3,491,888,400
lcm2= (=23*29*31*32*37*41*3 ) =3,011,232,864
lcm3= (=43*47*49*53*59*12) =3,715,964,196
lcm4= (=61*64*67*71*73*3) =2,711,413,888
100以内的数可分5组
lcm1 =16*27*25*7*11*13*17*19 =3,491,888,400
lcm2 =23*29*31*37*49*3*4*5 =2,249,244,060
lcm3 =41*43*47*53*64*3*5 =4,215,967,680
lcm4 =59*61*67*81*71*2 =2,773,511,766
lcm5 =73*79*83*89*97 =4,132,280,413
226以内的数可分12组
lcm1 =16*27*25*7*11*13*17*19 =3,491,888,400 (up to 22)
lcm2 =23*29*31*128*49*3*5 =1,945,292,160 (up to 36)
lcm3 =37*41*43*47*4*3*5 =183,951,420 (up to 52)
lcm4 =53*59*61*67*81*4 =4140735876 (up to 70)
lcm5 =71*73*79*83*3*2 =203,909,586 (up to 88)
lcm6 =89*97*101*103*2 =179,618,198 (up to 106)
lcm7 =107*109*113*121*2 =318,936,398 (up to 124)
lcm8 =125*127*131*137 =284,908,625 (up to 138)
lcm9 =139*149*151*157 =490,995,677 (up to 162)
lcm10=163*167*169*173 =795,860,377 (up to 178)
lcm11=179*181*191*193 =1,194,324,337 (up to 196)
lcm12=197*199*207*211 =1712269431 (up to 222)
*/
void verifySplitArray(WORD n, const DWORD lcmArray[],int len)
{
WORD *pBuff=new WORD[n];
int i,j,c1,c2;
for (i=1;i<=n;i++)
pBuff[i-1]=i;
c1=n;
for (j=0;j<len;j++)
{
printf("\nLCM[%d]=%u,bArray[%d]=",j,lcmArray[j],j);
for (c2=0,i=0;i<c1;i++)
{
if (lcmArray[j] % pBuff[i]==0)
{
printf("%hu,",pBuff[i]);
}
else
{
pBuff[c2++]=pBuff[i];
}
}
c1=c2;
}
if (c1>0)
{
printf("\nThe following is unsort:\n");
for (i=0;i<c1;i++)
{
printf("%hu,",pBuff[i]);
}
}
delete[] pBuff;
}
void verifyAll()
{
const DWORD lcmArray22[]={3491888400};
const DWORD lcmArray42[]={3491888400,3011232864};
const DWORD lcmArray60[]={3491888400, 3011232864,3715964196};
const DWORD lcmArray78[]={3491888400, 3011232864, 3715964196, 2711413888};
const DWORD lcmArray100[]={3491888400,2249244060,4215967680, 2773511766,4132280413};
const DWORD lcmArray222[]=
{
3491888400,1945292160 ,183951420,4140735876,
203909586,179618198,318936398,284908625,
490995677,795860377,1194324337,1712269431
};
printf("\n\ncheck numbers within %d\n",22);
verifySplitArray(22,lcmArray22,sizeof(lcmArray22)/sizeof(DWORD));
printf("\n\ncheck numbers within %d\n",42);
verifySplitArray(42,lcmArray42,sizeof(lcmArray42)/sizeof(DWORD));
printf("\n\ncheck numbers within %d\n",62);
verifySplitArray(60,lcmArray60,sizeof(lcmArray60)/sizeof(DWORD));
printf("\n\ncheck numbers within %d\n",78);
verifySplitArray(78,lcmArray78,sizeof(lcmArray78)/sizeof(DWORD));
printf("\n\ncheck numbers within %d\n",100);
verifySplitArray(100,lcmArray100,sizeof(lcmArray100)/sizeof(DWORD));
//-------------------------------------------------
printf("\n\ncheck numbers within %d\n",88);
verifySplitArray(88,lcmArray222,5);
printf("\n\ncheck numbers within %d\n",106);
verifySplitArray(106,lcmArray222,6);
printf("\n\ncheck numbers within %d\n",124);
verifySplitArray(124,lcmArray222,7);
printf("\n\ncheck numbers within %d\n",138);
verifySplitArray(138,lcmArray222,8);
printf("\n\ncheck numbers within %d\n",162);
verifySplitArray(162,lcmArray222,9);
printf("\n\ncheck numbers within %d\n",178);
verifySplitArray(178,lcmArray222,10);
printf("\n\ncheck numbers within %d\n",196);
verifySplitArray(196,lcmArray222,11);
printf("\n\ncheck numbers within %d\n",222);
verifySplitArray(222,lcmArray222,12);
}
int main(int argc, char* argv[])
{
verifyAll();
return 0;
}

复制代码

shshsh_0510 · 发表于 2009-2-6 11:50:47

如 27 # medie2005 那样，用2进制可以分析的更多一些对于重数为8的因子，如 [127, 8] 分别对应127* 1 - 127*8 乘1，2，3，4显然不用考虑 *5，6，7，8 这4个数，因为127是7位2进制，如果6和8在一组,只给这组增加了2位(乘了3),所以放在一起比较核算但假如5，6，7这几个数在同一组中而 127*8的这组又不包含3，5，7这几个因子的话，那么 127*5，127*6，127*7这几个数放在哪组都给该组增加7位。但由于上述条件很苛刻，所以倾向于将所有127的倍数都放在一组

liangbch · 发表于 2009-2-6 12:02:11

对于重数为8的因子，如 [127, 8] 分别对应127* 1 - 127*8 乘1，2，3，4显然不用考虑 *5，6，7，8 这4个数，因为127是7位2进制，如果6和8在一组,只给这组增加了2位(乘了3),所以放在一起比较核算

不明白你的意思，127*1 到 127*4 的最小公倍数是 127*3*4 不明白你的意思，127*1 到 127*8 的最小公倍数是 127*8*3*5*7

liangbch · 发表于 2009-2-6 12:24:18

我的分组的基本原则。第2种方法： 1. 任何一个自然数都可以写成几个质数乘积的乘积。 2. 对n以内所有的数按照质因数的大小排序，首先按照最大质因数排序升序排列，最大质因数相同者按照次大质因数排序，以此类推。 3. 从排序后数组中依次取数，直到这几个数的最小公倍数小于2^32, 将这些数分到一组。 4。重复步骤3，直到数组取空。例如对16以内的数，排序后将使这个样子 2=2 4=2*2 8=2*2*2 16=2*2*2*2 3=3 6=3*2 12=3*2*2 9=3*3 5=5 10=5*2 15=5*3 7=7 14=7*2 11=11 13=13 14=14 15=15 对于127*1 到 127*8 排序后将是 127 127*2 127*4 127*8 127*3 127*6 127*5 127*7 第3种方法： 1. 任何一个自然数都可以写成几个质数幂的乘积。 2. 对n以内所有的数按照质数幂因子的大小排序，首先按照最大质数幂因子排序升序排列，最大质数幂因子相同者按照次大质数幂因子排序，以此类推。 3. 从排序后数组中依次取数，直到这几个数的最小公倍数小于2^32, 将这些数分到一组。 4。重复步骤3，直到数组取空。 2=2 3=3 6=3*2 4=4 12=4*3 5=5 10=5*2 15=5*3 7=7 14=7*2 8=8 9=9 11=11 13=13 16=16 我倾向于第3个方法。当然，这只是基本原则，在实际算法实现中，采用了更多的规则，以实现分组最优。

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 数组拆分算法