【代码+详解】算法题 : 最大公约数

2024-06-05 06:36

本文主要是介绍【代码+详解】算法题 : 最大公约数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

❗❗❗必看:
下列题我全部都使用 Java 语言写的,并且均可以提交成功,获得Accepted 结果的. 如果代码和详解看了之后,对答案有任何疑问,都可以在评论区提出来,我都会一个一个回答.

❗❗❗感谢大家的支持,如果喜欢我的博客,关注 点赞 收藏 评论一波,非常感谢!!!

文章目录

  • 题目:最大公约数
    • 样例测试
    • 代码
    • 图示
    • 详解
      • 基本思想
      • 具体步骤
      • 代码解释

题目:最大公约数

给定两个正整数,求它们的最大公约数。

Input

有多组数据,每行为两个正整数,且不超过int可以表示的范围。

Output

行对应输出最大公约数。

样例测试

输入

4 8
8 6
200 300

输出

4
2
100


代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while(scanner.hasNextInt()) {int a = scanner.nextInt();int b = scanner.nextInt();System.out.println(gcd(a,b));}scanner.close();}private static int gcd(int a, int b) {while(b!=0) {int temp = b;b = a%b;a = temp;}return a;}}

图示

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

详解

这道题目我们可以通过欧几里得算法(也称辗转相除法)来解决。这是一种求两个正整数最大公约数(GCD)的高效算法。

基本思想

这道题目我们可以通过欧几里得算法(也称辗转相除法)来解决。这是一种求两个正整数最大公约数(GCD)的高效算法。

两个数的最大公约数等于其中较小的那个数和两个数相除余数的最大公约数。

具体步骤

  1. 用较大数除以较小数,得到余数。
  2. 若余数不为0,则用较小数和余数继续上述步骤,直到余数为0。
  3. 余数为0时,较小数即为两个数的最大公约数。

代码解释

  1. 输入处理
    • 使用 Scanner 类从标准输入中读取多组整数对。
    • 通过 scanner.hasNextInt() 循环读取输入,直到没有更多整数。
  2. 欧几里得算法
    • 定义一个 gcd 方法来计算两个整数的最大公约数。
    • 使用 while 循环,直到余数 b 为0。
    • 在循环内,使用变量 temp 保存当前余数 b,然后更新 b 为 a % b,再将 a 更新为 temp。
    • 当 b为0时,a即为最大公约数。
  3. 输出结果
    • 每对整数计算完成后,直接输出结果。

这篇关于【代码+详解】算法题 : 最大公约数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1032330

相关文章

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

HTML5中的Microdata与历史记录管理详解

《HTML5中的Microdata与历史记录管理详解》Microdata作为HTML5新增的一个特性,它允许开发者在HTML文档中添加更多的语义信息,以便于搜索引擎和浏览器更好地理解页面内容,本文将探... 目录html5中的Mijscrodata与历史记录管理背景简介html5中的Microdata使用M

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

HTML5表格语法格式详解

《HTML5表格语法格式详解》在HTML语法中,表格主要通过table、tr和td3个标签构成,本文通过实例代码讲解HTML5表格语法格式,感兴趣的朋友一起看看吧... 目录一、表格1.表格语法格式2.表格属性 3.例子二、不规则表格1.跨行2.跨列3.例子一、表格在html语法中,表格主要通过< tab

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at