当前位置: 首页 > news >正文

用python实现求两个整数的最大公约数

def gcd(a, b):  """计算最大公约数"""  while b:  a, b = b, a % b  return abs(a)  

下面是对 gcd 函数的逐行解释:

def gcd(a, b):"""计算最大公约数"""
  • 定义函数:这里定义了一个名为 gcd 的函数,它接受两个参数 ab,并返回它们的最大公约数(GCD)。函数文档字符串用来描述它的功能。
    while b:
  • 循环条件:这行代码是一个 while 循环,它会持续执行,直到 b 为 0。根据辗转相除法的原理,只要 b 不为 0,就可以继续计算最大公约数。
        a, b = b, a % b
  • 更新值:在循环中,通过同时赋值来更新 ab 的值:
    • a 被赋值为当前的 b
    • b 被赋值为 ab 的模(余数)a % b
  • 这个过程利用了辗转相除法的核心思想:最大公约数(gcd(a, b))等于最大公约数(gcd(b, a % b))。
    return abs(a)
  • 返回结果:当循环结束时,b 会变为 0,此时 a 就是 ab 的最大公约数。函数返回 abs(a),即 a 的绝对值。这是因为最大公约数的定义通常是非负的。

总结

这个 gcd 函数实现了求两个整数的最大公约数。通过反复取余的方式逐步逼近这个值,直到其中一个数为零。最终返回的就是它们的最大公约数。这一算法的效率很高,时间复杂度为 O(log(min(a, b)))。
我们来计算 8 和 6 的最大公约数(GCD),使用前面提到的 gcd 函数。

示例:计算 8 和 6 的最大公约数

  1. 初始化:将 a = 8b = 6

  2. 第一次迭代

    • while b: 这里 b 是 6,继续执行。
    • 计算 a % b,即 8 % 6 = 2
    • 更新值:a = 6b = 2
  3. 第二次迭代

    • while b: 这里 b 是 2,继续执行。
    • 计算 a % b,即 6 % 2 = 0
    • 更新值:a = 2b = 0
  4. 结束循环

    • 由于 b 现在为 0,循环结束。
    • 返回 abs(a),即 abs(2),结果是 2。

结论

因此,8 和 6 的最大公约数是 2。

总结步骤

与之前的示例相同,我们通过不断取模的方法逐步缩小问题的规模。最终,我们得到了这两个数的最大公约数,即 2。
计算 6 和 8 的最大公约数(GCD)与计算 8 和 6 的过程非常相似,因为最大公约数的顺序并不影响结果。我们来详细看一下步骤:

示例:计算 6 和 8 的最大公约数

  1. 初始化:将 a = 6b = 8

  2. 第一次迭代

    • while b: 这里 b 是 8,继续执行。
    • 计算 a % b,即 6 % 8 = 6(因为 6 小于 8,结果是 6)。
    • 更新值:a = 8b = 6
  3. 第二次迭代

    • while b: 这里 b 是 6,继续执行。
    • 计算 a % b,即 8 % 6 = 2
    • 更新值:a = 6b = 2
  4. 第三次迭代

    • while b: 这里 b 是 2,继续执行。
    • 计算 a % b,即 6 % 2 = 0
    • 更新值:a = 2b = 0
  5. 结束循环

    • 由于 b 现在为 0,循环结束。
    • 返回 abs(a),即 abs(2),结果是 2。

结论

因此,6 和 8 的最大公约数也是 2。

总结

无论是计算 6 和 8,还是 8 和 6,得到的结果都是相同的,最大公约数是 2。这表明计算的顺序不影响最终结果。

相关文章:

用python实现求两个整数的最大公约数

def gcd(a, b): """计算最大公约数""" while b: a, b b, a % b return abs(a) 下面是对 gcd 函数的逐行解释: def gcd(a, b):"""计算最大公约数"""定义函数:这里定义了一个名为 gcd…...

Linux 内核源码分析---proc 文件系统

proc文件系统 进程数据文件系统(process data filesystem, procfs)装载在 /proc,缩写为 procFS。 proc 文件系统是一种虚拟文件系统,其信息不能从块设备读取。只有在读取文件内容时才动态生成相应的信息。使用proc文件系统&…...

视频号直播回放怎么下载?

一、如果是下载自己直播回放视频: 方法一:视频号助手 打开网址:视频号助手 登陆账号后。下面路径,先点击成回放, 后就可以在下面路径,下载全场回放 但是这种有个缺点,就是不能分段下载。这样…...

【第九节】python中xml解析和json编解码

目录 一、Python XML 解析 1.1 什么是XML 1.2 Python 对 XML 的解析方法 1.3 SAX解析xml 1.4 xml.dom解析xml 1.6 ElementTree解析XML 二、Python编解码json 2.1 什么是json 2.2 使用json 库 2.3 使用第三方库Demjson 一、Python XML 解析 1.1 什么是XML XML&#x…...

yolo v8部署到云服务器问题记录

环境安装 1、运行项目报错:no python application found, check your startup logs for errors 在云服务器pytorch版本安装错了,安装了GPU版本,需要安装CPU版本 # CPU only 使用下面这段代码避免出现第二个错误 pip install torch2.3.1 to…...

