高职计算思维教育视域下Euclidean算法研究

耿江涛 匡增意 熊晓波 钟超婷

【摘  要】大数据和人工智能的发展，促使对计算思维更加系统和深刻的认知，其本质特征是计算模型和相应的算法设计，计算思维是新时代公民教育的基本内容，也是高职学生计算思维范式培养的重要内容。但在高职教育的算法思维问题求解领域，缺乏合适的案例进行贯穿问题求解框架的教学。本文对传统Euclidean算法进行计算思维教育视域下的研究，特别是通过对算法实现程序正确性的形式化证明，为高职院校在算法思维问题求解过程提供了适用、完整的案例。

【关键词】 计算思维;Euclidean算法;高职教育;程序正确性;形式化证明

引言

陈国良院士2020年在核心期刊《中国大学教学》发表《走向计算思维2.0》指出，自美国卡内基·梅隆大学周以真教授在权威期刊ACM通讯上提出计算思维（Computational Thinking）新概念以来，计算思维的概念不仅渗透到大学各学科的教学内容，且已延伸到中小学，计算思维被认为是继数学逻辑思维、物理实证思维后的第三种思维方式，成为新时代公民教育极为重要的基本内容。计算思维常被形象化的描述为计算机科学家解决问题时所用的思维，其本质特征是抽象与自动化。这一时期为计算思维1.0时代。

近年来，在大数据和人工智能推动下，促进了AI赋能的智能时代发展，产生众多新的计算模型及算法设计技术。2018年，国际教育技术学会（ISTE）发布《教育者计算思维能力标准》，强调教育者将计算思维融入学科教学的五方面标准。这些工作促进了对计算思维更加系统和深刻的认知，其本质是计算模型和相应的算法设计，进入计算思维2.0时代，体现出与1.0时代的显著不同的特点。

在此背景下，国内高校积极开展以计算思维为导向的计算机课程改革及研究，战德臣教授在对本科计算思维教育的探索中，使用计算之树概括了计算机课程计算思维教育空间，阐明了教学内容体系，并在新工科教育中开展了计算思维能力培养的实践，学者窦祥国也在积极探索适合高职教育的计算思维培养途径。

1. 高职计算思维教育的现状

与普通高校相比，计算思维培养在高职教育中的研究被严重忽视。在中国知网以“计算思维”为关键词检索核心期刊，查到文献超过330篇，其中与高职相关的文献仅有6篇。虽然程序设计课程被公认为实施计算思维教育的有力工具，但针对高职程序设计课程研究计算思维教育，在核心期刊上的文献仅有2篇，表明这方面的研究欠缺深度和广度。

从现有的研究和教学实践看，针对程序设计课程中算法类问题求解思维的教学，由于抽象、涉及知识点多的特点，应当采取案例化的教学方法阐释一般性的思维方式和抽象概念，通过案例教学培养学生计算思维能力。

实施案例教学，关键核心案例的选择，既要适合高职学生的特点和基础，避免难度过大;又不能过于简单而难以贯穿求解的全过程。然而现有的研究都无法提供适合高职学生水平、又能贯穿问题求解全过程进行计算思维能力培养的恰当案例。

Euclidean算法是非常成熟的算法，易于理解，实现代码复杂度低，有较完善的基础研究，已有各种程序设计语言的实现代码。因此选取Euclidean算法作为高职教育培养计算思维的案例，既能适应高职学生现有的基础，又能贯穿问题求解过程，是非常理想的典型案例。

2 .基于计算思维教育的Euclidean算法研究

陈国良院士指出，计算思维2.0的本质是计算模型及算法设计。具体到计算学科算法问题求解框架，抽象表示、理论分析和设计实现是其中重要的三個过程。设计实现是从工程实践的角度，用程序设计语言实现算法、构造计算系统来改造世界的过程;理论分析是从数学和计算理论的角度，对算法的正确性和有效性进行证明，是发现世界规律的过程;抽象表示是从科学抽象和数学分析的角度，感性认识世界构建计算模型的过程。认识世界→发现规律→改造世界，是计算学科发展的基本过程。

分析现阶段职业高校程序设计类课程的教学实际，可以看到，由于学生的数学基础薄弱、教师计算理论水平有限，特别是缺乏适当的教学案例，导致问题求解思维中的抽象表示和理论分析过程没有实质地开展，仅是将设计实现作为现阶段程序设计课程教学的核心内容，这对开展系统的计算思维教育极为不利。

Euclidean算法又称辗转相除法，是求两个正整数最大公约数（Greatest Common Divisor， gcd）的算法，从表面看仅涉及小学数学知识，非常容易理解，且Euclidean算法实现代码的复杂度较低，是高职实施计算思维教育中极为理想的案例算法。

下面从抽象表示、理论分析和设计实现三个方面对Euclidean算法进行研究。在此过程中，必须使用严格的数学和计算理论分析，故在研究方法上，充分考虑高职学生的特点，从简单的数学基础出发，摒弃数学家严密的证明过程，以学生易于理解的方式进行推导，在不失正确性基础上构建问题求解框架，以期培养学生建立完整的算法问题求解思维体系。

