数组拆分算法

liangbch

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

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
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
8. B[2]=43,47,49,53,59,86,94,98
9. Total 8 number in B[2], LCM of B[2] =619327366
11. B[3]=61,64,67,71,73
12. Total 5 number in B[3], LCM of B[3] =1355706944
14. B[4]=79,81,83,89
15. Total 4 number in B[4], LCM of B[4] =47269413
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"
4. typedef unsigned long DWORD;
5. typedef unsigned char BYTE;
6. typedef unsigned BOOL;
7. #define TRUE 1
8. #define FALSE 0
11. #define MAX_DWORD (4294967295L)
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;
22. bigNum= (n1>n2)?n1:n2;
23. smallNum=(n1<n2)?n1:n2;
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. }
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;
44. pBuff=new BYTE[n+2];
45. if (pBuff==NULL)
46. return;
48. pBuff[0]=pBuff[1]=0;
49. for (i=2;i<=n;i++)
50. pBuff[i]=1;
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);
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. }
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. }
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>
5. typedef unsigned long DWORD;
6. typedef unsigned char BYTE;
7. typedef unsigned BOOL;
8. #define TRUE 1
9. #define FALSE 0
12. #define MAX_DWORD (4294967295L)
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;
23. bigNum= (n1>n2)?n1:n2;
24. smallNum=(n1<n2)?n1:n2;
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. }
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;
45. pBuff=new BYTE[n+1];
46. if (pBuff==NULL)
47. return;
49. memset(pBuff, 1, n+1);
50. // memset(pBuff+1, 0, n/2); //13# 的简化算法
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);
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. }
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. }
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.