【算法积累】辗转相除法

【算法积累】辗转相除法,python实现两种

  • 辗转相除法(又称欧几里得算法)
  • 减法(不常用)
      • 代码实现
      • 执行结果
    • 辗转相除法
      • 代码实现
      • 执行结果

辗转相除法(又称欧几里得算法)

又称欧几里得算法,是一种用于求两个整数最大公约数的算法

在辗转相除法中分为使用除法运算和使用减法运算两种方法。

减法(不常用)

在这里插入图片描述

代码实现

a = int(input("第一个数字:"))
b = int(input("第二个数字:"))while a!=b:           # a不等于b   比如(a=42,b=12)if a > b:         # 判断a>b    a=a-b         # a=30 此时 a还是>b 一直减到a=6elif b>a:b=b-a         # 现在b>a b=12-6 =6# else不用写了,此时a=b了 跳出循环了# 上面的数字反过来也一样print("a和b的最大公约数:" ,a) # a和b相等了,输出谁都行

执行结果

C:\Users\Administrator>python xianyujiang.py
第一个数字:42
第二个数字:12
a和b的最大公约数: 6C:\Users\Administrator>python xianyujiang.py
第一个数字:22
第二个数字:42
a和b的最大公约数: 2C:\Users\Administrator>python caishuzi.py
第一个数字:4141241
第二个数字:4235235
a和b的最大公约数: 1C:\Users\Administrator>python caishuzi.py
第一个数字:3241512
第二个数字:5213152
a和b的最大公约数: 8C:\Users\Administrator>python xianyujiang.py
第一个数字:24
第二个数字:24
a和b的最大公约数: 24

辗转相除法

辗转相除法的基本思想是:用较大的数除以较小的数,然后用除数与余数再做同样的运算,直到余数为0为止,此时的除数就是两个数的最大公约数。

辗转相除法的步骤如下:

  1. 如果一个数能被另一个数整除,那么它们的最大公约数就是被除数。

  2. 如果一个数不能被另一个数整除,那么用被除数除以除数,得到的商就是新的被除数,余数就是新的除数。

  3. 重复上述步骤,直到余数为0,此时的除数就是最大公约数。

代码实现

a = int(input("第一个数字:"))
b = int(input("第二个数字:"))
m = max(a, b)            # 
n = min(a, b)
r = m % n
while r != 0:m = nn = rr = m % n
print(num1, "和", num2, "的最大公约数为", n)

执行结果

C:\Users\Administrator>python xianyujiang.py
第一个数字:20
第二个数字:40
2040 的最大公约数为 20C:\Users\Administrator>python xianyujiang.py
第一个数字:12
第二个数字:42
1242 的最大公约数为 6

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/274877.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【洛谷 P8781】[蓝桥杯 2022 省 B] 修剪灌木 题解(数学)

[蓝桥杯 2022 省 B] 修剪灌木 题目描述 爱丽丝要完成一项修剪灌木的工作。 有 N N N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌木,让灌木的高度变为 0 0 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始,每天向右修剪一棵灌木…

镭速教你如何解决大数据量串行处理的问题

大数据的高效处理成为企业发展的关键。然而,大数据量串行处理的问题常常困扰着许多企业,尤其是在数据传输方面。本文将探讨大数据量串行处理的常见问题,并介绍企业常用的处理方式,最后重点阐述镭速如何提供创新解决方案&#xff0…

【20240309】WORD宏设置批量修改全部表格格式

WORD宏设置批量修改全部表格格式 引言1. 设置表格文字样式2. 设置表格边框样式3. 设置所有表格边框样式为075pt4. 删除行参考 引言 这两周已经彻底变为office工程师了,更准确一点应该是Word工程师,一篇文档动不动就成百上千页,表格图片也是上…

Linux中三次握手,四次挥手状态图,端口复用 半关闭状态,心跳包

tcp三次握手和四次挥手状态图: 为什么需要2MSL: 原因1:让四次挥手过程更加可靠,确保最后一个发送给对方的ACK到达;若对方没有收到ACK应答,对方会再次发送FIN请求关闭,此时在2MSL时间内被动关闭…

MySQL-锁:共享锁(读)、排他锁(写)、表锁、行锁、意向锁、间隙锁,锁升级

MySQL-锁:共享锁(读)、排他锁(写)、表锁、行锁、意向锁、间隙锁 共享锁(读锁)、排他锁表锁行锁意向锁间隙锁锁升级 MySQL数据库中的锁是控制并发访问的重要机制,它们确保数据的一致性…

[C语言][PTA基础C基础题目集] strtok 函数的理解与应用

一.strtok函数的解释与说明 ①strtok函数的功能 Find the next token in a string. 即查找字符串中的下一个标记. 就是将一个字符串分割成一系列的子串. ②strtok函数的原型 char *strtok( char * strToken, const char * strDelimit ); strToken: 要分割的字符串. strDel…