端口被占用,杀死进程的步骤

一、 查看所有进程占用的端口 在开始-运行-cmd,输入:netstat –ano可以查看所有进程 二、查看占用指定端口的程序 查看被那个端口占用,可以用该命令: 三、使用命令杀死进程 杀死进程,使用命令:...

接口入门(企业常见使用,一分钟搞定版)

目录 1、接口的定义 定义位置 接口内容 2、接口的使用 正常实现接口 接口当做函数参数 匿名实现接口 3、OPPO便签接口具体分析 总结一下: 1、接口的定义 定义位置 可以写在类中,但注意现在接口名字是 类名.接口名 可以单独写在一个文件 接口内…...

深入解析:Cookie 与 Session 的区别及应用场景

引言 在Web开发中,Cookie 和 Session 是两种常用的用户状态管理机制。虽然它们的目标都是在无状态的HTTP协议中维护用户的状态,但它们的工作原理和适用场景却有所不同。在本文中,我们将深入探讨 Cookie 和 Session 的区别,并通过…...

LLM金融文本分类文档说明

Python注意事项: 1,创建虚拟环境: conda create --prefixD:\software\Anaconda3\envs\finance_analysis python3.10.4 conda create -p D:/software/anaconda3/envs/finance_analysis python3.10.4 注释: D:\software\anaconda3\e…...

EI检索,2天录用,3天见刊!截稿在即,这本水刊你还不投吗?

点击关注:关注GZH【欧亚科睿学术】,GET完整版2023JCR分区列表! 🎉 🎉 🎉 🎉 恭喜!这本毕业水刊仅2天录用!3天见刊! 重要时间节点如下 2024-08-03 Sub…...

sql获取过去的小时数

TIMESTAMPDIFF(HOUR, create_time, NOW()) AS pastHours 是一条 SQL 语句的一部分,它使用 TIMESTAMPDIFF 函数来计算两个时间点之间的差异,并将结果标记为 pastHours。 让我们详细解析一下这条语句: TIMESTAMPDIFF 函数: 这个函数用于计算两…...

【Android Studio】彻底卸载

文章目录 卸载程序控制面板卸载安全软件卸载 重启计算机删除文件重启计算机 我们在Android开发时涉及重装时,如果卸载不干净,再次安装是不会正常运行项目的,接下来就让我教你如何删除干净吧。 卸载程序 控制面板卸载 control控制面板一>…...

美术版权可以当做商标使用吗

美术版权与商标的区别及不可混用性分析 在知识产权领域,美术版权和商标权是两个重要的概念,它们各自承载着不同的法律意义和保护范围。 美术版权概述 美术版权,又称著作权,是指著作权人对其创作的美术作品所享有的权利。这些作品…...

控制某些请求不记录日志

说明:由于统一拦截日志请求,导致所有匹配的请求都会打印日志,这里需要控制有些请求执行不打印日志,比如定时每隔几秒执行某些请求。 具体实现如下: 一、自定义注解,如下: /** * Description: …...

Java线程池原理剖析和应用指南

目录 Java线程池详解一、Java线程池简介池化思想池化思想的优点 二、线程池的实现原理分析实现线程池需要考虑哪些问题?线程池的简单使用示例线程池原理的简单图示 三、Executor详解Executor简介Executor框架的继承结构总结ExecutorExecutorService 四、ThreadPoolE…...

ST-LINK烧录MCU

打开ST-LINK软件: 主板断电状态下接入烧录器,烧录器USB连接电脑: 主板上电,点击连接按钮: 点击加载文件: 点击写入按钮,烧录成功后拔掉烧录器,主板重新上电...

Go - 10. * 值类型和指针类型的差异

目录 一.引言 二.接收者类型 三.代码示例 1.指针接收者 2.值接收者 3.运行结果对比 4.代码修改 5.刨根问底 四.总结 一.引言 go 语言中 func (c *Title) 和 func (c Title) 两个方法的传参差一个 * 号,二者的区别是一个是指针类型,一个是值类型…...

waf绕过:网络安全狗绕过

引言: 所有的绕过原理都大致一致,但是并不是所有的绕过都能起到作用,渗透测试主要还是一个猜加试的过程,本文仅供参考 网络攻击或扫描绕过 1.get绕过(未开启cc防护) 网络安全狗的默认防护为,拒…...

Django中的模型小总结:

from django.db import models from django.urls import reverse# 自定义Manager方法 class HighRatingManager(models.Manager):def get_queryset(self):return super().get_queryset().filter(rating1)# CHOICES选项 class Rating(models.IntegerChoices):VERYGOOD 1, Very …...

深入理解 RDMA 的软硬件交互机制

作者:羽京 一、前言 随着数据中心的飞速发展,高性能网络不断挑战着带宽与时延的极限,网卡带宽从过去的 10 Gb/s 、25 Gb/s 到如今的 100 Gb/s、200 Gb/s 再到下一代的 400Gb/s 网卡,其发展速度已经远大于 CPU 发展的速度。 为了…...

docker详细操作--未完待续

docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...