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

Python数据结构与算法-欧几里算法(p95)

一、欧几里算法原理

  1. 欧几里得公式

欧几里得算法:gcd(a,b) = gcd(b, a mod b) ; mod是指模,即a/b取余数。

运算示例: gcd(60,21)= gcd(21,18) = gcd(18,3)=gcd(3,0)

证明略

  1. 最大公约数-欧几里得求解

(1)最大公约数定理

  • 约数:如果整数a能被整数b整除,那么a叫做b的倍数,b叫做a的约数。

  • 给定两个整数a,b,两个数的所有公共约数中的最大值即为最大公约数 (Greatest Common Divisor, GCD)

  • 例:12与16的最大公约数是4。

  • 最大公约数求解:

  • 欧几里得,又叫辗转相除法

  • 《九章算术》:更相减损术

(2)最大公约数求解-欧几里得算法实现


def gcd_1(a,b): # 最大公约数-递归,a,b是两个数值if b == 0: # 递归终止条件return aelse:return gcd_1(b, a % b) # 公式gcd(a,b) = gcd(b, a mod b)print(gcd_1(12,16))def gcd_2(a, b): # 最大公约数-非递归,a,b是两个数值while b > 0: # b = 0时就得的a就是最后求的值r = a % b # 循环中a,b值一直在变化,需要先存储在一个变量中,不能直接用a%ba = bb = rreturn aprint(gcd_2(12,16))

输出结果

4
4

二、欧几里得算法应用——分数计算

1、提出问题

利用欧几里得算法实现一个分数类,支持分数的四则运算。

2、分数计算代码实现

(1)知识点—__add__()函数

__add__()方法是python的内置方法之一, 是一个一元函数。作用相当于求和运算。

1)__add__(self, other)是同一个类,两个对象相加的实现逻辑

class Myclass(object):def __init__(self,value):self.value = valuedef __add__(self, other):return self.value + other.value
a = Myclass(1)
b = Myclass(2)
print(a + b) # 实现加法运算

以上代码中,self 只本身对象,other 指另一个对象(同属于Myclass 类)

2)类外部加法使用

class Num:def __init__(self, x):self.x = xnumber = Num(5)    
print(number.x.__add__(6))# 输出结果
11

3) __add__属性-拼接操作

可以进行拼接操作,拼接list和tuple。

b = [7, 8, 9, 10, 11, 12]
d = [19, 20, 21, 22, 23, 24]# 执行了拼接动作,拼接后的值被return出来
g = b.__add__(d)
print(g)# 输出结果
[7, 8, 9, 10, 11, 12, 19, 20, 21, 22, 23, 24]

(2)代码实现-加法

# 分数运算
class Fraction(): # 分数运算的类def __init__(self,a,b): # 传入参数属性,a,b是数字self.a = a # 分子self.b = b # 分母x = self.gcd(a, b) # 分子分母的最大公约数,x不是属性,不需要加self# 约分,分子和分母都除以最大公约数self.a = a / x # 分子化简self.b = b /x # 分母化简def gcd(self, a, b): # a,b最大公约数while b > 0:r = a % ba = b b = rreturn adef lcm(self, a, b): # 最小公倍数# 12 ,16 最大公约数为4# LCM = (12/4) * (16/4) * 4x = self.gcd(a, b)return a / x * b # (a / x) * (b / x) * x 的化简def __add__(self, other): # 加法,是内置函数# 1/12 + 1/20# 分母化成最小公倍数a = self.a # 分子b = self.b # 分母c = other.a # 分子d = other.b # 分母den = self.lcm(b, d) # 找到分母的最小功倍数,作为分母num_a = den / b * a  # 换算分子anum_c = den / d * c  # 换算分子cnum = num_a + num_c # 分子相加return Fraction(num, den) # 分子分母化简def __str__(self) -> str: # 类中的字符串显示的函数return "%d/%d" %(self.a, self.b) # %d表示十进制的整数f = Fraction(30,16) # 实例化类
print(f)a = Fraction(1, 12) # 1/12 实例化类
b = Fraction(1, 20) # 1/20 实例化类
print(a + b)

输出结果

15/8
2/15

相关文章:

Python数据结构与算法-欧几里算法(p95)

一、欧几里算法原理 欧几里得公式 欧几里得算法:gcd(a,b) gcd(b, a mod b) ; mod是指模,即a/b取余数。 运算示例: gcd(60,21) gcd(21,18) gcd(18,3)gcd(3,0) 证明略 最大公约数-欧几里得求解 &#xff08…...

【故障诊断】用于轴承故障诊断的性能增强时变形态滤波方法及用于轴承断层特征提取的增强数学形态算子研究(Matlab代码实现)

💥 💥 💞 💞 欢迎来到本博客 ❤️ ❤️ 💥 💥 🏆 博主优势: 🌞 🌞 🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 …...

水羊转债,超达转债,晓鸣转债上市价格预测

水羊转债 基本信息 转债名称:水羊转债,评级:A,发行规模:6.94987亿元。 正股名称:水羊股份,今日收盘价:13.94元,转股价格:13.71元。 当前转股价值 转债面值 /…...

从数据管理到数据资产管理

数据已经与土地、劳动力、资本、技术并称为五种生产要素,数据的价值是毋庸置疑的。数据甚至成为了国家的基础性战略资源,数字经济也正在成为经济增长的强大创新动力。那么—— 数据到底指的是什么? 数据管理又是怎么回事? 数据如何…...

RabbitMQ【#1】是什么,有什么用

