最大公约数的算法

算法的原理:

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

相关文章

来自专栏数据结构与算法

洛谷P3273 [SCOI2011]棘手的操作

题目描述 有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:U x y: 加一条边,连接第x个节点和第...

3137
来自专栏计算机视觉与深度学习基础

Leetcode 234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome. Follow up: Could...

1867
来自专栏计算机视觉与深度学习基础

Leetcode 24 Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. For ex...

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

3137 栈练习1

3137 栈练习1  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descriptio...

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

BZOJ4195: [Noi2015]程序自动分析(并查集)

考虑一个约束满足问题的简化版本:假设x1,x2,x3...代表程序中出现的变量,给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件,请判定是否可以分别...

632
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之数组中出现次数超过一半的数字(九度OJ1370)

题目描述: 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出...

1849
来自专栏java学习

来测试一下你对数据结构中的栈和队列的了解有多少?

选择题 1.向一个栈顶指针为top的链栈中插入一个结点s,执行( )。 A.top.next=s; B.s.next=top.next ;top.next=s;...

5099
来自专栏机器学习从入门到成神

一道归并排序题的解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

532
来自专栏猿人谷

单链表反转的分析及实现

我先画一个单链表,这个单链表有4个元素。我的思路就是,每次把第二个元素提到最前面来。比如下面是第一次交换,我们先让头结点的next域指向结点a2,再让结点a1...

45510
来自专栏C语言及其他语言

【每日一题】问题 1224: 整除的尾数

一个整数,只知道前几位,不知道末二位,被另一个整数除尽了,那么该数的末二位该是什么呢

1012

扫描关注云+社区