最大公约数的算法

算法的原理:

  对于辗转相除法:i和j的最大公约数,也就是i和j都能够除断它。换句话讲,就是i比j的n倍多的那个数k(i = j*n + k,即i % j = k)应该也是最大公约数的倍数。所以就能转换成求k和j的最大公约数。同理,对于更相减损术,同样的道理,i比j大的部分也是最大公约数的倍数。

代码:

 1 /**
 2  * 求最大公约数算法汇总
 3  *
 4  */
 5 public class GCD {
 6     public static void main(String[] args) {
 7         GCD gcd = new GCD();
 8         gcd.gcd1(43, 45);
 9         gcd.gcd2(64, 80);
10         gcd.gcd3(45, 81);
11     }
12     
13     
14     /**
15      * 第三种方法:更相减损术 + 辗转相除法,即
16      * 当a和b均为偶数,gcb(a,b) = 2*gcb(a/2, b/2) = 2*gcb(a>>1, b>>1)
17      * 当a为偶数,b为奇数,gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)
18      * 当a为奇数,b为偶数,gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)
19      * 当a和b均为奇数,利用更相减损术运算一次,gcb(a,b) = gcb(b, a-b), 此时a-b必然是偶数,又可以继续进行移位运算。
20      */
21     private void gcd3(int i, int j) {
22         System.out.println("The greatest common divisor is:" + doubleGcd(i, j));
23     }
24     
25     private int doubleGcd(int i, int j) {
26         if (i % j == 0) {
27             return j;
28         } 
29         
30         if ((i&1) == 0 && (j&1) == 0) {
31             // 都是偶数
32             return doubleGcd(i >> 1, j >> 1) << 1;
33         } else if ((i&1) == 0 && (j&1) != 0) {
34             // i为偶数,j为奇数
35             return doubleGcd(i >> 1, j);
36         } else if ((i&1) != 0 && (j&1) == 0) {
37             // i为奇数,j为偶数
38             return doubleGcd(i, j >> 1);
39         } else {
40             // i和j都为奇数
41             return doubleGcd(i, i > j ? i - j : j - i);
42         }
43     }
44 
45 
46     /**
47      * 第二种方法:九章算术的更相减损术,即如果i>j,那么先用i-j得到其差k.然后将问题转换成求k和m的最大公约数.依此类推,直到差为0.
48      * 这个方法也有一个问题,就是如果i和j想差的比较大,那么这个方法存在较高的时间复杂度.
49      */
50     private void gcd2(int i, int j) {
51         if (i < j) {
52             gcd2(j, i);
53             return;
54         }
55         
56         int k = i - j;
57         if (k == 0) {
58             System.out.println("The greatest common divisor is:" + j);
59             return;
60         } else {
61             if (k >= j) {
62                 gcd2(k, j);
63             } else {
64                 gcd2(j, k);
65             }
66         }
67     }
68 
69     /**
70      * 第一种方法:辗转相除法, 即如果i>j, 那么先用i%j得到余数k.将问题转换成求k和m的最大公约数.依此类推,直到余数为0.
71      * 该方法有一个比较大的问题问题是取模的性能。
72      */
73     private void gcd1(int i, int j) {
74         // 确保n>m
75         if (i < j) {
76             gcd1(j, i);
77             return;
78         }
79         
80         int k = i%j;
81         if (k == 0) {
82             System.out.println("The greatest common divisor is:" + j);
83             return;
84         } else {
85             if (k >= j) {
86                 gcd1(k, j);
87             } else {
88                 gcd1(j, k);
89             }
90         }
91     }
92 }    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

PAT 1010 Radix

1010. Radix (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 St...

3555
来自专栏赵俊的Java专栏

落单的数

2142
来自专栏小樱的经验随笔

洛谷 P1598 垂直柱状图【字符串+模拟】

P1598 垂直柱状图 题目描述 写一个程序从输入文件中去读取四行大写字母(全都是大写的,每行不超过72个字符),然后用柱状图输出每个字符在输入文件中出现的次数...

2975
来自专栏HansBug's Lab

3409: [Usaco2009 Oct]Barn Echoes 牛棚回声

3409: [Usaco2009 Oct]Barn Echoes 牛棚回声 Time Limit: 3 Sec  Memory Limit: 128 MB Su...

2447
来自专栏测试开发架构之路

C语言之位运算

指针和位运算很适合编写系统软件的需要。 位运算指进行二进制位的运算。   按位与”运算符 & 用途 1)清零 2)取一个数中某些指定位(比如只需要低8位) 3)...

37110
来自专栏增长技术

Swift-?-!

上面了解到的是普通值,接下来Optional值要上场了。Optional其实是个enum,里面有None 和Some两种类型。其实所谓的nil就是Optiona...

953
来自专栏数据结构与算法

2570 绝对素数

2570 绝对素数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一个自然数...

3337
来自专栏数据结构与算法

cf550C. Divisibility by Eight(结论)

设$x = 10000 * a_i + 1000 * a_{i - 1} + \dots$

732
来自专栏云霄雨霁

删数问题

2100
来自专栏mySoul

设计模式 里氏替换原则

在场景中,三毛需要什么枪支,就直接new 出一个枪支即可,然后其内通过抽象类获取到对象,然后对齐进行修饰

1056

扫码关注云+社区