数组拆分算法

liangbch

1. 我实现了8#中提到的第一个算法，先给出运行结果

1. 
   
2. B[0]=2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,28,30,32,33,34,35,36,38,39,40,42,44,45,48,50,51,52,55,56,57,60,63,65,66,68,70,72,75,76,77,78,80,84,85,88,90,91,95,96,99,100
   
3. Total 65 number in B[0], LCM of B[0] =2327925600
   
4. 
   
5. B[1]=23,27,29,31,37,41,46,54,58,62,69,74,82,87,93
   
6. Total 15 number in B[1], LCM of B[1] =1693818486
   
7. 
   
8. B[2]=43,47,49,53,59,86,94,98
   
9. Total 8 number in B[2], LCM of B[2] =619327366
   
10. 
    
11. B[3]=61,64,67,71,73
    
12. Total 5 number in B[3], LCM of B[3] =1355706944
    
13. 
    
14. B[4]=79,81,83,89
    
15. Total 4 number in B[4], LCM of B[4] =47269413
    
16. 
    
17. B[5]=92,97
    
18. Total 2 number in B[5], LCM of B[5] =8924

复制代码

liangbch

这里给出代码：

1. #include "stdio.h"
   
2. #include "stdlib.h"
   
3. 
   
4. typedef unsigned long DWORD;
   
5. typedef unsigned char BYTE;
   
6. typedef unsigned BOOL;
   
7. #define TRUE 1
   
8. #define FALSE 0
   
9. 
   
10. 
    
11. #define MAX_DWORD (4294967295L)
    
12. 
    
13. DWORD GCD32(DWORD n1, DWORD n2) //Greatest Common Divisor
    
14. // 功能: 求n1,n2的最大公约数
    
15. //***************************************************
    
16. {
    
17.         DWORD bigNum,smallNum,modNum;
    
18.         //----------------------------------------
    
19.         if (n1==n2)
    
20.                 return n1;
    
21.        
    
22.         bigNum=  (n1>n2)?n1:n2;
    
23.         smallNum=(n1<n2)?n1:n2;
    
24.        
    
25.         while (1)
    
26.         {
    
27.                 modNum=bigNum % smallNum;
    
28.                 if (modNum==0)
    
29.                         break;
    
30.                 bigNum=smallNum;
    
31.                 smallNum=modNum;
    
32.         }
    
33.         return smallNum;
    
34. }
    
35. 
    
36. void divideIntArray(DWORD n)
    
37. {
    
38.         BYTE* pBuff=NULL;
    
39.         DWORD lcm,gcd,limit;
    
40.         DWORD  i,j;
    
41.         BOOL  first;
    
42.         int    count;
    
43. 
    
44.         pBuff=new BYTE[n+2];
    
45.         if (pBuff==NULL)
    
46.                 return;
    
47.        
    
48.         pBuff[0]=pBuff[1]=0;
    
49.         for (i=2;i<=n;i++)
    
50.                 pBuff[i]=1;
    
51.        
    
52.         j=0;
    
53.         while (TRUE)
    
54.         {
    
55.                 i=2;  
    
56.                 lcm=1;
    
57.                 limit=MAX_DWORD/lcm;
    
58.                 while (TRUE)
    
59.                 {
    
60.                         DWORD t;
    
61.                         while ( pBuff[i]==0 && i<=n) //skip empty number
    
62.                                 i++;
    
63.                         if (i>n)
    
64.                                 break;
    
65.                         gcd=GCD32(lcm,i);
    
66.                        
    
67.                         t=i / gcd;
    
68.                         if (t < limit && t>1)
    
69.                         {
    
70.                                 lcm=lcm * t;
    
71.                                 limit=MAX_DWORD/lcm;
    
72.                         }
    
73.                         if (lcm > MAX_DWORD/2)
    
74.                                 break;
    
75.                         i++;
    
76.                 }
    
77.                
    
78.                 if (lcm==1 )
    
79.                         break;
    
80.                 printf("\nB[%d]=",j);
    
81.                 for (count=0,first=TRUE,i=2;i<=n;i++)
    
82.                 {
    
83.                         if ( pBuff[i] && lcm % i==0)
    
84.                         {
    
85.                                 if (!first)
    
86.                                         printf(",");
    
87.                                 printf("%u",i);
    
88.                                 pBuff[i]=0;
    
89.                                 first=FALSE;
    
90.                                 count++;
    
91.                         }
    
92.                 }
    
93.                 printf("\n");
    
94.                 printf("Total %d number in B[%d], LCM of B[%d] =%u\n",count,j,j,lcm);
    
95.                 j++;
    
96.         }
    
97.         delete[] pBuff;
    
98.         pBuff=NULL;
    
99. }
    
100. 
     
101. 
     
102. void divideIntArray(DWORD n);
     
103. int main(int argc, char* argv[])
     
104. {
     
105.         divideIntArray(100);
     
106.         return 0;
     
107. }

复制代码

gxqcn

突然想到一个比较好的简化思路：

1、将数组倒序排序，记作数组A；

2、从A中取出第一个数及其所有的约数，形成一个新数组；

3、重复步骤2，直至A为空为止。

此时将原数组初次划分成一系列的新数组，
这些新数组的“排头兵”可以完全屏蔽其后数字的“最小公倍数”。
所以只要将这些“排头兵”进一步按楼主的要求进行划分即可。

如果对前n个连续正整数进行上述操作，最终将有且仅有[(n+1)/2]组，
它们的“排头兵”依次为：n, n-1, ..., [n/2]+1
这样可以将工作量下降50%

liangbch

但不知这么一来，生成的结果是否比直接处理更优。

gxqcn

是完全等同的。

