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

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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片,如艺术画作、设计素材、报告图表等,提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

Android中Dialog的使用详解

《Android中Dialog的使用详解》Dialog(对话框)是Android中常用的UI组件,用于临时显示重要信息或获取用户输入,本文给大家介绍Android中Dialog的使用,感兴趣的朋友一起... 目录android中Dialog的使用详解1. 基本Dialog类型1.1 AlertDialog(

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义