【机器学习】在Python中进行K-Means聚类和层次聚类

文章目录 Python中聚类算法API的使用指南K-Means 聚类步骤一:导入必要的库步骤二:加载数据步骤三:应用K-Means聚类步骤四:保存聚类结果 层次聚类步骤一:导入库步骤二:加载数据并计算距离矩阵步骤三&#xf…

MyBatis拦截器四种类型和自定义拦截器的使用流程

文章目录 MyBatis拦截器四种类型和自定义拦截器的使用流程一、MyBatis拦截器四种类型的详细解释:1. **ParameterHandler 拦截器**:2. **ResultSetHandler 拦截器**:3. **StatementHandler 拦截器**:4. **Interceptor Chain 拦截器…

Threejs粒子水波纹效果

依赖 three(这个重要)react (这个不重要)ahooks(这个不重要)unocss(这个不重要) 效果 代码 import React, { useEffect, useRef } from react; import { useGetState } from ahoo…

数据结构---C语言栈队列

知识点: 栈: 只允许在一端进行插入或删除操作的线性表,先进后出LIFO 类似一摞书,按顺序拿,先放的书只能最后拿; 顺序栈:栈的顺序存储 typedef struct{Elemtype data[50];int top; }SqStack; SqS…

Java实现自定义Hive认证账户密码

一、业务背景 在搭建好Hive环境后,应用项目远程连接hive需要设置用户名和密码,但hive默认的用户名和密码都是空,因此需要设置自定义用户名和密码。 二、开发步骤 2.1 新建maven项目,pom.xml引入相关依赖,主要是hadoop、…

RabbitMQ 面试题及答案整理,最新面试题

RabbitMQ的核心组件有哪些? RabbitMQ的核心组件包括: 1、生产者(Producer): 生产者是发送消息到RabbitMQ的应用程序。 2、消费者(Consumer): 消费者是接收RabbitMQ消息的应用程序…

计算机网络——计算机网络的性能

计算机网络——计算机网络的性能 速率带宽吞吐量时延时延宽带积往返时间RTT利用率信道利用率网络利用率 我们今天来看看计算机网络的性能。 速率 速率这个很简单,就是数据的传送速率,也称为数据率,或者比特率,单位为bit/s&#…

Midjourney绘图欣赏系列(七)

Midjourney介绍 Midjourney 是生成式人工智能的一个很好的例子,它根据文本提示创建图像。它与 Dall-E 和 Stable Diffusion 一起成为最流行的 AI 艺术创作工具之一。与竞争对手不同,Midjourney 是自筹资金且闭源的,因此确切了解其幕后内容尚不…

信息安全、网络安全以及数据安全三者之间的区别

随着信息技术的飞速发展,网络安全、信息安全、数据安全等词汇在平时出现的频率越来越高,尤其是数据安全,是大家都关心的一个重要话题。事实上,有很多人对网络安全、信息安全、数据安全的概念是区分不清的,下面由我帮大…

吴恩达深度学习笔记:深度学习引言1.1-1.5

目录 第一门课:神经网络和深度学习 (Neural Networks and Deep Learning)第一周:深度学习引言(Introduction to Deep Learning)1.1 欢迎(Welcome)1.2 什么是神经网络?(What is a Neural Network)1.3 神经网络的监督学习(Supervised Learning …

【PyQT/Pysider】控件背景渐变

默认渐变配色说明 background-color: qlineargradient(spread:pad, x1:0, y1:0, x2:1, y2:0, stop:0 rgba(255, 178, 102, 255), stop:0.55 rgba(235, 148, 61, 255), stop:0.98 rgba(0, 0, 0, 255), stop:1 rgba(0, 0, 0, 0));这段样式表使用了qlineargradient函数来创建…

Dynamic Wallpaper v17.4 mac版 动态视频壁纸 兼容 M1/M2

Dynamic Wallpaper Engine 是一款适用于 Mac 电脑的视频动态壁纸, 告别单调的静态壁纸,拥抱活泼的动态壁纸。内置在线视频素材库,一键下载应用,也可导入本地视频,同时可以将视频设置为您的电脑屏保。 应用介绍 Dynam…

chatgpt与人类有何不同?

ChatGPT和人类之间存在多个显著的差异。 首先,ChatGPT是一种基于人工智能技术的计算机程序,通过机器学习和自然语言处理等技术,从大量的数据中获取知识并生成语言输出。它主要依赖于算法和数据进行工作,能够迅速处理和检索信息&a…

Objective-C blocks 概要

1.block的使用 1.1什么是block? Blocks是C语言的扩充功能:带有自动变量(局部变量)的匿名函数。 “带有自动变量”在Blocks中表现为“截取自动变量" “匿名函数”就是“不带名称的函数” 块,封装了函数调用及调用…