【擂台醒目】计算公倍数的最佳算法，效率最高者独得200分
输入：
1. 一组无符号长整型数，求出这组数的公倍数
2. 数组长度
3. 基数。仅计算大于该基数的最小公倍数
4. 个数。计算得出公倍数的个数。
输出
按照所给个数N，输出给定数组的最小的N个公倍数。
问题点数：200、回复次数：127Top
1 楼Icat（晨）回复于 2003-08-01 19:46:17 得分 0
公倍数个数?
是指最小公倍数到全部的乘积中的公倍数么?
呵呵,我数学不好^_^Top
2 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 19:47:10 得分 2
4. 个数。计算得出公倍数的个数。--- 无穷多啊？Top
3 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 19:48:13 得分 0
最小的N个公倍数。--- 为什么最小的还有N个？？？那这个最字怎么理解？Top
4 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 19:48:51 得分 0
你的题目应该给出一个例子，否则很难看懂。Top
5 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 19:59:38 得分 0
//范例文件头
bool CalcLCM( DWORD dwBase, DWORD *pNumbers, DWORD NumCount, DWORD *pOutNumbers, DWORD dwOutCount );
//调用：
DWORD dwArray[] = { 4, 6, 8 };
DWORD dwOut[3];
CalcLCM( 1, dwArray, 3, dwOut, 3 );
cout << dwOut[0] << endl << dwOut[1] << endl << dwOut[2] << endl;
//输出
24
48
72
Top
6 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 20:00:20 得分 0
fireseed(奶油狗) ( )：啊，你这是在做什么？Top
7 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 20:03:07 得分 0
fireseed(奶油狗) ( )：我刚才看到你的源代码了。呵。可是。。。我吓了一跳，还以为你要自己独得200分呢，呵呵，开个玩笑。Top
8 楼pengzhenwanli（紫气日盈）回复于 2003-08-01 20:04:39 得分 0
markTop
9 楼Icat（晨）回复于 2003-08-01 20:18:51 得分 0
还是不明白72哪来的?
为什么没有更大的?Top
10 楼realmyth（wind）回复于 2003-08-01 20:20:04 得分 0
楼主好象是出了道ACMTop
11 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 20:25:17 得分 0
这个题做出来是不成问题的，但要做出最佳算法的，恐怕有难度。Top
12 楼yunyun820930（我爱张云芸）回复于 2003-08-01 20:27:42 得分 0
gz.......有意思 呵呵Top
13 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 20:28:23 得分 0
我在网吧上网，不能直接参与楼主你的活动，只能在这胡扯一下，捧捧场了，不介意吧。Top
14 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 20:31:04 得分 0
一种办法是穷举法，但这种显然不是最佳算法了。Top
15 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 20:33:56 得分 0
说简单一点，就是给你几个数，让你求这几个数的N个公倍数。这N个公倍数必须是这几个数的所有公倍数里最小的N个公倍数。Top
16 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 20:34:46 得分 0
穷举也行啊，反正就咱们这些人，谁的算法效率高，分给谁咯~Top
17 楼Icat（晨）回复于 2003-08-01 20:46:28 得分 0
^_^,那偶去写个穷举Top
18 楼realmyth（wind）回复于 2003-08-01 20:49:29 得分 0
有难度啊,研究中...Top
19 楼Dragon132（飞龙在天）回复于 2003-08-01 20:52:42 得分 2
做完啦！
#include <stdio.h>
int min(int a,int b)
{
int t;
if(a<b)
{
t=a;a=b;b=t;
}
while(a%b)
{
t=a%b;
a=b;
b=t;
}
return b;
}
main()
{
int a[20];
int incount,outcount,i,base;
printf("Please enter the number N to count:");
scanf("%d",&incount);
printf("Please enter %d number:",incount);
for(i=1;i<=incount;i++)
scanf("%d",&a[i]);
a[0]=a[1];
for(i=2;i<=incount;i++)
a[0]=a[0]*a[i]/min(a[0],a[i]);
printf("Please enter the base number:");
scanf("%d",&base);
printf("Please enter the outcount of number:");
scanf("%d",&outcount);
for(i=base/a[0]+1;i<base/a[0]+1+outcount;i++)
printf("%d\n",i*a[0]);
}
Top
20 楼Dragon132（飞龙在天）回复于 2003-08-01 20:55:32 得分 2
有点小问题改一下：
#include <stdio.h>
int min(unsigned long a,unsigned long b)
{
unsigned long t;
if(a<b)
{
t=a;a=b;b=t;
}
while(a%b)
{
t=a%b;
a=b;
b=t;
}
return b;
}
main()
{
unsigned long a[20];
unsigned long incount,outcount,i,base;
printf("Please enter the number N to count:");
scanf("%d",&incount);
printf("Please enter %d number:",incount);
for(i=1;i<=incount;i++)
scanf("%d",&a[i]);
a[0]=a[1];
for(i=2;i<=incount;i++)
a[0]=a[0]*a[i]/min(a[0],a[i]);
printf("Please enter the base number:");
scanf("%d",&base);
printf("Please enter the outcount of number:");
scanf("%d",&outcount);
for(i=base/a[0]+1;i<base/a[0]+1+outcount;i++)
printf("%d\n",i*a[0]);
}
Top
21 楼Icat（晨）回复于 2003-08-01 20:58:08 得分 2
有个想法,先求出最大公约数,
然后每一个数分别除以它*最大公约数(其实就是除n-1次)
然后相乘,就是最小公倍数了,接着就是乘自然数取出满足条件的最小公倍数了
Top
22 楼Icat（晨）回复于 2003-08-01 21:01:12 得分 2
其实除N-1次,也就是乘积除以最大公约数的n-1次方
呵呵
程序还在写Top
23 楼Dragon132（飞龙在天）回复于 2003-08-01 21:05:57 得分 2
#include <stdio.h>
int min(unsigned long a,unsigned long b)
{
unsigned long t;
if(a<b)
{
t=a;a=b;b=t;
}
for(i=1;i<=b;i++)
(i*a%b==0) break;
return i*a;
}
main()
{
unsigned long a[20];
unsigned long incount,outcount,i,base;
printf("Please enter the number N to count:");
scanf("%d",&incount);
printf("Please enter %d number:",incount);
for(i=1;i<=incount;i++)
scanf("%d",&a[i]);
a[0]=a[1];
for(i=2;i<=incount;i++)
a[0]=min(a[0],a[i]);
printf("Please enter the base number:");
scanf("%d",&base);
printf("Please enter the outcount of number:");
scanf("%d",&outcount);
for(i=base/a[0]+1;i<base/a[0]+1+outcount;i++)
printf("%d\n",i*a[0]);
}
Top
24 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 21:15:28 得分 0
Dragon132(Dragon) 的相对测试结果
Please enter the number N to count:3
Please enter 3 number:127
133
159
Please enter the base number:1
Please enter the outcount of number:5
2685669
5371338
8057007
10742676
13428345
请按任意键继续 . . .
运算区共计耗时0.000251987秒Top
25 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 21:18:15 得分 0
Dragon132(Dragon) 果然强，比我的算法快多了！Top
26 楼Dragon132（飞龙在天）回复于 2003-08-01 21:20:35 得分 2
to fireseed(奶油狗)
怎么测出来的啊，这么精确Top
27 楼Dragon132（飞龙在天）回复于 2003-08-01 21:24:35 得分 2
其实还是你强，你昨天的问题我可是只知道一问，做你的题真的是一种享受Top
28 楼Icat（晨）回复于 2003-08-01 21:24:39 得分 2
Dragon132(Dragon)
好强,
fireseed(奶油狗)
计时是如何计的?Top
29 楼Icat（晨）回复于 2003-08-01 21:25:21 得分 2
你们就别再谦虚,,都好强的说,
^_^Top
30 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 21:25:26 得分 0
to Dragon132(Dragon)
CTimer 一旦拥有，别无所求
class CTimer
{
public:
CTimer() {QueryPerformanceFrequency(&m_Frequency); Start();}
void Start() {QueryPerformanceCounter(&m_StartCount);}
double End() {LARGE_INTEGER CurrentCount;QueryPerformanceCounter(&CurrentCount);return double(CurrentCount.LowPart - m_StartCount.LowPart) / (double)m_Frequency.LowPart;}
private:
LARGE_INTEGER m_Frequency;
LARGE_INTEGER m_StartCount;
};
Top
31 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 21:29:22 得分 0
公布我那不值一提的慢算法：
bool CalcLCM( DWORD dwBase, DWORD *pNumbers, DWORD NumCount, DWORD *pOutNumbers, DWORD dwOutCount )
{
CTimer t;
if ( 0 == pNumbers || NumCount < 2 || 0 == pOutNumbers || 0 == dwOutCount )
return false;
DWORD dwTemp = 0, i;
for ( DWORD dwMultiple = dwBase; dwMultiple < 0xffffffffUL; dwMultiple++ )
{
for ( i = 0; i < NumCount; i++ )
{
if ( dwMultiple % pNumbers[i] )
break;
}
if ( i == NumCount )
{
pOutNumbers[dwTemp++] = dwMultiple;
if ( dwTemp == dwOutCount )
{
return true;
}
}
}
return false;
}
Top
32 楼Icat（晨）回复于 2003-08-01 21:42:25 得分 2
for(i=2;i<=incount;i++)
a[0]=a[0]*a[i]/min(a[0],a[i]);
惭愧,没想到这样去做....Top
33 楼Icat（晨）回复于 2003-08-01 21:47:03 得分 2
狗狗的思路和龙龙不一样的哦,
请教狗狗,DWORD是32位的么?Top
34 楼MaiCle（原来小日本连畜生都不如）回复于 2003-08-01 21:49:58 得分 2
typedef unsigned long DWORD;Top
35 楼BinaryWorld（为实现中华软件产业自强而读书！）回复于 2003-08-01 21:53:02 得分 2
做个标志,先去吃饭.Top
36 楼Icat（晨）回复于 2003-08-01 21:54:16 得分 2
to MaiCle(【深圳，今夜请将我遗忘】)
谢谢;
to狗狗,先检查是否有偶数
如果有偶数的话,每次可以dwMultiple=dwMultiple+2的
那样稍微会快一点
^_^
我只会改小地方Top
37 楼kbsoft（让世界充满爱!）回复于 2003-08-01 22:49:43 得分 2
555...糊里糊涂的写了一个.这里没有编译器.所以没有编译过.哪位给看看.程序也没有优化,不过我想有很大的优化余地.
#include <afxwin.h>
#include <limits.h>
#include <stdlib.h>
#include <windows.h>
#include <iostream.h>
const int N=100; // Array 's MaxLength
bool flag;
int n,len,step=0;
unsigned long cm[20]; // Define the MaxLength of Common Multiple Array
unsigned long list[N],base,count;
unsigned long GCD(unsigned long a,unsigned long b)
{
unsigned long x,y,t;
x=a,y=b;
while(y!=0)
{
t=x%y;
x=y;
y=t;
}
return x;
}
void search()
{
if(list[0]*list[1]/GCD(list[0],list[1])<base)
{
cout<<"No solution!"<<endl;
return;
}
for(int j=1;j<=n;j++)
for(int i=1;i<len;i++)
{
if(list[i]&count==1)
count++;
else {
cm[step++]=count++; break;}
}
}
int main(void)
{
unsigned long s;
cout<<"Input a sequence of array: ";
for(int i=0;i<N;i++)
cin>>list[i];
cout<<"Input Base Number: ";
cin>>base;
count=base+1;
len=sizeof(list)/sizeof(LONG);
qsort(list,len,sizeof(LONG),''); //qsort最后一个参数是什么来着?忘了...
s=list[0]*list[1];
search();
for(int k=0;k<step;k++)
cout<<cm[k]<<" ";
cout<<endl;
return 0;
}Top
38 楼kbsoft（让世界充满爱!）回复于 2003-08-01 22:57:58 得分 2
上面那个有些问题。
#include <afxwin.h>
#include <limits.h>
#include <stdlib.h>
#include <windows.h>
#include <iostream.h>
const int N=100; // Array 's MaxLength
bool flag;
int n,len,step=0;
unsigned long cm[20]; // Define the MaxLength of Common Multiple Array
unsigned long list[N],base,count;
unsigned long GCD(unsigned long a,unsigned long b)
{
unsigned long x,y,t;
x=a,y=b;
while(y!=0)
{
t=x%y;
x=y;
y=t;
}
return x;
}
void search()
{
if(list[0]*list[1]/GCD(list[0],list[1])<base)
{
cout<<"No solution!"<<endl;
return;
}
for(int j=1;j<=n;j++)
{
for(int i=1;i<len;i++)
{
if(list[i]&count==1) {flag=false;
count++;}
else {flag=true;
continue;}
}
if(flag) cm[step++]=count++;
}
}
int main(void)
{
cout<<"Input a sequence of array: ";
for(int i=0;i<N;i++)
cin>>list[i];
cout<<"Input Base Number: ";
cin>>base;
count=base+1;
len=sizeof(list)/sizeof(LONG);
qsort(list,len,sizeof(LONG),0);
search();
for(int k=0;k<step;k++)
cout<<cm[k]<<" ";
cout<<endl;
return 0;
}Top
39 楼kbsoft（让世界充满爱!）回复于 2003-08-01 23:00:25 得分 2
其实这种题目，视输入数据的不同，效率而不同。以及base的值的大小。
不可能找到一个完美的快速算法!
Top
40 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-01 23:01:25 得分 0
kbsoft(景乐)：
写点注释哈，帮你改了半天，编过了，可是没结果Top
41 楼kbsoft（让世界充满爱!）回复于 2003-08-01 23:11:51 得分 2
还是说说我的算法吧。
1.先对给定的一组数据进行快速排序,花费O(nlogn)时间.
2.在搜索时判断一下给定的base是否小于LCM(list[0],list[1])就是最小的两个数据的最小公倍数,如果小于,那么肯定无解!
3.依次判断已排序数组的两两的大于base的公倍数:
先判断mul(list[0],list[1])的公倍数,然后再判断Mul(list[2],mul(list[0],list[1]))...依次类推直到Mul(list[len],mul(list[len-1],list[len-2]). mul()就是两个数的公倍数.如果都满足.那么则输出.否则,继续判断下一个.Top
42 楼kbsoft（让世界充满爱!）回复于 2003-08-01 23:13:06 得分 2
另外,对于unsigned long很大时,用位运算速度应该很快!Top
43 楼kbsoft（让世界充满爱!）回复于 2003-08-01 23:14:38 得分 2
时间仓促,没想更好的算法...等我回去再想想.Top
44 楼ckacka（/*小红帽*/ckacka();）回复于 2003-08-01 23:22:43 得分 2
很有意思！！：）
我也去想想Top
45 楼galoit（虎虎）回复于 2003-08-02 00:10:28 得分 2
我觉得你们的都有问题
至少有一点你们没考虑 因为 c++中的内在类型 都是有范围的
而 楼主问的问题没有提到这一点
刚一看 我觉得好难 阿
各位同行 能不能写出一个 能计算任意两个数的公倍数阿
一个挑战 呵呵Top
46 楼kbsoft（让世界充满爱!）回复于 2003-08-02 00:51:09 得分 2
哎。我上面的算法错误！！！
还是Dragon132的算法好，求出最小的倍数K，然后输出2k,3k,...nk就可以了。Top
47 楼Icat（晨）回复于 2003-08-02 03:31:40 得分 2
无聊中,,,把狗狗的的算法偷过来改了一下^_^,别打我
用上面的数据测试,结果是0.024614,当然,把177改成了176呵呵^_^不然就是0.05左右了
int check(DWORD *pNumbers,DWORD NumCount,DWORD *Max)
{
bool even=false;
if ( 0 == pNumbers || NumCount < 2)
return false;
for(int i=0;i<NumCount;++i)
{
if(!even)
even=!(pNumbers[i]%2);
if(pNumbers[i]>Max[1])
{
if(pNumbers[i]>Max[0])
{
Max[1]=Max[0];
Max[0]=pNumbers[i];
}else
{
Max[1]=pNumbers[i];
}
}
}
return(even);
//LOG(N)
}
bool CalcLCM( DWORD dwBase, DWORD *pNumbers, DWORD NumCount, DWORD *pOutNumbers, DWORD dwOutCount )
{
//TTimer t;
DWORD Max[2]={0,0};
DWORD dwLCM;
int even=check(pNumbers,NumCount,Max);
if ( 0 == pNumbers || NumCount < 2 || 0 == pOutNumbers || 0 == dwOutCount )
return false;
DWORD dwTemp = 0, i;
DWORD dwMultiple =LCM(Max[0],Max[1])-(LCM(Max[0],Max[1])%2);
for ( ; dwMultiple < 0xffffffffUL; dwMultiple+=1+even)
{
for ( i = 0; i < NumCount; i++ )
{
if ( dwMultiple % pNumbers[i] )
break;
}
if ( i == NumCount )
{
dwLCM=dwMultiple;
break;
}
}
for(int j=dwBase/dwLCM+1,k=0;j<dwBase/dwLCM+1+dwOutCount,k<dwOutCount;++j,++k)
{
pOutNumbers[k] = j*dwLCM;
}
return true;
}Top
48 楼Icat（晨）回复于 2003-08-02 03:35:41 得分 2
狗狗不介意的话,你在你上面再测试一下,谢谢
^_^Top
49 楼xingforever（星星）回复于 2003-08-02 09:31:48 得分 2
想法和Dragon132(Dragon)实在很接近，要赶火车，挪用了Dragon132(Dragon)一点东西，别介意啊：）
#include <iostream>
#define NMAX 100
using namespace std;
void fsort(unsigned long n,unsigned long a[NMAX]);
unsigned long amin(unsigned long a,unsigned long b);
void main()
{
unsigned long a[NMAX];
unsigned long aa;
unsigned long incount,outcount,base;
unsigned long i;
cout<<"Please enter the number N to count:";
cin>>incount;
cout<<"Please enter"<<incount<<"numbers:";
for(i=1;i<=incount;i++)
cin>>a[i];
fsort(incount,a);
aa = a[1];
for(i=2;i<=incount;i++)
{
if(aa % a[i]!=0)
aa=amin(aa,a[i]);
}
cout<<"Please enter the base number:";
cin>>base;
cout<<"Please enter the outcount of number:";
cin>>outcount;
for(i=base/aa+1;i<base/aa+1+outcount;i++)
cout<<i*aa<<endl;
}
void fsort(unsigned long n,unsigned long a[NMAX])
{
unsigned long t;
for(int i=1;i<=n-1;i++)
for(int j=1;j<=n-i;j++)
if(a[j]<a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
unsigned long amin(unsigned long a,unsigned long b)
{
unsigned long t;
if(a<b)
{
t=a;a=b;b=t;
}
int x=a;
int y=b;
while(x%y!=0)
{
t=x%y;
x=y;
y=t;
}
return a*b/y;
}
Top
50 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-02 10:13:58 得分 0
to Icat(晨)
你的代码好像有点问题，编译不过呀
LCM是什么？？递归调用？Top
51 楼fireseed（【VC无敌，英明神武，千秋万代，一统江湖！】—奶油狗）回复于 2003-08-02 10:18:14 得分 0
xingforever(星星)
你的代码也有错，不知道你测试过没有Top
52 楼0xff（）回复于 2003-08-02 10:35:53 得分 2
xingforever(星星)说他在VC下编译过了~没发现错误啊~结果和Dragon132(Dragon)的一样
现在他赶火车去了` : )Top
53 楼Icat（晨）回复于 2003-08-02 11:01:57 得分 0
to,狗狗
我的代码是在CB下写的,VC下没试过,
还有些代码没帖,在下面,主函数的不帖了
LCM是求两个数的最小公倍数
GCD是最大公因数
DWORD GCD(DWORD a,DWORD b)
{
DWORD T;
if(a<b)
{
T=a;a=b;b=T;
}
while(a%b)
{
T=a%b;
a=b;
b=T;
}
return b;
}
DWORD LCM(DWORD a,DWORD b)
{
return((a*b)/GCD(a,b));
}
昨天睡觉比较晚没保存,昏头了,呵呵
Top
54 楼echoher（Est Sularus oth Milthas）回复于 2003-08-02 11:12:04 得分 2
公约数函数：
int gy(const int& a, const int& b)
{
int ret = 1;
int x = max(a,b);
int y = min(a,b);
for(int i=1;i<=sqrt(x);++i)
{
if( (y%i == 0) && (x%i==0) )
ret = i;
}
return ret;
}
公倍数函数：
int gb(const int&a, const int&b)
{
return a*b/gy(a,b);
}
主函数
int main()
{
int buff[100];
int gbs=1;
//input
for(int i=0;i<100;i++)
{
gbs = gb(gbs,buff[i]);
}
//output
}Top
55 楼shinedreamnt（白日梦nt）回复于 2003-08-02 12:03:04 得分 2
我的思路,要想最快,就最好避免乘法和除法,
先找出最小公倍数X,其它的公倍数就是X*2,X*3,X*4...排下去.
而找A,B的最小公倍数可以,建立数组或vector,AA[B],BB[A],CC[A+B]
元素分别为AA[i]=AA[i-1]+A;BB[i]=BB[i-1]+B;
CC是两者的并集,找出CC中重复的就可以了.
这样的算法是否会快些???
有时间我再完成程序.Top
56 楼Icat（晨）回复于 2003-08-02 12:08:03 得分 2
请问楼上的,求最小公倍数怎么样才能避免乘除?位运算?
这个题目最重要的还是求最小公倍数啊^_^Top
57 楼0xff（）回复于 2003-08-02 12:40:50 得分 2
我也来改一下~
原理：用所有数的乘积除以它们的最大公约数就是最小公倍数
#include <windows.h>
#include <iostream>
#define NMAX 100
using namespace std;
class CTimer
{
public:
CTimer() {QueryPerformanceFrequency(&m_Frequency); Start();}
void Start() {QueryPerformanceCounter(&m_StartCount);}
double End()
{
LARGE_INTEGER CurrentCount;QueryPerformanceCounter(&CurrentCount);
return double(CurrentCount.LowPart - m_StartCount.LowPart) / (double)m_Frequency.LowPart;
}
private:
LARGE_INTEGER m_Frequency;
LARGE_INTEGER m_StartCount;
};
unsigned long amin(unsigned long a,unsigned long b);
void main()
{
unsigned long a[NMAX];
unsigned long aa;
unsigned long incount,outcount,base;
unsigned long i;
unsigned long mm;
CTimer t;
cout<<"Please enter the number N to count:";
cin>>incount;
cout<<"Please enter"<<incount<<"numbers:"<<endl;
for(i=0;i<incount;i++)
cin>>a[i];
cout<<"Please enter the base number:";
cin>>base;
cout<<"Please enter the outcount of number:";
cin>>outcount;
t.Start();
mm = aa = a[0];
for(i=1;i<incount;i++)
{
aa = amin(aa,a[i]);
mm = mm*a[i];
}
aa = mm/aa;
cout<<"Time:"<<t.End()<<endl;
for(i=base/aa+1;i<base/aa+1+outcount;i++)
cout<<i*aa<<endl;
}
unsigned long amin(unsigned long a,unsigned long b)
{
unsigned long t;
if(a<b)
{
t=a;a=b;b=t;
}
while ( a%b!=0 )
b = a%b;
return b;
}Top
58 楼Icat（晨）回复于 2003-08-02 13:40:55 得分 2
to,0xff()
这我想过,,但是非常容易溢出,,呵呵
感觉还是Dragon的算法好
a[0]=a[1];
for(i=2;i<=incount;i++)
a[0]=a[0]*a[i]/min(a[0],a[i]);Top
59 楼Icat（晨）回复于 2003-08-02 13:59:02 得分 2
要回家了,先Mark,过几天回来再看看Top
60 楼shinedreamnt（白日梦nt）回复于 2003-08-02 14:18:05 得分 2
写好了没有考虑到overflow .
对于多个数的最小公倍数,可以用迭代的办法计算
min=calcMin(calcMin(a,b),c) ;
不知道计算速度怎么样,希望得到大家指点.
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std ;
int calcMin(int a,int b)
{
int i,iA=0;
vector<int> v(a) ;
vector<int>::const_iterator p ;
v[0] = b ;
for (i=1;i<a ;i++)
v[i]=v[i-1]+b ;
for (i=0;i<a;i++)
{
iA += a ;
p=find(v.begin(),v.end(),iA) ;
if (p != v.end())
return iA ;
}
return 0;
}
void main ()
{
int x,y ;
cout << "please input 2 integer"<<endl ;
cin >> x >> y ;
cout<<"min GongBeiShu is "<<calcMin(x,y)<<endl ;
cout<<"finished "; //finished for set breakpint
}
Top
61 楼sugrong（sam）回复于 2003-08-02 14:30:30 得分 2
我已经很长时间不做了
不过我的建议是为什么不先判断奇偶呢
然后用乘除的办法
不过我的想法对多个数有点麻烦Top
62 楼shinedreamnt（白日梦nt）回复于 2003-08-02 14:31:25 得分 2
sorry,忘记调试一下了,现在可以用了,
把这个求两数最小公倍数函数改改就符合楼主要求了.
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std ;
int calcMin(int a,int b)
{//返回a,b的最小公倍数
int i,iA=0;
vector<long> v(a) ;
vector<long>::const_iterator p ;
v[0] = b ;
for (i=1;i<a ;i++)
v[i]=v[i-1]+b ;
for (i=0;i<b;i++)
{
iA += a ;
p=find(v.begin(),v.end(),iA) ;
if (
( p != v.end() ) &&
( i < b - 1 ))
return iA ;
}
return iA;
}
void main ()
{
int x,y ;
cout << "please input 2 integer"<<endl ;
cin >> x >> y ;
cout<<"min GongBeiShu is "<<calcMin(x,y)<<endl ;
cout<<"finished "; //finished for set breakpint
}
Top
63 楼WindsonZhL（风之子）回复于 2003-08-02 14:44:53 得分 2
本题的关键是求两数的最小公倍数。下面给出一个应该是最优的算法。
int lcm( int m, int n)
{
if( m > n ) { m^=n; n^=m; m^=n } //保证n是大数，m是小数。
if( n%m == 0 ) return n; //n是m的倍数
else if( m % ( n%m ) ==0 ) return m * n / ( n%m ); //m与n有公约数
else return m * n; //m与n没有公约数
}Top
64 楼WindsonZhL（风之子）回复于 2003-08-02 14:50:21 得分 2
别忘了，vector可是个类，再加上泛型算法，未必就比乘除法来得快。Top
65 楼wkoji（杨威利）回复于 2003-08-02 14:52:49 得分 2
markTop
66 楼shinedreamnt（白日梦nt）回复于 2003-08-02 15:04:03 得分 2
to WindsonZhL(风之子)
你的算法不对的,
m=33,n=55,结果应该是5*3*11=165.
你的计算结果为...
上面的最大公约数的计算用的是辗转相除法,是正确的.
可以把vector改成数组,再实现find函数,对于已经排序的数组find应该很快的.Top
67 楼WindsonZhL（风之子）回复于 2003-08-02 15:37:29 得分 2
订正一下：
int lcm( int m, int n)
{
if( m > n ) { m^=n; n^=m; m^=n } //保证n是大数，m是小数。
if( n%m == 0 ) return n; //n是m的倍数
else if( m % ( n%m ) ==0 ) return m * n / ( n%m );
//m与n不同是最大公约数的奇数倍
else if((n%m)%(m%(n%m))==0) return n*lcm(m, n%m)/(n%m);
//m与n同是最大公约数的奇数倍
else return m * n; //m与n没有公约数
}
Top
68 楼WindsonZhL（风之子）回复于 2003-08-02 15:52:13 得分 2
我的方法应该说是脱胎于Dragon132(Dragon)的方法(某本教材上的习题答案)。
如果m与n一个是最大公约数的奇数倍，一个是偶数倍，两者等效，但我认为分支比循环快。
而且我的方法节约了中间变量t 。
但开始我未考虑到m与n都是最大公约数奇数倍的情况，这种情况不用循环就只能用递归了。
考虑到两个奇数间一定相差一个偶数，则m与n%m必定是一个奇数倍、一个偶数倍。Top
69 楼shinedreamnt（白日梦nt）回复于 2003-08-02 16:36:03 得分 2
sorry ,still wrong !!!
n=96,m=75?
n%m=21
m%(n%m)=12
Dragon132(Dragon)开始用的是辗转相除法计算最大公约数.
while(a%b)
{
t=a%b;
a=b;
b=t;
}
你可以把他改成递归,担我觉得不容易理解.
Dragon132(Dragon)后来用的是减化的方法计算最小公倍数,和我的原理是一致的
Top
70 楼wide288（鱼）回复于 2003-08-02 17:00:30 得分 2
Dragon132(Dragon) 我的测试：
$ time ./gongbei
Please enter the number N to count:3
Please enter 3 number:127
133
159
Please enter the base number:1
Please enter the outcount of number:5
2685669
5371338
8057007
10742676
13428345
real 0m24.960s
user 0m0.000s
sys 0m0.000s
$
Top
71 楼zoezinsser（wealth）回复于 2003-08-03 10:34:28 得分 2
我也想了一下，算不上最简，但可以参考一下：
思想：
1，利用数组元素的最大元素与边界值判断，检查参数；
2，利用循环判断temp是否为公倍数，并修改标志flag；
用在边界值和最大元素之间的数除数组中的每个元素，余数为零则为公倍数，并修改标志；
3，打印公倍数。
int cmd(unsiged long array[] , int arrsize , unsiged long bndvalue , int count)
{
unsiged long flag = 0;
unsiged long temp = 0 ， maxvalue = 0;
register int j = 0;
//求最大值
maxvalue = array[0];
for (j = 0 ; j < arrsize ; j++)
{
if (array[j] > maxvalue)
{
maxvalue = array[j];
}
}
//检查参数
if (maxvalue > bndvalue)
{
printf("参数错误");
return FALSE;
}
//找公倍数
count = 0;
for (temp = bndvalue ; temp > maxvalue ; )
{
flag = 0;
for (j = 0 ; j < arrsize ; j++)
{
if (i % a[j] == 0)
{
flag++;//修改标志
}
}
if (flag == temp)
{
printf("%d",temp);//打印
count++;
}
temp = temp - maxvalue;//修改测试元素范围
}
}Top
72 楼witcheese（狗餅）回复于 2003-08-03 11:25:06 得分 2
加油!!!Top
73 楼Kaye（菜到几时）回复于 2003-08-03 16:28:31 得分 2
不如改成求1-10000的最小公倍数吧,这样才比较有意思Top
74 楼crcr（游侠）回复于 2003-08-03 17:46:37 得分 2
等会儿Top
75 楼crcr（游侠）回复于 2003-08-03 19:38:03 得分 2
#include<stdio.h>
int number[20];
int gy(int x,int y);
int gys_max(int no,int p,int i,int n1);
int gbs_min(int no,int p,int i,int n1);
void main()
{
int i=0,p=0,max,min;
printf("请输入若干整型数(小于20个),结束标志为ctrl+z!\n");
while(scanf("%d",&number[i])!=EOF)
i++;
p=i-1;
i=0;
max=gys_max(number[0],number[1],i,p);
printf("最大的公约数=%d\n",max);
min=gbs_min(number[0],number[1],i,p);
printf("最小的公倍数为=%d\n",min);
}
int gys_max(int no,int p,int i,int lebel)
{
int p1;
p1=gy(no,p);
if(i==lebel)
return p1;
else if(i==0)
i+=2;
else
i++;
no=number[i];
gys_max(no,p1,i,lebel);
}
int gbs_min(int no,int p,int i,int lebel)
{
int p1,p2;
p1=gy(no,p);
p2=no*p/p1;
if(i==lebel)
return p2;
else if(i==0)
i+=2;
else
i++;
no=number[i];
gbs_min(no,p2,i,lebel);
}
int gy(int m,int n)
{
int m1,r;
if(m<n)
{
m1=m;
m=n;
n=m1;
}
r=m%n;
while(r!=0)
{
m=n;
n=r;
r=m%n;
}
return (n);
}
Top
76 楼leechongqing（李重庆）回复于 2003-08-03 21:22:47 得分 2
呵呵，有现成的算法的，可以自己找一下，
1，先找出最小公约数
2。在找出最大公倍数3
3。。。。。。。。。。Top
77 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-08-04 00:19:51 得分 2
怎么稀奇古怪的一大堆东东???不是很简单的吗?很显然的,因为3个数{a,b,c}求其最小共倍数,是集合{a,b,c}中任意取两个求最小公倍数再和剩下的那个再求一个,据此可以建立递推关系.如果有N个数,只要如此比较N-1次即可.而且比较各种算法效率需要有个标准,比如都在渐进下,是可以证明最优算法和求最大公约数的效率是线性关系(N-1倍).Top
78 楼ZZH1983（ZZH）回复于 2003-08-04 09:45:11 得分 2
to fireseed (奶油狗)
不好意思，不过我最感兴趣的是你是怎样把运算时间算出来的？
能不能把算时间那一部分的源码贴出来？Top
79 楼bigtea（企鹅）回复于 2003-08-04 12:26:38 得分 2
先把思路写出来。
如果从效率考虑，就应该考虑是一个较长并且有大数的数组，就把数据类型设为long int型.
则先要对数组按排序递增顺序排序（注意剔除重复及小数能被大数整除的小数)
void sort_ascend(long [],int ),
然后从数组两边取元素(即先取最小和最大的元素，直至中间的一个或两个元素,
这样可以减少最少公倍数函数
long lcm(long ,long)
辗转相除的次数)。
剩下的处理就跟Dragon132(Dragon)的差不多了，其实输出一个即可，多个不过是按倍数递增。
附:关于最少公倍数函数其实不需要判断两个输入参数的大小，%运算自身的特性会将大、小数调转。
例:3 ,5 在做循环时
t=a%b;
a=b;
b=t;
3,5会自动互换。Top
80 楼chinajiji（菜鸟叽叽）回复于 2003-08-05 00:16:22 得分 2
如果是求n个正整数的最在公约数,我倒是有个很快的方法,但求n正整数目前我能想到的最好算法是:
1.去掉n个正整数中的重复元素和1.
2.先求出array[0] 与 array[1]的最小公倍数,设为lcm1,
3.计算lcm1与array[2]的最小倍数lcm2
...
4. 计算lcm_(n-1) 与 array[n-1]的最小公倍数,得到最后结果.
5. 不用排序.
6.对于"先求n个整数的最大公约数后,再用每个数除这个最大公约数的方法来求N个正整数的最小公倍数"的方法是错误的.
7.上述算法的效率是:O{(n-1)*f}; f 是求两个正整数的最大约数的效率.f 与参与运算的两个整数有关,效率大致是O(log{min: n1, n2}),也就是说f用辗转相除法还是比较快的.
bigtea(企鹅) 说:
1.然后从数组两边取元素(即先取最小和最大的元素，直至中间的一个或两个元素,
这样可以减少最少公倍数函数
long lcm(long ,long)
辗转相除的次数)。
////////////////////////////
在理论上可能快一点,但实际提高可能并不显著
2.
附:关于最少公倍数函数其实不需要判断两个输入参数的大小，%运算自身的特性会将大、小数调转。
////////////////////////////
可行,但比判断两个输入参数的大小后再运算的方法反而要慢.
Top
81 楼chinajiji（菜鸟叽叽）回复于 2003-08-05 00:50:14 得分 2
如果已知N个已排好序的正整数中的最小合数，可以有更快的算法，前提是N比较大。
比如：
3, 4, 6, 8;
最小合数是4;
一。将最小合数4分解成2*2,得到：
3, （2，2）, 6, 8;
二. 将最小合数4的每个组成数（这里是2,2)依次除最小合数4之后的每个数，得；
第一个2来除：
3, （2，2）, 6/2 = 3 , 8 / 2 = 4;
第二个2来除：
3, （2，2）, 3/2 -> 3（不能整除的数不变！） , 4 / 2 = 2;
三，得到4,6,8的最小公倍数是：2*2*3*2=24；
四，用前贴所述方法得最后的结果：
lcm(3,24) = 24.
说明，上述方法没有经过严格证明。只有已知在N个已排好序的正整数中的最小合数且N值大的情况下，才可能比我前贴所说的方法快。
///////////////////////////
最理想的方法是将辗转相除法推广到N个正整数中去。
谁来解决这个难题？我给200分。
///////////////////////////////////
背景资料：
据我所知：fireseed (奶油狗) 在水园的名气很大。Top
82 楼Dragon132（飞龙在天）回复于 2003-08-05 11:13:37 得分 2
to chinajiji(菜鸟叽叽)
辗转相除是求最大公约数的，N个数中最大公约数和最小公倍数已不存在乘积和原数乘积相等的情况了，你想怎样实现“将辗转相除法推广到N个正整数中去”啊？Top
83 楼kkkwww（期望完全）回复于 2003-08-05 11:21:50 得分 2
你要这有何用？可否告知一二？Top
84 楼aimheliopause（voyager）回复于 2003-08-05 11:29:23 得分 2
通过求最大公约数在乘每个数和其之比值求出的并不一定是最小公倍数，
请看：2，3，6的最大公约数是1，但是他们的最小公倍数并不是1*（2/1）*（3/1）*（6/1）
而是6。
所以这个问题应当是两两相求最小公倍数，做法是：
如果求（a1,a2,a3,...)的最小公倍数
先求两个最小数(a1,a2)的（辗转相除）最大公约数记为c，这两个数的最小公倍数d=c*(a/c)*(b/c);
在用d同另一个次小的数a3的最小公倍数，依次类推，这样的算法应当还可以优化。Top
85 楼bigtea（企鹅）回复于 2003-08-05 11:49:23 得分 2
先把代码贴出来，下帖回chinajiji(菜鸟叽叽) 的讨论。
#include <stdio.h>
#define N 10
int main(void)
/*程序功能:求一组数据的最小公倍数*/
/*算法说明:
1.对数组进行递增排序，并将能互相整除的两个数中的小数剔除;
2.从排序后的最右边两个数开始(即最大两个数)求得最小公倍数，
然后与下一个数 组对再求，依次向左直到'有效数'求完。
最后求得的最小公倍数即为整个数组的最小公倍数。
*/
{
void sort_ascend(unsigned [],int );
unsigned long gcd(unsigned long,unsigned long);
void n_lcm(unsigned [],int,unsigned long,int );
unsigned num[N]={4,6,61464,7,512,567,1,32567,6668,12};
n_lcm(num,N,65535,3);
return 0;
}
void n_lcm(unsigned num[],int n,unsigned long bas,int cnt)
{
int i,j;
unsigned long tmp;
sort_ascend(num,n);
for (i=0;1==num[i];i++) /*把排除的数略过*/
;
for (tmp=num[n-1],j=n-2;j>=i;j--)
/*根据lcm(a,b)=a*b/gcd(a,b)*/
tmp=tmp*num[j]/gcd(tmp,num[j]);
if (tmp<bas) {printf("lcm <base\n");return;}
for (i=1;i<=cnt;i++)
printf("%lu ",i*tmp);
printf("\n");
}
void sort_ascend(unsigned a[],int n)
{/*对数组递增排序,将能互相整除两数中的小数剔除*/
int i,j;
int tmp;
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
{
if ( a[i]>a[j]) {tmp=a[i];a[i]=a[j];a[j]=tmp;}
if (a[j]%a[i]==0) a[i]=1;
}
}
unsigned long gcd(unsigned long a,unsigned long b)
{/*辗转相除法求最大公约数*/
unsigned long tmp;
/*因为调用时，都是大数在前，不需要判断大小
即使小数在前也不会出错，详解我与chinajiji(菜鸟叽叽)
的有关讨论*/
while(tmp=a%b){
a=b;
b=tmp;
}
return b;
}
Top
86 楼wingfiring（非典型秃子）回复于 2003-08-05 13:24:04 得分 2
我这里也利用了辗转相除法，狗狗看一下在你的机器上运行时间是多少。
#include <iostream>
#include <algorithm>
#include <cassert>
inline int max_gy(int a, int b)
{
assert(a > 1 && b > 1);
if (a < b) std::swap(a, b);
int r;
while ((r = a%b) >0)
{
a = b;
b = r;
}
return b;
}
//arr,in:输入数据和个数 out,on:输出数据和个数
void min_ngb(int arr[], int in, int out[], int on)
{
assert( in > 1 && on > 0 && arr != NULL && out != NULL);
int r = arr[0];
int i;
for (i = 1; i < in; i++)
r = r/max_gy(r, arr[i]) * arr[i];
out[0] = r;
for (i = 1; i < on ; i++)
out[i] = out[i-1] + r;
}
int main()
{
int arr[3]={127,133,159};
int out[5];
min_ngb(arr,3,out,5);
for (int i = 0; i < 5;i++)
std::cout << out[i] <<std::endl;
return 0;
}
我的编译命令行是：
cl /GX /Ob2 /O2 /Og -DNDEBUG aa.cppTop
87 楼wingfiring（非典型秃子）回复于 2003-08-05 13:38:03 得分 2
#include <iostream>
#include <algorithm>
#include <cassert>
inline int max_gy(int a, int b)
{
assert(a > 1 && b > 1);
if (a < b) std::swap(a, b);
int r;
while ((r = a%b) >0)
{
a = b;
b = r;
}
return b;
}
void min_ngb(int arr[], int in, int out[], int on)
{
assert( in > 1 && on > 0 && arr != NULL && out != NULL);
int r = arr[0];
int i;
for (i = 1; i < in; i++)
r = r * arr[i] / max_gy(r, arr[i]);
out[0] = r;
for (i = 1; i < on ; i++)
out[i] = out[i-1] + r;
}
int main()
{
int arr[3]={127,133,159};
int out[5];
min_ngb(arr,3,out,5);
for (int i = 0; i < 5;i++)
std::cout << out[i] <<std::endl;
return 0;
}Top
88 楼njuhuangmy（茶）回复于 2003-08-05 14:08:17 得分 2
暂时 不考虑 具体的 实现， 也就是 详细的 先不考虑
下面 是 我认为 最 简单的 算法， 程序 我稍微 考虑了 一下 ，认为 是
比较 好写 的， 结构 也好 设计， 我求 n 个数里面的 最小公倍数
1. 输入 //这是所有的步骤里面都有必要的
2. 排序 按照从大到小的顺序排序。
{ // 主体
3. 使 最小公倍数的变量 hehe = 最大的数
并使用它去除以第二个数，
不能除尽， 求最大的和第二大的数的最小公倍数，赋值给hehe
能除尽， 不做任何事，继续下面的
4. hehe， 除第三个最大的数， 重复 上面的过程....
}
5. 结束条件 该数为1 或者，已经到了最后一个
好像 写的 很简单 啊， 不知道 能不能达到 高效率呢
建议 测试的 时候 ， 多输入几个数， 或者 不考虑大数的情况下
不妨 做 1, 2 ,3 ,4 .... 10 的测试，Top
89 楼njuhuangmy（茶）回复于 2003-08-05 14:11:52 得分 2
暂时 不考虑 具体的 实现， 也就是 详细的 先不考虑
下面 是 我认为 最 简单的 算法， 程序 我稍微 考虑了 一下 ，认为 是
比较 好写 的， 结构 也好 设计， 我求 n 个数里面的 最小公倍数
1. 输入 //这是所有的步骤里面都有必要的
2. 排序 按照从大到小的顺序排序。
{ // 主体
3. 使 最小公倍数的变量 hehe = 最大的数
并使用它去除以第二个数，
不能除尽， 求最大的和第二大的数的最小公倍数，赋值给hehe
能除尽， 不做任何事，继续下面的
4. hehe， 除第三个最大的数， 重复 上面的过程....
}
5. 结束条件 该数为1 或者，已经到了最后一个
好像 写的 很简单 啊， 不知道 能不能达到 高效率呢
建议 测试的 时候 ， 多输入几个数， 或者 不考虑大数的情况下
不妨 做 1, 2 ,3 ,4 .... 10 的测试Top
90 楼wingfiring（非典型秃子）回复于 2003-08-05 14:13:47 得分 2
呵呵，我在自己的机器上测了一下，运算区域min_ngb的运行时间是0.000000606s
我的机器是赛杨1G.
测时间的函数如下：
inline unsigned __int64 GetCycleCount()
{
__asm _emit 0x0F
__asm _emit 0x31
}Top
91 楼njuhuangmy（茶）回复于 2003-08-05 14:17:42 得分 2
上面 说错 了 一点点
根本 就 用不着去除，在求最小公倍数（使用最大公约数）的时候，就内置了
先 除Top
92 楼zoezinsser（wealth）回复于 2003-08-05 21:30:29 得分 2
我觉得把边界值考虑进去效率会提高的！Top
93 楼njuhuangmy（茶）回复于 2003-08-05 22:33:02 得分 2
算法
1. 读入
2. 降序排序
3.
i = 0;
fewest = a[0];
如果 不是 最后一个 或者 a[i+1] == 1
fewest = 最小公倍数（fewest , a[i+1]）
i++
4. 输出
Top
94 楼chon81（当我遇上你…）回复于 2003-08-06 01:59:56 得分 2
小弟也现丑了.是不是求最小公倍数啊.
#include "stdio.h"
#include "math.h"
#include "conio.h"
unsigned long min(unsigned int arr[],unsigned int len)
{
unsigned int i;
unsigned long m=1,maxmul=1;
for(i=0;i<len;i++)
maxmul*=arr[i];
i=2;
while(i<=maxmul)
{
if(maxmul%i==0)
{
int n,j=0;
while(maxmul%i==0)
{
maxmul=maxmul/i;
j++;
}
for(n=0;n<len;n++)
{
int a=0;
int temp=arr[n];
while(temp%i==0)
{
a++;
temp=temp/i;
}
if(a>i)
j=a;
}
while(j--)
m*=i;
}
i+=(i==2?1:2);
}
return m;
}
void main()
{
unsigned int a[]={4,3,5,7,11,13,17};
printf("最小公因数为%d\nend ",min(a,7));
getch();
}Top
95 楼bigtea（企鹅）回复于 2003-08-06 09:09:50 得分 2
略过这么多了，再贴一下，下贴回 chinajiji(菜鸟叽叽)
#include <stdio.h>
#define N 10
int main(void)
/*程序功能:求一组数据的最小公倍数*/
/*算法说明:
1.对数组进行递增排序，并将能互相整除的两个数中的小数剔除;
2.从排序后的最右边两个数开始(即最大两个数)求得最小公倍数，
然后与下一个数 组对再求，依次向左直到'有效数'求完。
最后求得的最小公倍数即为整个数组的最小公倍数。
*/
{
void sort_ascend(unsigned [],int );
unsigned long gcd(unsigned long,unsigned long);
void n_lcm(unsigned [],int,unsigned long,int );
unsigned num[N]={4,6,61464,7,512,567,1,32567,6668,12};
n_lcm(num,N,65535,3);
return 0;
}
void n_lcm(unsigned num[],int n,unsigned long bas,int cnt)
{
int i,j;
unsigned long tmp;
sort_ascend(num,n);
for (i=0;1==num[i];i++) /*把排除的数略过*/
;
for (tmp=num[n-1],j=n-2;j>=i;j--)
/*根据lcm(a,b)=a*b/gcd(a,b)*/
tmp=tmp*num[j]/gcd(tmp,num[j]);
if (tmp<bas) {printf("lcm <base\n");return;}
for (i=1;i<=cnt;i++)
printf("%lu ",i*tmp);
printf("\n");
}
void sort_ascend(unsigned a[],int n)
{/*对数组递增排序,将能互相整除两数中的小数剔除*/
int i,j;
unsigned tmp;
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
{
if ( a[i]>a[j]) {tmp=a[i];a[i]=a[j];a[j]=tmp;}
if (a[j]%a[i]==0) a[i]=1;
}
}
unsigned long gcd(unsigned long a,unsigned long b)
{/*辗转相除法求最大公约数*/
unsigned long tmp;
/*因为调用时，都是大数在前，不需要判断大小
即使小数在前也不会出错，详解我与chinajiji(菜鸟叽叽)
的有关讨论*/
while(tmp=a%b){
a=b;
b=tmp;
}
return b;
}
Top
96 楼bigtea（企鹅）回复于 2003-08-06 09:25:02 得分 2
chinajiji(菜鸟叽叽)说道:
如果是求n个正整数的最在公约数,我倒是有个很快的方法,但求n正整数目前我能想到的最好算法是:
1.去掉n个正整数中的重复元素和1.
2.先求出array[0] 与 array[1]的最小公倍数,设为lcm1,
3.计算lcm1与array[2]的最小倍数lcm2
...
4. 计算lcm_(n-1) 与 array[n-1]的最小公倍数,得到最后结果.
5. 不用排序.
6.对于"先求n个整数的最大公约数后,再用每个数除这个最大公约数的方法来求N个正整数的最小公倍数"的方法是错误的.
7.上述算法的效率是:O{(n-1)*f}; f 是求两个正整数的最大约数的效率.f 与参与运算的两个整数有关,效率大致是O(log{min: n1, n2}),也就是说f用辗转相除法还是比较快的.
bigtea(企鹅) 说:
1.然后从数组两边取元素(即先取最小和最大的元素，直至中间的一个或两个元素,
这样可以减少最少公倍数函数
long lcm(long ,long)
辗转相除的次数)。
////////////////////////////
在理论上可能快一点,但实际提高可能并不显著
2.
附:关于最少公倍数函数其实不需要判断两个输入参数的大小，%运算自身的特性会将大、小数调转。
////////////////////////////
可行,但比判断两个输入参数的大小后再运算的方法反而要慢.
o chinajiji(菜鸟叽叽) ;
回复你第一贴的内容。
1.总体思路接近，即先对数组做处理。最大的不同你说不用排序。
假设数组num[10]={4,6,61464,7,512,567,1,32567,6668,12};
我想这组数据比较有代表性。
如果不排序，仅剔除能整除两数中的小的数,则
num[10]={1,1,61464,1,512,567,1,32567,6668,12}
而排序后的为
num[10]={1,1,1,1,12,512,567,6668,32567,61464}
同时按照你说得从左进行是lcm(lcm(lcm(lcm(1,1),61464),1),512),再与6668等求最少公倍数。其实会包含很多多余计算，因为
lcm(lcm(61464,32567),6668)能整除512的可能性极大。
还不包括用标志位1来略过的求最少公倍数复杂计算的次数。
所以说，在一般情况下，虽然排序和剔除数花费了一些时间，但会减少%运算的次数。
2.关于在辗转相除法的不需比较大小的问题，同意你的说法，只是代码简化，但会提高执行时间。
Top
97 楼wingfiring（非典型秃子）回复于 2003-08-06 13:42:25 得分 2
讨论：
首先是求出所有数的最小公倍数。
两个数的最小公倍数是容易的：g(a,b) = a*b/f(a,b), f是a,b的最大公约数。
然后，用这个最小公倍数公式，例如还有c,则最小公倍数公式就是：g(g(a,b), c),不难看出，这是个简单的迭代过程。
其次是求出若干个最小的公倍数，这个很简单，只要把最小公倍数累加若干次就可以了，不存在是公倍数，但又不是最小公倍数的整数倍的情况。
对楼上几位性能的分析，这里只分析算法，不分析代码。
>1.去掉n个正整数中的重复元素和1.
一般来说，去掉重复元素意味着要排序，这需要额外的存储和时间开销，而排序的开销是相当大的，平均复杂度是O(Nlog2N)。而不排序，无非是：对于每一次重复，求公约数多做一次模运算和两次比较，求公倍数多做一次乘法和除法。很显然，这里最多是线性复杂度(n-2)/2。
>2.辗转相除的效率
辗转相除的效率是很高的， Dragon132用循环肯定赶不上的。
>3.关于最少公倍数函数其实不需要判断两个输入参数的大小
如果不判断，顺序正确的时候，节约一次比较。
错误的时候浪费一次求模的操作。从经验上看，求模的操作开销不大会小于比较。
假如发生的概率各半，似乎不比较会浪费时间。
但是从公式g(g(a,b), c)来看，g(a,b) > c的概率也是会很大的，尤其是当迭代次数增加以后,"发生的概率各半"的假设未必正确。
所以结论是难以判断，需要实际的数值来统计。Top
98 楼njuhuangmy（茶）回复于 2003-08-06 20:02:57 得分 2
为何 都没人 看我得 算法
呜呜Top
99 楼chinajiji（菜鸟叽叽）回复于 2003-08-07 01:05:38 得分 2
赞同wingfiring(别逗了)!高!Top
100 楼chinajiji（菜鸟叽叽）回复于 2003-08-07 01:06:08 得分 2
赞同wingfiring(别逗了)! 高!
我认为求最大公约数的最好算法gcd(x1,x2) 是O(logN) N= min{x1,x2},不知对不对?
我认为最少公倍数函数其实不需要判断两个输入参数的大小问题:
错误的时候不仅浪费一次求模的操作,而且还有while循环语句,虽然它花时很小.Top
101 楼wingfiring（非典型秃子）回复于 2003-08-07 09:37:55 得分 0
chinajiji(菜鸟叽叽)的O(logN) N= min{x1,x2}的复杂度我不知道你是怎么算出来的。
关于辗转相除法的复杂度问题我不知道怎么估算，但是我认为应该小于logN.log的底数为2。原因是2是最小的一个质数，辗转相除的时候，除以2，和1这两次有限运算达到这一复杂度，大部分时候来说会除一个比较大的数，显然，这个运算的时间复杂度应该是小于logN的。对于一对足够大的数字来说，即使是其最坏效率也不可能达到logN。
这个复杂度推算起来似乎也可以做到，就是分析余数大小分布的概率，但还要考虑到是否是合数、能否整除等等情况，感觉有点复杂，可能要用到一些比较难的数学知识。
楼上提到while循环语句的开销，确实是我没注意到，够细心的呀：）
其实这个分析也都是机遇逻辑上的一些分析，实际上，还可以分析从存储器读取、写入数据的开销。
所以，我的程序应该把int改成register,应该也会提高一点效率。Top
102 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-08-07 16:50:45 得分 2
怎么没人看我上面的回答???算法和 wingfiring是一样的.gcd(x1,x2) 是O(logN) N= max{x1,x2},利用初等数论可以证明.最优的算法应该是O(Nlog(Max(a,b)),此外讨论代码最优化没什么意义,还不如直接用汇编呢...
很显然的,因为3个数{a,b,c}求其最小共倍数,是集合{a,b,c}中任意取两个求最小公倍数再和剩下的那个再求一个,据此可以建立递推关系.如果有N个数,只要如此比较N-1次即可.而且比较各种算法效率需要有个标准,比如都在渐进下,是可以证明最优算法和求最大公约数的效率是线性关系(N-1倍).Top
103 楼wingfiring（非典型秃子）回复于 2003-08-07 17:33:31 得分 2
to ZhangYv(闭关修炼中):
>gcd(x1,x2) 是O(logN) N= max{x1,x2},
这个怎么来的？我觉得不对吧？
>利用初等数论可以证明.最优的算法应该是O(Nlog(Max(a,b))
怎么证明啊，我想知道。
我对数论一知半解：（Top
104 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-08-07 18:03:27 得分 2
O(logN) N= max{x1,x2}怎么不对? 可以利用初等数论中的一个定理：
GCD( a , b ) = GCD( a , b-a ) = GCD( a , b-2*a ) = GCD( a , b-3*a ) = … = GCD( a , b mod a )关于这个定理的具体证明，及其对辗转相除的时间复杂度推导过程请参考初等数论书.我写一个程序终结这次讨论好了...
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
long GCD(long a, long b)
{
E1: a = a % b;
if (!a) return b;
b = b % a;
if (!b) return a;
else goto E1;
}
void main()
{
srand((unsigned)time(NULL));
const int N = 5;
int i, last = N;
int d[N];
long f;
for (i = 0; i < N; i++){
d[i] = rand()%100+1; //防止long型上溢出
//scanf("%d", &d[i]);
printf("%d ", d[i]);
}//Initialize();
printf("\n");
for (i = 1, f = d[0]; i < N; i++)
f *= d[i] / GCD(f, d[i]);
printf("The Least Comman Multiply = %ld", f);
system("pause");
}Top
105 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-08-07 18:09:34 得分 2
上面没经过测试时间,数据范围也太小.但肯定是渐进最优的,算法分析我在上面就说明了,实际上容易推出存在递推关系.Top
106 楼wingfiring（非典型秃子）回复于 2003-08-07 19:46:57 得分 2
楼上的求公约数的函数效率确实高，佩服！
不过，GCD( a , b ) = GCD( a , b-a ) = GCD( a , b-2*a ) = GCD( a , b-3*a ) = … = GCD( a , b mod a )这个公式只是证明了辗转相除法，没有说明复杂度。
关于O(logN) N= max{x1,x2}复杂度的问题，决不可能是正确的。
很简单：假定GCD( a , b )出结果需要迭代N次，N足够大（>>2)。第一次迭代的结