RabbiMQ是什么? RabbitMQ是一种开源的消息队列软件,它实现了高级消息队列协议(AMQP)并支持多种编程语言。它可以用于将消息从一个应用程序传递到另一个应用程序或进程,并支持分布式系统中的异步消息通信。RabbitMQ的主…...

RabbitMQ防止消息丢失

生产者没有成功把消息发送到MQ 丢失的原因 :因为网络传输的不稳定性,当生产者在向MQ发送消息的过程中,MQ没有成功接收到消息,但是生产者却以为MQ成功接收到了消息,不会再次重复发送该消息,从而导致消息的丢…...

ImageJ用户手册——第二部分(ImageJ操作)

ImageJ用户手册-第二部分 ImageJ的使用4. 使用键盘快捷键5. 查找命令6. 撤消和重做7. 图像类型和格式原生格式非原生格式 8. 堆栈、虚拟堆栈、超堆栈Stacks(堆栈)Virtual Stacks(虚拟堆栈)Hyperstacks(超堆栈&#xff…...

Java中Lambda表达式(面向初学者)

目录 一、Lambda表达式是什么?什么场景下使用Lambda? 1.Lambda 表达式是什么 2.函数式接口是什么 第二章、怎么用Lambda 1.必须有一个函数式接口 2.省略规则 3.Lambda经常用来和匿名内部类比较 第三章、具体使用场景举例() …...

2023年淮阴工学院五年一贯制专转本数字电子技术考试大纲

2023年淮阴工学院五年一贯制专转本数字电子技术考试大纲 一、考核对象 本课程的考核对象是五年一贯制高职专转本电子科学与技术专业普通在校生考生。 二、考试目的及总体要求 通过本课程的考试,检查学生对掌握数字电路的基础理论知识的掌握程度,是否…...

使用 GO 编写 Web 应用:学习如何使用 GO 语言编写 Web 应用,包括使用 HTTP 路由、模板引擎等。

GO 语言是一个高效、可靠和简洁的编程语言,越来越多的开发者开始选择 GO 语言来编写 Web 应用。本文将介绍如何使用 GO 语言编写 Web 应用,并且将重点关注使用 HTTP 路由和模板引擎。 使用 HTTP 路由 HTTP 路由是 Web 应用中非常重要的一个概念。它可以帮助我们将请求路由到…...

Leetcode-day4【88】【167】【125】【345】

文章目录 88. 合并两个有序数组题目解题思路解题思路【学习】尾插入法 167. 两数之和 II - 输入有序数组题目解题思路 125. 验证回文串题目解题思路 345. 反转字符串中的元音字母题目解题思路 88. 合并两个有序数组 题目 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums…...

【IoT】如何使用软件加密(文件夹加密工具.exe),并破解工具

目录 第一步:显示隐藏的文件。 第二步:将隐藏文件变成文件夹。 第三步:解密文件。 有时候出差或者有些商务场合,需要对一些敏感文件做一下简单的加密,这样在分享内容的时候,可以起到初步的保护作用。 当…...

Spring Boot——优雅的参数校验

🎈 概述 当我们想提供可靠的 API 接口,对参数的校验,以保证最终数据入库的正确性,是 必不可少 的活。比如下图就是 我们一个项目里 新增一个菜单校验 参数的函数,写了一大堆的 if else 进行校验,或者基础校…...

【c语言】typedef的基本用法 | 定义格式

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; 给大家跳段街舞感谢支持&#xff01;ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ…...

深度学习论文分享(二)Data-driven Feature Tracking for Event Cameras

深度学习论文分享&#xff08;二&#xff09;Data-driven Feature Tracking for Event Cameras&#xff08;CVPR2023&#xff09; 前言Abstract1. Introduction2. Related Work3. Method3.1. Feature Network3.2. Frame Attention Module3.3. Supervision 4. Experiments5. Con…...

蛇优化算法

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 蛇优化算法算法流程图初始化进化操作搜索阶段&#xff08;无食物&#xff09;——全局搜索搜索阶段&#xff08;有食物&#xff09;——局部搜索战斗模式交配模式 备…...

循环神经网络(RNN)简单介绍—包括TF和PyTorch源码,并给出详细注释

文章目录 循环神经网络&#xff08;RNN&#xff09;入门教程1. 循环神经网络的原理2. 循环神经网络的应用3. 使用keras框架实现循环神经网络3.1导入对应的库及加载数据集3.2.数据预处理3.3定义RNN模型3.4训练模型3.5测试模型 4.使用PyTorch框架实现上述功能—注释详细5.结论 循…...

Struts2 快速入门

Struts2 是一个基于 MVC 设计模式的 Java Web 应用程序框架&#xff0c;它可以帮助我们更加有效地开发 Web 应用程序。Struts2 采用了前端控制器模式&#xff0c;通过核心控制器 DispatchServlet 将所有请求进行集中处理&#xff0c;然后将请求分发到指定的 Action 中&#xff…...

关于PullToRefreshView下拉刷新失效问题

一、问题原因 昨天&#xff0c;突然一个问题丢在了我的头上&#xff0c;用户反馈说某某界面下拉刷新不好使啊&#xff0c;怎么回事。二话不说直接运行项目&#xff0c;经过测试&#xff0c;发现果然不好使。一看代码提交日期好家伙2020年&#xff0c;百思不得其解&#xff0c;…...

JAVA开发中的六大原则

JAVA开发中的六大原则&#xff0c;也被称为SOLID原则&#xff0c;是软件开发中常用的一组设计原则。这些原则提供了实现高质量、易于维护和可扩展软件的基本策略。 以下是JAVA开发中的六大原则以及它们的详细说明&#xff1a; 单一职责原则&#xff08;Single Responsibility…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...