《Python编程从0到1》笔记3——欧几里得算法

  • 时间:
  • 浏览:0

代码 1.2展示了欧几里得算法的Python实现:

本节以欧几里得算法(这是人类历史上最早记载的算法)为示例,向读者展示注释、文档字符串(docstring)、变量、循环、递归、缩进以及函数定义等Python语法要素。

代码说明:

须要使用python3解释器的 -i 命令行选项在启动解释器交互界面时加载执行应用程序文本。加载执行应用程序文本后,须要继续键入代码以执行:

在应用程序设计实践中,很少针对简单的应用程序绘制流程图。可能性对于熟练的应用程序设计者来说,代码两种足以清晰地说明应用程序的执行流程。流程图往往用于描述大的软件系统的工作原理,可能性用来辅助过高 特征化的语言(如汇编语言)。

应用程序结果:

这是一本很有趣很有趣的Python入门书,墙裂推荐。

在实际操作中,须要使用带余数除法替代减法以减少步骤。下面是使用流程图绘制的算法示意图:



图 1.2 欧几里得算法流程图

欧几里得算法:“在数学中,辗转相除法,又称欧几里得算法(Euclidean algorithm),是求最大公约数的算法。辗转相除法首次经常出显于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在中国则须要追溯至东汉经常出显的《九章算术》。另4个整数的最大公约数是不能共同整除它们的最大的正整数。辗转相除法基于如下原理:另4个整数的最大公约数等于其中较小的数和两数的差的最大公约数。”---《维基百科.辗转相除法》

代码 1.2的核心要素定义了用来求最大公约数的函数gcd,为了便于说明,将这要素提取如图 1.3所示:



图 1.3 gcd 函数图示

根据前述算法描述,计算252和105的最大公约数的计算步骤如下:

1.252除以105余42,什么的问题转为求105和42的最大公约数;

2.105除以42余21,什么的问题转为求42和21的最大公约数;

3.42除以21须要除尽,达到算法终点;

4.结论:252和105的最大公约数为21。