2.1 Euclidean算法的抽象表达

抽象表达是对客观事物进行描述、建立具体问题的计算模型的过程，是由感性认识到理性认识飞跃的关键环节。以下从Euclidean算法解决问题的背景出发，经过数学抽象处理，得到算法的抽象数学描述和具体的ANSI流程图表示。

2.1.1 问题背景-丢番图方程

丢番图方程是指求解一个或多个变量的整系数方程的整数解，是由代数之父、古希腊的大数学家丢番图（Diophantine）提出，是数论中基础的研究内容，其可解性被希尔伯特列为著名的23个数学问题中的第10题。

对于一元线性丢番图方程：ax=b，只要a能整除b，则方程有整数解，且解为b/a。

对于二元线性丢番图方程：ax+by=c，其可解性由Bézout定理给出，即先求a和b 的最大公约数d=gcd（a，b），若d能整除c，则此方程有整数解。

可见，整除、最大公约数是丢番图方程的研究基础，也是数论基础的研究内容。

2.1.2 数论基础

2.1.2.1 除法算法定理

定理1 除法算法：对任意给定的整数a 和b，其中b > 0，存在唯一的整数对q（商）和r（余数）使得 a=qb+r，且0≤r

在除法算法定理中，若r=0，则 a=qb，则称a可被b整除，记为 b | a 。

如果整数d满足d | a  且d | b ，则称 d 为a  和 b 的公约数。

2.1.2.2 最大公约数的严格数学定义

如果整数d为a和b的公约数，且对a  和  b的其他公约数 d′，都有d′|d ，则称 d 为 a 和  b的最大公约数，记为d=gcd（a，b） 。

2.1.3 Euclidean算法表述

2.1.3.1 Euclidean算法数学表达

定理2 Euclidean算法：对任意给定的正整数 a 和 b，计算最大公约数的算法过程为：gcd （a，b）=gcd（b，a mo d b） 其中a mo d b ，表示用a  除b  所得到的余数r 。

2.1.3.2 Euclidean算法的ANSI流程图表示

图1为Euclidean算法的ANSI流程图（Flowchart）表示，见算法程序的正确性证明部分。

2.1.3.3 扩展Euclidean算法

定理3 Bézout定理：对非零整数 a和b  ，存在整数r  和 s ，使得gcd（a，b）=ar+bs，  r 和s  称为Bézout系数。（证明从略）

Bézout定理表明，非零整数 a 和b  的最大公约数一定能表达为  a和 b 的线性组合。据此对Euclidean算法进行推广，得到扩展Euclidean算法（extended Euclidean algorithm，xgcd），不但能计算出两个非零整数 a 和 b 的最大公约数，还同时计算出这个最大公约数如何表达为 a 和 b 的线性组合，即Bézout系数。

2.2 Euclidean算法的理论分析

首先对算法的正确性和有效性进行证明，再对算法实现程序给予正确性的形式化证明。

2.2.1 Euclidean算法的正确性和有效性

以下用数论基础理论证明Euclidean算法的正确性和有效性。

2.2.1.1 Euclidean算法的正确性证明

要证明 gcd（a，b）=gcd（b，a mo d b） ，不失一般性，不妨设 a>b>0，则只要证明gcd（a，b）=gcd（a-b，b）  即可。

根据模除消减定理，算法在连续两次迭代后，a 和  b的值都至少消减了一半，意味着算法在O（log a） 步之后会终止。事实上，已经证明，算法的时间复杂度为O（log b）。

2.2.2 Euclidean算法实现程序的正确性

采用软件测试方法可以发现程序中的错误，却不能证明程序中没有错误。而程序正确性理论则可以证明程序的正确性。程序正确性的形式化方法能夠严格分析、证明程序及其性质，对于确保程序正确性和提高可信性具有基础性的作用。

根据程序正确性理论，程序的完全正确，等价于该程序是部分正确，同时又是终止的。因此，以下通过Floyd不变式断言法先证明Euclidean算法程序的部分正确性，再使用Knuth计数器法证明Euclidean算法程序的终止性，从而证明了Euclidean算法程序的完全正确性。

2.2.2.1 Floyd断言法证明程序的部分正确性

Floyd的不变式断言法是证明程序部分正确性的方法，主要通过以下三个步骤进行证明。

完全正确性：综合上述证明，程序是部分正确的且也是终止的，故程序是完全正确的。

2.3 Euclidean算法的设计实现

Euclidean算法gcd及扩展Euclidean算法xgcd都可以使用迭代和递归两种方式实现。另外，既可以使用C/C++语言实现，也可以使用Python语言实现。

2.3.1 gcd算法的实现示例

（1）递归实现gcd算法的C/C++版

（2）迭代实现gcd算法的C/C++版

（3） 高效二进制实现gcd算法（Stein算法）的C++版

算法核心是避免使用复杂的乘除法计算，而使用减法和更高效的移位操作来提高效率。

int binary_gcd（int a， int b） { int k = 0;

while （ ！（ （a | b） & 1 ） ）

a >>= 1， b >>= 1， k++;

while （ ！（ a & 1）） a >>= 1;

while （ b ） {

while （  ！（ b & 1） ） b >>= 1;

if （ b < a ） swap（ a， b）;

b = （ b - a ） >> 1;  }

return （ a << k ）;  }

