| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2816 人关注过本帖
标题:[算法]高效求最大公约数
只看楼主 加入收藏
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
 问题点数:0 回复次数:11 
[算法]高效求最大公约数

因式分解的问题相信大家并不陌生,

一般的求最大公约数函数可以这么写:

long max(long a, long b) {long ma,mi; if(a>b)ma=a,mi=b; else ma=b,mi=a;

for(s=mi;s>1;s--) if((mi%s==0)&&(ma%s==0))break;

return s;}

但这个算法的缺点在于如果两数的最大公约数很小但两个数都很大的时候效率不高;

如1111和2223这个算法要1111次循环后才能得到结果;

再看这个:

long max(long a,long b) {long i,ma,mi,c=0; if(a>b){ma=a;mi=b;} else {ma=b;mi=a;} i=mi; while(i) {i=ma%mi; if(i>(mi/2))i=mi-i; ma=mi; mi=i; c++;} printf("c1=%ld\n",c); return ma;}

这也是一个求最大公约数的算法;

它的思想是:

求A和B的最大公约数,假设A>B;

A/B表示成假分数的形式为N+X/B。

如果X不等于0

那A和B的最大公约数=B和X的最大公约数

如果X=0那这两个数的最大公约数就是B,

再看这个结论:X<B;X和B的最大公约数=(B-X)和X的最大公约数;

利用上面这些结论,可以写出跌代的算法,

大家可以看代码自己研究一下:

最坏情况循环只需要执行log2(B)次,效率可以大大提高。

PS:这个算法是我昨天为了优化一个程序想到的,拿出来给大家分享一下

[此贴子已经被作者于2004-10-07 18:52:20编辑过]

搜索更多相关主题的帖子: 算法 long 最大公约数 max else 
2004-10-07 09:39
心若在
Rank: 1
等 级:新手上路
帖 子:82
专家分:0
注 册:2004-9-21
收藏
得分:0 

你看看我的

main() {int x,y,z; scanf("%d %d",&x,&y); if(x<y) {z=x; x=y; y=z; } while(y!=0) {z=x%y; x=y; y=z; } printf("%d",x); getch(); }


我知道我菜 但我会尽我最大的努力去帮助别人!
2004-10-07 10:54
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 
顶一下,留个位置
2004-10-07 12:39
小小
Rank: 1
等 级:新手上路
威 望:1
帖 子:219
专家分:0
注 册:2004-5-31
收藏
得分:0 

精神可贵


有一天咖啡的舞者 £
2004-10-07 17:39
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
得分:0 
以下是引用心若在在2004-10-07 10:54:06的发言:

你看看我的

main() {int x,y,z; scanf("%d %d",&x,&y); if(x<y) {z=x; x=y; y=z; } while(y!=0) {z=x%y; x=y; y=z; } printf("%d",x); getch(); }

思想和我一样,但少了一个优化对于求N和N+1的公约数效果欠佳。

今天翻了一下书,发现这是“欧几里德辗转相除法”

说一下,尊重专利

[此贴子已经被作者于2004-10-08 08:28:19编辑过]


我喜欢创造,一只扑腾着翅膀向天空飞翔的乌鸦
2004-10-07 18:54
风中涟漪
Rank: 1
等 级:新手上路
帖 子:234
专家分:0
注 册:2004-8-9
收藏
得分:0 
欧几里德辗转想除法   -&gt;   我晕~~~

2004-10-07 20:35
心若在
Rank: 1
等 级:新手上路
帖 子:82
专家分:0
注 册:2004-9-21
收藏
得分:0 

我不知道是什么法 我只知道别人都这么用


我知道我菜 但我会尽我最大的努力去帮助别人!
2004-10-07 22:58
lyn_gemini
Rank: 1
等 级:新手上路
帖 子:103
专家分:3
注 册:2004-9-15
收藏
得分:0 

楼主的优化不错,顶


欢迎访问我的博客--*IT一粟*-- : http://lyn_gemini.
2004-10-09 13:44
xingning001
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2005-9-1
收藏
得分:0 

int gcd(int a,int b) /* a>b),注意b=0*/ { return b?gcd( b,a%b):a;}

2005-09-01 10:13
jjkl832
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2005-9-1
收藏
得分:0 
都不错啊

2005-09-01 20:06
快速回复:[算法]高效求最大公约数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017312 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved