《Python编程从0到1》笔记3——欧几里得算法
本节以欧几里得算法(这是人类历史上最早记载的算法)为示例,向读者展示注释、文档字符串(docstring)、变量、循环、递归、缩进以及函数定义等Python语法要素。
欧几里得算法:“在数学中,辗转相除法,又称欧几里得算法(Euclidean algorithm),是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的《九章算术》。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。”---《维基百科.辗转相除法》
在实际操作中,可以使用带余数除法替代减法以减少步骤。下面是使用流程图绘制的算法示意图:
图 1.2 欧几里得算法流程图
在程序设计实践中,很少针对简单的程序绘制流程图。因为对于熟练的程序设计者来说,代码本身足以清晰地说明程序的执行流程。流程图往往用于描述大的软件系统的工作原理,或者用来辅助不够结构化的语言(如汇编语言)。
根据前述算法描述,计算252和105的最大公约数的计算步骤如下:
1.252除以105余42,问题转为求105和42的最大公约数;
2.105除以42余21,问题转为求42和21的最大公约数;
3.42除以21可以除尽,达到算法终点;
4.结论:252和105的最大公约数为21。
代码 1.2展示了欧几里得算法的Python实现:
#!/usr/bin/env python3 def gcd(a, b): while b!=0: a, b = b, a%b return a print(gcd(252, 105))
代码 1.2的核心部分定义了用来求最大公约数的函数gcd,为了便于说明,将这部分提取如图 1.3所示:
图 1.3 gcd 函数图示
代码说明:
- 第1行定义了有两个参数的函数gcd()。函数是一段可以被反复调用的代码。gcd()函数计算参数a和b的最大公约数,并通过第4行的return语句返回计算的结果;
- 第2行while语句,请读者注意到这行连同在排版上用4个空格缩进,这表示这条语句属于gcd()函数(没有缩进的最后一行print()语句就不属于gcd函数)。while关键字后面跟随的条件判断"b!=0"表示当这个条件为真时就反复执行之后的第3行语句;
- 第2行语句是赋值语句,将b的值和a除以b的余数,再次赋值给a和b。这行每执行一次,就完成了一次“辗转相除”。这行语句前有8个空格,表明这行语句受前一条while语句控制,直至while之后的"b!=0"条件不为真,才停止执行。换言之就是当某次余数为0时停止执行。这实际上就是上面描述的欧几里得算法;
- 第4行语句是返回语句,将最后剩下的公约数a返回;
- 最后使用print语句将gcd(252, 105)的返回值打印出来。
程序运行结果:
$ ./gcd.py 21
可以使用python3解释器的 -i 命令行选项在启动解释器交互界面时加载执行程序文本。加载执行程序文本后,可以继续键入代码以执行:
$ python3 -i gcd.py 21 >>> gcd(12, 4) 4 >>> gcd(36, 54) 18
这是一本很有趣很有趣的Python入门书,墙裂推荐。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
《Python编程从0到1》笔记2——表达式竟然也有副作用
在表达式的求值过程中,对状态的改变称为表达式的副作用。Python中内建的各种运算符(此处是狭义的含义,如加减乘除比较等运算符,并不包含用户自定义的运算符或函数)是没有副作用的,但各种函数调用时常带有副作用(比如各种输入输出函数)。在使用带有副作用的表达式构建复杂表达式时要格外留意,因为这可能带来程序员容易忽视的行为。如: if expA and expB : ... 这条语句用来测试表达式A B都为真的条件。expA and expB的计算具有短路性质,即如果A为假则整个表达式已然能够判断为假,表达式B不会被求值。如果表达式B包含函数调用,则意味着该函数不一定被调用。 不过总体说来,Python中副作用带来的麻烦并不多。程序员只要不在复杂表达式中嵌套带有副作用的函数即可避免这些容易混淆的情形。这种编码风格也能很容易遵守。[1][1] C程序员往往需要利用各种副作用(比如自增、赋值)写出简洁紧凑的程序,但在Python中,由于语法本身已经提供足够的简洁性,这门语言被刻意设计成避免这些写法。 这是一本很有趣很有趣的Python入门书,墙裂推荐。
- 下一篇
Guns 6.0发布,更简洁的后台管理系统
本次更新主要是为升级框架架构,升级UI界面! Guns 6.0更新说明: 前端框架升级easyweb 3.1.5,layui升级2.5.5。 优化整体前端UI界面,更加简洁,大气。 抽象出一套权限模型,利用接口进行权限控制和调用规则,方便在权限控制方面进行拓展。 替换掉了以往的ShiroKit,采用LoginContextHolder.getContext().getUser()获取当前登录用户。 权限框架替换为spring security + jwt,采用令牌登录方式,更加灵活可拓展,同时方便对接多系统SSO。 新增常量容器模型,对系统变量,常量,以及用户自定义的一些参数进行在线维护,在线刷新参数值,无需重启。 系统的验证码开关,顶部导航栏开关,系统默认密码等在常量容器进行维护,极大方便了系统使用。 所有页面加载的css和js进行版本控制,当升级项目时,更新对应版本号,可控制浏览器对缓存js和css的刷新。 增加用户的职务管理,可对用户进行职务绑定。 Guns 介绍: Guns基于SpringBoot 2,致力于做更简洁的后台管理系统,完美整合springmvc + spring ...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS6,CentOS7官方镜像安装Oracle11G
- CentOS8编译安装MySQL8.0.19