算法_趣味分数_Question1_最大公约数（java实现）
【算法_趣味分数_Question1_最大公约数（java实现）】这篇文章讲述的是算法趣味分数部分的最大公约数问题的java实现，参考的书籍为清华大学出版社出版，贾蓓等编著的《c语言趣味编程1000例》，如有错误或者不当之处，还望各位大神批评指正。
问题描述 求任意两个数的最大公约数（GCD），最大公约数如果一个自然数a可以被自然数b整除，则称a为b的倍数，b为a的倍数。几个自然数有共有的约数，叫作这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数
算法分析 该题有两种解决方案，第一种穷举法，从2开始遍历，找出同时能被这两个数整除的所有数取其最大值。第二种辗转相除法：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
代码实现
- 方法一（穷举法）：
package fraction;
/**
* @author 叶清逸
* @date 2018年7月18日上午12:18:37
* @version 1.0
* @project fraction
*/
public class Q1_GCD {
/**
* 问题分析：求任意两个数的最大公约数（GCD），最大公约数如果一个自然数a可以被自然数b整除，则称a为b的倍数，b为a的倍数。几个
*自然数有共有的约数，叫作这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。
*
* 算法分析：该题有两种解决方案，第一种穷举法，从2开始遍历，找出同时能被这两个数整除的所有数取其最大值。第二种辗转相除法：
*用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最
*后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
*/public static void main(String[] args) {
method1() ;
}/*遍历法求出最大公约数*/
private static void method1() {
/*初始化两个数a，b*/
int a = 56 ;
int b = 72 ;
int gcd = 0 ;
/*排序保证a始终小于b*/
if(a > b){
int t = a ;
a = b ;
b = t ;
}
/*遍历求最大公约数*/
for(int i=2 ;
i- 方法二（辗转相除法）：
package fraction;
/**
* @author 叶清逸
* @date 2018年7月18日上午12:18:37
* @version 1.0
* @project fraction
*/
public class Q1_GCD {
/**
* 问题分析：求任意两个数的最大公约数（GCD），最大公约数如果一个自然数a可以被自然数b整除，则称a为b的倍数，b为a的倍数。几个
*自然数有共有的约数，叫作这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。
*
* 算法分析：该题有两种解决方案，第一种穷举法，从2开始遍历，找出同时能被这两个数整除的所有数取其最大值。第二种辗转相除法：
*用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最
*后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
*/public static void main(String[] args) {
method2() ;
}
/*辗转相除法求最大公约数*/
private static void method2(){
/*初始化两个数a，b*/
int a = 8 ;
int b = 4 ;
/*排序保证a始终小于b*/
if(a > b){
int t = a ;
a = b ;
b = t ;
}
/*复制变量a和b，不造成变量被修改*/
int c = a ;
int d = b ;
/*辗转相除*/
while(c%d != 0){
//k保存余数
int k = c%d ;
//除数变为c
c = d ;
//被除数变为余数
d = k ;
}
/*辗转相除结束后的c即为所求的最大公约数*/
System.out.println(a+"和"+b+"的最大公约数为："+d);
}
}
样例输出
56和72的最大公约数为：8
4和8的最大公约数为：4
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 中国军校