- 序、专栏前言
- 序、本章前言
- 一、什么是gcd?
- 二、gcd模板代码
- 三、【例题1】
- 2、解题思路
- 3、模板代码
- 4、代码解析
- 四、【例题1】
- 2、解题思路
- 3、模板代码
- 4、代码解析
- 五、推荐专栏
- 六、课后习题
本专栏开启,目的在于帮助大家更好的掌握学习Java,特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法,同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
但最最主要的还是需要独立思考,对于本专栏的所有内容,能够进行完全掌握,自己完完全全将代码写过一遍,对于算法入门肯定是没有问题的。
算法的学习肯定不能缺少总结,这里我推荐大家可以到高校算法社区将学过的知识进行打卡,以此来进行巩固以及复习。
学好算法的唯一途径那一定是题海战略,大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。
求最大公约数的需求随处可见,比如专栏第6天我就使用了gcd函数。今天我们主要的内容是细讲模板以及原理,大家一定要烂熟于心,能自己默写出模板。
一、什么是gcd?gcd函数指的是求两整数a,b的最大公约数。如果采用最朴素的思想,寻找最大公约数应该像这样:
static int gcd(int a,int b){
int start=Math.min(a,b);
for (int i = start; i >=2 ; i--) {
if (a%i==0&&b%i==0) return i;
}
return 1;
}
很明显,这样的时间复杂度是
O
(
m
i
n
(
a
,
b
)
)
O(min(a,b))
O(min(a,b)),如果
a
a
a 和
b
b
b 都非常大的话,效率极其的低。而数学届普遍用来优化求最大公约数的有两种方法,一种名为更相减损术,还有一种叫辗转相除法。这里我们讲解性能更优秀的辗转相除法。
辗转相除法也叫欧几里得算法(没错又是这位大佬),是他搞出来的。它基于的原理是:
a , b a, b a,b的最大公约数等于 b 与 a / b 余 数 b 与 a / b 余数 b与a/b余数的最大公约数相等。
它的操作步骤也非常简单,我们假设 a , b a,b a,b两数较大的为 a a a:
- ( 1 ) (1) (1)先用较大数对较小数取余,我们得到a%b=c。根据上述原理我们可以进行转化,求a和b的最大公约数转化为求b和c的最大公约数。
- ( 2 ) (2) (2)求b和c的最大公约数,同样回到第一步,b%c=d,从上一步出关系可知,除数一定是比余数大的,所以b一定是大于c的。所以求b和c的最大公约数又转换为求c和d的最大公约数。
- ( 3 ) (3) (3) 第1步和第2步来回跳转,数字持续变小。
- ( 4 ) (4) (4)如果当某个时刻,此时我们的数是f和g,而且f%g=0了,余数为0,那么此时的g就是我们的最大公约数。及我们可以得到a和b的最大公约数是g。
之所以步骤这么详细,是想让大家注意到,1、2步之间的联系非常紧密,它将一个复杂的问题转化为一个子问题去解决,这恰好就符合到了我们之前学习使用递归的条件,而递归写法也恰好是最简单的。
二、gcd模板代码static int gcd(int a,int b){
if (b==0){
return a;
}
return gcd(b,a%b);
}
其中b等于0时,说明上一步存在某个数x,使得x%a==b。根据之前的结论,此时a就是我们的答案。所以b为0就是我们递归出口。熟练以后我们可以结合条件判断符写的更加简洁
static int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
其实更相减损术基于的原理和辗转相除法是一样的,只不过它使用减法,辗转相除法使用的是除法,时间复杂度稳定在
O
(
l
o
g
n
)
O(logn)
O(logn)。而在答案需要迭代多次时(比如最大公约数为1的情况),更相减损术复杂度可能会退化到
O
(
n
)
O(n)
O(n),所以推荐大家熟记上述的辗转相除法的gcd模板。
2、解题思路给定多组测试数据,每次给定两个整数 a , b a,b a,b,请你打印出它们的最大公约数 ( 1 ≤ a , b ≤ 1 e 6 ) (1 leq a,b leq 1e6) (1≤a,b≤1e6)。
题目难度:⭐️
写出gcd函数模板,每次直接打印结果即可。
3、模板代码import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while (sc.hasNext()){
int a=sc.nextInt();
int b=sc.nextInt();
System.out.println(gcd(a,b));
}
}
static int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
}
4、代码解析
- ( 1 ) (1) (1)解析就是熟悉模板gcd~。
2、解题思路给定一个整数t,然后输入t个整数,求这t个整数的最大公约数。 ( 2 ≤ t , t i ≤ 1000 ) (2 leq t,t_i leq1000) (2≤t,ti≤1000)
题目难度:⭐️
求多个数的最大公约数,我们只需要迭代进行gcd即可,每次的结果和下一个数进行gcd。
3、模板代码import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
int[] a=new int[t];
for (int i = 0; i < t; i++) {
a[i]=sc.nextInt();
}
int s=gcd(a[0],a[1]);
for (int i = 2; i
s=gcd(s,a[i]);
}
System.out.println(s);
}
static int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
}
4、代码解析
-
(
1
)
(1)
(1)先拿第一个数和第二个数得到答案s,然后再用s去和剩余的数不断进行gcd进行迭代,最后s则为答案。
| 序号 | 题目链接 | 难度评级 |
|---|---|---|
| 1 | 找出数组的最大公约数 | 2 |



