栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【第14天】给定两个整数a和b,求它们的最大公约数 | 辗转相除法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【第14天】给定两个整数a和b,求它们的最大公约数 | 辗转相除法

本文已收录于专栏
《Java入门一百例》

学习指引
  • 序、专栏前言
  • 序、本章前言
  • 一、什么是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模板。

三、【例题1】

  给定多组测试数据,每次给定两个整数 a , b a,b a,b,请你打印出它们的最大公约数 ( 1 ≤ a , b ≤ 1 e 6 ) (1 leq a,b leq 1e6) (1≤a,b≤1e6)。

2、解题思路

  题目难度:⭐️

  写出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~。
四、【例题1】

  给定一个整数t,然后输入t个整数,求这t个整数的最大公约数。 ( 2 ≤ t , t i ≤ 1000 ) (2 leq t,t_i leq1000) (2≤t,ti​≤1000)

2、解题思路

  题目难度:⭐️

  求多个数的最大公约数,我们只需要迭代进行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则为答案。
五、推荐专栏
《零基础学算法100天》
六、课后习题
序号题目链接难度评级
1找出数组的最大公约数2
 学习有疑问?
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950436.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号