1. 我实现了8#中提到的第一个算法，先给出运行结果
B=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
Total 65 number in B, LCM of B =2327925600
B=23,27,29,31,37,41,46,54,58,62,69,74,82,87,93
Total 15 number in B, LCM of B =1693818486
B=43,47,49,53,59,86,94,98
Total 8 number in B, LCM of B =619327366
B=61,64,67,71,73
Total 5 number in B, LCM of B =1355706944
B=79,81,83,89
Total 4 number in B, LCM of B =47269413
B=92,97
Total 2 number in B, LCM of B =8924
这里给出代码：#include "stdio.h"
#include "stdlib.h"
typedef unsigned long DWORD;
typedef unsigned char BYTE;
typedef unsigned BOOL;
#define TRUE 1
#define FALSE 0
#define MAX_DWORD (4294967295L)
DWORD GCD32(DWORD n1, DWORD n2) //Greatest Common Divisor
// 功能: 求n1,n2的最大公约数
//***************************************************
{
DWORD bigNum,smallNum,modNum;
//----------------------------------------
if (n1==n2)
return n1;
bigNum=(n1>n2)?n1:n2;
smallNum=(n1<n2)?n1:n2;
while (1)
{
modNum=bigNum % smallNum;
if (modNum==0)
break;
bigNum=smallNum;
smallNum=modNum;
}
return smallNum;
}
void divideIntArray(DWORD n)
{
BYTE* pBuff=NULL;
DWORD lcm,gcd,limit;
DWORDi,j;
BOOLfirst;
int count;
pBuff=new BYTE;
if (pBuff==NULL)
return;
pBuff=pBuff=0;
for (i=2;i<=n;i++)
pBuff=1;
j=0;
while (TRUE)
{
i=2;
lcm=1;
limit=MAX_DWORD/lcm;
while (TRUE)
{
DWORD t;
while ( pBuff==0 && i<=n) //skip empty number
i++;
if (i>n)
break;
gcd=GCD32(lcm,i);
t=i / gcd;
if (t < limit && t>1)
{
lcm=lcm * t;
limit=MAX_DWORD/lcm;
}
if (lcm > MAX_DWORD/2)
break;
i++;
}
if (lcm==1 )
break;
printf("\nB[%d]=",j);
for (count=0,first=TRUE,i=2;i<=n;i++)
{
if ( pBuff && lcm % i==0)
{
if (!first)
printf(",");
printf("%u",i);
pBuff=0;
first=FALSE;
count++;
}
}
printf("\n");
printf("Total %d number in B[%d], LCM of B[%d] =%u\n",count,j,j,lcm);
j++;
}
delete[] pBuff;
pBuff=NULL;
}
void divideIntArray(DWORD n);
int main(int argc, char* argv[])
{
divideIntArray(100);
return 0;
}
突然想到一个比较好的简化思路：
1、将数组倒序排序，记作数组A；
2、从A中取出第一个数及其所有的约数，形成一个新数组；
3、重复步骤2，直至A为空为止。
此时将原数组初次划分成一系列的新数组，
这些新数组的“排头兵”可以完全屏蔽其后数字的“最小公倍数”。
所以只要将这些“排头兵”进一步按楼主的要求进行划分即可。
如果对前n个连续正整数进行上述操作，最终将有且仅有[(n+1)/2]组，
它们的“排头兵”依次为：n, n-1, ..., +1
这样可以将工作量下降50%
但不知这么一来，生成的结果是否比直接处理更优。
是完全等同的。:)
因为这些“排头兵”也是必须进行划分的，
它们各自的约数就象小第跟着老大站好队伍即可。
一个小弟可以有多个“老大”可选，任选一个即可。
你的12#程序计算 divideIntArray(1024)得到104 组划分。
我将它略作改造，仅将顺序由升序变为降序，得到的结果则仅需86组。
代码如下：#include "stdio.h"
#include "stdlib.h"
#include <memory.h>
typedef unsigned long DWORD;
typedef unsigned char BYTE;
typedef unsigned BOOL;
#define TRUE 1
#define FALSE 0
#define MAX_DWORD (4294967295L)
DWORD GCD32(DWORD n1, DWORD n2) //Greatest Common Divisor
// 功能: 求n1,n2的最大公约数
//***************************************************
{
DWORD bigNum,smallNum,modNum;
//----------------------------------------
if (n1==n2)
return n1;
bigNum=(n1>n2)?n1:n2;
smallNum=(n1<n2)?n1:n2;
while (1)
{
modNum=bigNum % smallNum;
if (modNum==0)
break;
bigNum=smallNum;
smallNum=modNum;
}
return smallNum;
}
void divideIntArray(DWORD n)
{
BYTE* pBuff=NULL;
DWORD lcm,gcd,limit;
DWORDi,j;
BOOLfirst;
int count;
pBuff=new BYTE;
if (pBuff==NULL)
return;
memset(pBuff, 1, n+1);
// memset(pBuff+1, 0, n/2); //13# 的简化算法
j=0;
while (TRUE)
{
i=n+1;
lcm=1;
limit=MAX_DWORD/lcm;
while (TRUE)
{
DWORD t;
while (pBuff[--i]==0) //skip empty number
;
if (0 == i)
break;
gcd=GCD32(lcm,i);
t=i / gcd;
if (t < limit && t>1)
{
lcm=lcm * t;
limit=MAX_DWORD/lcm;
}
if (lcm > MAX_DWORD/2)
break;
}
if (lcm==1 )
break;
printf("\nB[%d]=",j);
for (count=0,first=TRUE,i=1;i<=n;i++)
{
if ( pBuff && lcm % i==0)
{
if (!first)
printf(",");
printf("%u",i);
pBuff=0;
first=FALSE;
count++;
}
}
printf("\n");
printf("Total %d number in B[%d], LCM of B[%d] =%u\n",count,j,j,lcm);
j++;
}
delete[] pBuff;
pBuff=NULL;
}
void divideIntArray(DWORD n);
int main(int argc, char* argv[])
{
divideIntArray(1024);
return 0;
}
谢谢楼上，好快的编程速度！
我只是略作改造（不敢说“改进”）而已，
主要模块还是你的。
你改进的这个版本得到的数组的个数确实少了。
我提的这个问题的和求高精度对数有关。其实精确的需求是这样的。
将包含1..n共n个自然数的数组拆成几个数组，
1)使得得到的每个数组各个数的最小公倍数小于2^32
2)使得得到的所有数组的跨度的和最小。跨度是这样定义的。如一个数组中最小的那个数是x。则这个数组的跨度L=n-x+1
1.有时间验证下，你改进的程序和我的原始版本，那个跨度和最小。
2.我将试验我在8#提到的第二个算法，估计，这个算法得到的结果应该比现在的这个版本得到的结果更优。
重新描述一下我的第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.