2.7 编程之美--最大公约数的3种解法[efficient method to solve gcd problem]
【本文链接】
http://www.cnblogs.com/hellogiser/p/efficient-method-to-solve-gcd-problem.html
【题目】
求两个正整数的最大公约数Greatest Common Divisor (GCD)。如果两个正整数都很大,有什么简单的算法吗?例如,给定两个数1 100 100 210 001, 120 200 021,求出其最大公约数。
【解法】
【1. 辗转相除法】
辗转相除法:f(x,y) = f(y , x % y)(x>y)
f(42,30) = f(30,12) = f(12,6) = f(6,0) = 6
【代码】
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
/*
version: 1.0 author: hellogiser blog: http://www.cnblogs.com/hellogiser date: 2014/7/8 */ int gcd(int x, int y) |
此方法中用到了取模运算,对于大整数而言,取模运算(其中用到了除法)开销是非常昂贵的,将成为整个算法的瓶颈。
【2. 辗转相减法】
辗转相减法:f(x,y) = f(y, x-y) (x>y)
f(42,30) = f(30,12) = f(12,18) = f(18,12) = f(12,6)=f(6,6)=f(6,0)=6
【代码】
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
/*
version: 1.0 author: hellogiser blog: http://www.cnblogs.com/hellogiser date: 2014/7/8 */ int gcd(int x, int y) |
这个算法免去了大整数除法的繁琐,但同样也有不足之处。最大的瓶颈是迭代的次数过多,如果出现(1 000 000 000,1)这类情况,那就相当让人郁闷了。
【3. 奇偶法】
奇偶法:
此种方法是将解法1)和解法2)结合起来,降低计算复杂度的同时也降低迭代次数。
1:若 x, y均为偶数,f (x,y) = 2 * f(x / 2, y / 2) = 2 * f(x >> 1, y >> 1)
2:若x为偶,而y为奇,f (x , y ) = f (x / 2, y) = f ( x >> 1, y)
3:若x为奇,y为偶,f ( x, y) = f (x , y / 2) = f(x , y >> 1)
4:若x,y均为奇,f ( x, y ) = f (y , x - y)
在f(x, y) = f(y, x - y)之后,(x - y)是一个偶数,下一步一定会有除以2的操作。
因此最坏情况下时间复杂度为O(log2 (max(x,y)))。
f (42 , 30 ) = 2 * f (21,15)
= 2 * f (15,6)
= 2 * f (15,3)
= 2 * f (3,12) =2 * f (12,3)
= 2 * f (6,3)
= 2 * f (3,3)
= 2 * f (3,0)
= 2 * 3
= 6
【代码】
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/*
version: 1.0 author: hellogiser blog: http://www.cnblogs.com/hellogiser date: 2014/7/8 */ bool IsEven(int x) int gcd(int x, int y) |
【参考】
http://blog.csdn.net/ajioy/article/details/7478008
http://blog.csdn.net/rein07/article/details/6739688
【本文链接】
http://www.cnblogs.com/hellogiser/p/efficient-method-to-solve-gcd-problem.html
最新文章
- 漫谈JVM
- C#控制台程序的参数解析类库 CommandLine简单使用说明
- 【SQL 数据库】将一张数据表信息复制到另一张数据表
- 菜鸟带你飞______DP基础26道水题
- Node.js上传文件
- spring mvc 自定义转换器
- unable to load default svn client
- UNIX环境下用C语言写静态库与动态库
- LeetCode 58 Spiral Matrix II
- ERROR 1290 (HY000): The MySQL server is running with the --skip-grant-tables opt
- linux内核系统调用--sendfile函数
- Safari 3D transform变换z-index层级渲染异常的研究
- dubbo序列化
- 转载:编译安装Nginx(1.4)《深入理解Nginx》(陶辉)
- 【ZH奶酪】如何用Python计算最长公共子序列和最长公共子串
- 安装nginx和添加ssl证书
- sorted()&;enumerate()
- spring boot 自定义异常
- C语言dos程序源代码分享(进制转换器)
- PHP7 - 如何禁用Xdebug
热门文章
- ASP.NET MVC3 局部页面@RENDERBODY @RENDERPAGE@RENDERSECTION使用方法详细说明
- c#截图
- Java编程思想学习(十五) 注解
- 2.Android之按钮Button和编辑框EditText学习
- 【bzoj2463】 谁能赢呢?
- POJ 2559 Largest Rectangle in a Histogram
- 初次使用erlang的concurrent
- Java 对象的串行化(Serialization)
- Android事件机制之一:事件传递和消费
- PHP函数篇详解十进制、二进制、八进制和十六进制转换函数说明