（4）使用Python包中函数计算最大公约数

在Python中，还可以使用函数  或  计算最大公约数。

2.3.2 xgcd算法的实现（Python实现）

def xgcd（ a， b ） ：

r0， s0， r1， s1 = 1， 0， 0， 1

while b ：

q， a， b = a // b， b， a % b

r0， s0， r1， s1 = r1， s1， r0 - q * r1， s0 - q * s1

return a， r0， s0

3. Euclidean算法的综合实验

为测试Euclidean算法在各种实现下的效率即时间性能，设计了两组实验进行性能统计。

3.1 Euclidean算法C++版各种实现的实验

实验数据集：随机生成200对随机数，分别采用Euclidean算法的递归、迭代和二进制等三种实现程序，对每对随机数进行一百万次的求最大公约数。

实验结果：由于采用随机数，每次运行的结果有细微的差距，但以秒为单位时，运行时间基本稳定。具体情况是，递归实现运行约16.5秒，迭代实现运行约15.1秒，二进制实现运行约13.6秒。

结果分析：Euclidean算法的二进制实现最为高效，递归实现耗时最长，效率最低，这是由于会使用函数的递归调用，增加了额外的开销所致。

3.2 Euclidean算法C++与Python各种实现的实验

实验数据集：对两个大整数1160718174、316258250，分别采用Euclidean算法在C++、Python的递归、迭代和二进制等各三种实现程序，以及Python的语言包中的函数对这对大整数进行二千万次的求最大公约数。

实验结果：由于随机干扰，每次运行的结果有细微的差距，但以秒为单位时，运行时间基本稳定。具体情况是：

C++编程递归实现运行约2.7秒，迭代实现运行约1.5秒，二进制实现运行约1.5秒;

Python编程递归实现运行约31.1秒，迭代实现运行约21.0秒，二进制实现运行约13.5秒，函数包中的 运行约7.2秒，运行27.8秒。

结果分析：Euclidean算法的C++实现都非常高效，而各种Python实现都较C++慢几倍以上，在这些实现中，只有  运行程序时间最短，可以优先使用。

4. 结语

算法思维是典型的计算思维，也是其核心概念。掌握算法类问题的求解过程，树立完整的问题求解框架，对计算思维的培养具有重要的意义。以上对Euclidean算法的研究，旨在为高职计算思维教育提供典型的案例。在案例使用中，框架和求解的过程、结构是教学的核心内容;而证明和分析，则是建立计算模型的基础;算法实现的正确性和效率，则是计算思维实际应用的指南。

参考文献

[1] 陈国良，李廉，董荣胜.走向计算思维2.0[J].中国大学教学，2020（04）：24-30.

[2] Jannette M. Wing. Computational Thinking[J]. Communication of the ACM. 2006， 49，（3）：33-35.

[3] International Society for Technology in Education （ISTE）.Computational Thinking Competencies.[EB/OL].[2020-08-03]. https：//www.iste.org/standards/computational-thinking

[4] Peter J. Denning. Remaining trouble spots with computational thinking[J]. Communications of the ACM，2017，60（6）：33-39.

[5] 戰德臣，王浩.面向计算思维的大学计算机课程教学内容体系[J].中国大学教学， 2014（07）：59-66.

[6] 邓磊，战德臣，姜学锋.新工科教育中计算思维能力培养的价值探索与实践[J].高等工程教育研究，2020（02）：49-53.

[7] 窦祥国.面向计算思维培养的高职C程序设计案例教学研究[J]. 中国职业技术教育， 2019（32）：93-96.

[8] 王戟等. 形式化方法概貌[J]. 软件学报， 2019， 30（01）：33-61.

基金项目： 1. 广东省教育厅2019年度普通高校特色创新类项目（2019GKTSCX152）;2. 广东省教育厅2018年度广东省特色创新项目（2018GWTSCX055）; 3. 广东省教育厅2018年省高职质量工程教改项目（GDJG2019309）;4. 广州涉外经济职业技术学院2020年校级质量工程重点项目（SWZL202001）;5. 广州涉外经济职业技术学教育研究院2020年度专项研究重点课题（SWJY202001）; 6. 广州涉外经济职业技术学院2020年度校级重点科研项目（2018KY01）; 7. 广州涉外经济职业技术学院2018年校级教研项目（2018JY25）

作者简介：耿江涛，副教授，高级工程师，华南师范大学博士生，广州涉外经济职业技术学院华文与国际教育学院院长。研究方向：大数据应用，程序设计双语教学;

*通讯作者：匡增意，副教授，硕士，广州涉外经济职业技术学院常务副校长。研究方向：高职教育管理。E-mail： 2801756492@qq.com;

熊晓波，教授，硕士，广州涉外经济职业技术学院副校长兼信息工程学院院长。研究方向：计算机课程教学;

钟超婷，讲师，硕士，广州涉外经济职业技术学院华文与国际教育学院专任教师。研究方向：高职教学实践。