因为这些“排头兵”也是必须进行划分的，
它们各自的约数就象小第跟着老大站好队伍即可。
一个小弟可以有多个“老大”可选，任选一个即可。

gxqcn

你的12#程序计算 divideIntArray(1024)  得到104 组划分。

我将它略作改造，仅将顺序由升序变为降序，得到的结果则仅需86组。

代码如下：

1. #include "stdio.h"
   
2. #include "stdlib.h"
   
3. #include <memory.h>
   
4. 
   
5. typedef unsigned long DWORD;
   
6. typedef unsigned char BYTE;
   
7. typedef unsigned BOOL;
   
8. #define TRUE 1
   
9. #define FALSE 0
   
10. 
    
11. 
    
12. #define MAX_DWORD (4294967295L)
    
13. 
    
14. DWORD GCD32(DWORD n1, DWORD n2) //Greatest Common Divisor
    
15. // 功能: 求n1,n2的最大公约数
    
16. //***************************************************
    
17. {
    
18.         DWORD bigNum,smallNum,modNum;
    
19.         //----------------------------------------
    
20.         if (n1==n2)
    
21.                 return n1;
    
22.        
    
23.         bigNum=  (n1>n2)?n1:n2;
    
24.         smallNum=(n1<n2)?n1:n2;
    
25.        
    
26.         while (1)
    
27.         {
    
28.                 modNum=bigNum % smallNum;
    
29.                 if (modNum==0)
    
30.                         break;
    
31.                 bigNum=smallNum;
    
32.                 smallNum=modNum;
    
33.         }
    
34.         return smallNum;
    
35. }
    
36. 
    
37. void divideIntArray(DWORD n)
    
38. {
    
39.         BYTE* pBuff=NULL;
    
40.         DWORD lcm,gcd,limit;
    
41.         DWORD  i,j;
    
42.         BOOL  first;
    
43.         int    count;
    
44.        
    
45.         pBuff=new BYTE[n+1];
    
46.         if (pBuff==NULL)
    
47.                 return;
    
48.        
    
49.         memset(pBuff, 1, n+1);
    
50. //        memset(pBuff+1, 0, n/2); //13# 的简化算法
    
51.        
    
52.         j=0;
    
53.         while (TRUE)
    
54.         {
    
55.                 i=n+1;  
    
56.                 lcm=1;
    
57.                 limit=MAX_DWORD/lcm;
    
58.                 while (TRUE)
    
59.                 {
    
60.                         DWORD t;
    
61.                         while (pBuff[--i]==0) //skip empty number
    
62.                                 ;
    
63.                         if (0 == i)
    
64.                                 break;
    
65.                         gcd=GCD32(lcm,i);
    
66.                        
    
67.                         t=i / gcd;
    
68.                         if (t < limit && t>1)
    
69.                         {
    
70.                                 lcm=lcm * t;
    
71.                                 limit=MAX_DWORD/lcm;
    
72.                         }
    
73.                         if (lcm > MAX_DWORD/2)
    
74.                                 break;
    
75.                 }
    
76.                
    
77.                 if (lcm==1 )
    
78.                         break;
    
79.                 printf("\nB[%d]=",j);
    
80.                 for (count=0,first=TRUE,i=1;i<=n;i++)
    
81.                 {
    
82.                         if ( pBuff[i] && lcm % i==0)
    
83.                         {
    
84.                                 if (!first)
    
85.                                         printf(",");
    
86.                                 printf("%u",i);
    
87.                                 pBuff[i]=0;
    
88.                                 first=FALSE;
    
89.                                 count++;
    
90.                         }
    
91.                 }
    
92.                 printf("\n");
    
93.                 printf("Total %d number in B[%d], LCM of B[%d] =%u\n",count,j,j,lcm);
    
94.                 j++;
    
95.         }
    
96.         delete[] pBuff;
    
97.         pBuff=NULL;
    
98. }
    
99. 
    
100. 
     
101. void divideIntArray(DWORD n);
     
102. int main(int argc, char* argv[])
     
103. {
     
104.         divideIntArray(1024);
     
105.         return 0;
     
106. }

复制代码

liangbch

谢谢楼上，好快的编程速度！

gxqcn

我只是略作改造（不敢说“改进”）而已，
主要模块还是你的。

liangbch

你改进的这个版本得到的数组的个数确实少了。
我提的这个问题的和求高精度对数有关。其实精确的需求是这样的。
   将包含1..n共n个自然数的数组拆成几个数组，
     1)使得得到的每个数组各个数的最小公倍数小于2^32
            2)使得得到的所有数组的跨度的和最小。跨度是这样定义的。如一个数组中最小的那个数是x。则这个数组的跨度L=n-x+1

       1.有时间验证下，你改进的程序和我的原始版本，那个跨度和最小。
   2.我将试验我在8#提到的第二个算法，估计，这个算法得到的结果应该比现在的这个版本得到的结果更优。

liangbch

重新描述一下我的第2个算法。

定义：
  1.符号$p_n$ 表示第n个质数，如$p_1$=2,$p_2=3$,$p_3=5$
    2.自然数的阶,如果一个自然数的最大素因数是$p_k$,我们说这个自然数的阶是k. 例：1的阶是0，2的阶是1，60的阶是3，7的阶是4.

数组拆分算法：
  1.将1到n之间的所有自然数按照其阶和它的大小排序，即，首先阶从小到大排序，阶相同者按照数的从小到大的顺序排序，另排序后的数组为A。
  2.置i=1;   
    3.从数组A中顺序取数，直到这几个数的最小公倍数lcm恰好小于2^32.
    4.将所有lcm的约数从数组中移出，放入$B_i$数组.
    5.如果数组A为空，结束。
  6.i=i+1,转3.