最大公约数的算法

算法的原理:

  对于辗转相除法: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 条评论
登录 后参与评论

相关文章

来自专栏Gaussic

一个关于Java输入输出优化的坑 原

在用Scanner输入大量数据的时候,会出现时间巨慢的问题,今天网上查到了方法,原来java的输入输出是有优化方法的。

481
来自专栏前端儿

Fibonacci数

无穷数列1,1,2,3,5,8,13,21,34,55...称为Fibonacci数列,它可以递归地定义为 F(n)=1 ...........(n=1或n=2...

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

数据结构 线性表操作

输入样例: 4 1 1 11 2 2 3 3 4 输出样例: 1 3 11 2 3 4 5 6 7 8 9 10 #include<stdio.h> #incl...

1925
来自专栏wym

HDU 6108 小C的倍数问题

http://acm.hdu.edu.cn/showproblem.php?pid=6108

563
来自专栏calmound

Minimum Depth of Binary Tree

题意:二叉树的最小深度 注意   1.当root为空的时候直接返回0,因为MIN赋值很大,所以如果不单独预判的话会返回MIN         2.判断树的深度应...

3437
来自专栏鸿的学习笔记

Python写的Python解释器(五)

条件和循环 到目前为止,解释器仅仅只是简单的逐个执行指令。下面将会讲述需要多次执行某些指令,或者在特定条件下跳过它们的做法。在代码中编写循环和if语句时,解释器...

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

洛谷P2468 [SDOI2010]粟粟的书架(二分答案 前缀和 主席树)

给出一个矩形,每个点都有一些值,每次询问一个子矩阵最少需要拿几个数才能构成给出的值

451
来自专栏python百例

118-ip地址与10进制数的转换

当我们ping数字2130706433时,从127.0.0.1返回结果。为什么是这样呢? IP地址是个32位的二进制数,表示成点分10进制,只是为了方便,如果...

843
来自专栏ACM小冰成长之路

HDU-2017 ACM/ICPC Asia Regional Qingdao Online-1011-A Cubic number and A Cubic Number

ACM模版 描述 ? 题解 上 oeisoeis 可以查到这个 YESYES 的数列,这个数列的每一项都是素数,并且可以化成如下: image.png 所以最...

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

23:区间内的真素数

23:区间内的真素数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 找出正整数 M 和 N 之间(N 不小于 M)的所有...

2667

扫码关注云+社区