美文网首页
辗转相除法

辗转相除法

作者: KallyCat | 来源:发表于2020-04-26 00:30 被阅读0次
  1. 如果b等于0,计算结束,a就是最大公约数

  2. 否则,计算a除以b的余数,让a等于b,b等于那个余数

  3. 回到第一步

import java.util.Scanner;

import static java.lang.System.out;

public class Main {
    public static int f(int a,int b){//求公约数,辗转相除法
        int count = 0;
        for(int i=1;i<=Math.min(a, b);i++){
            if(a%i==0&&b%i==0){
                count = i;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String[] num = s.split("/");//切割字符串
        int a = Integer.parseInt(num[0]); //string 转 int
        int b = Integer.parseInt(num[1]);
        System.out.println(a/f(a,b)+"/"+b/f(a,b));
    }
}

相关文章

  • 算法-辗转相除法

    算法:辗转相除法(欧几里得算法) GCD递归定理 辗转相除法算法概述 辗转相除法伪代码 辗转相除法代码实现 对于两...

  • 辗转相除法

  • 辗转相除法

    大家好,我是BUG,继算法专辑之后,我现在发出了数学专辑,研究和编程相关的数学问题。讲解之前,别忘了收藏我的编程专...

  • 辗转相除法

    如果b等于0,计算结束,a就是最大公约数 否则,计算a除以b的余数,让a等于b,b等于那个余数 回到第一步

  • 辗转相除法

    求两个数a和b的最大公约数的算法: 1、如果b等于0,计算结束,a就是最大公约数; 2、否则,计算a除以b的余数,...

  • 辗转相除法

    辗转相除法(欧几里得算法)求两个数的最大公约数和最小公倍数?1、最大公约数思路:大数除以小数,如果能够整数,则小数...

  • 求最大公约数

    辗转相除法

  • 辗转相除法求最大公因数 2020-03-12

    今天做了一道题,需要求最大公因数,已经完全把辗转相除法忘记了,特此记录 辗转相除法 辗转相除法,也叫欧几里得算法,...

  • 最大公约数与最小公倍数:辗转相除法

    已知两个数x和y,求x和y的最大公约数 暴力循环求解: 辗转相除法求解: 辗转相除法递归求解: 理解辗转相除法: ...

  • 算法:辗转相除法

    题目:要求方法传两个正整数参数,返回值就是他们的最大公约数。 解法一:(性能最差) 解法二:辗转相除法,又名欧几里...

网友评论

      本文标题:辗转相除法

      本文链接:https://www.haomeiwen.com/subject/chdrwhtx.html