论文部分内容阅读
【摘 要】大数据和人工智能的发展，促使对计算思维更加系统和深刻的认知，其本质特征是计算模型和相应的算法设计，计算思维是新时代公民教育的基本内容，也是高职学生计算思维范式培养的重要内容。但在高职教育的算法思维问题求解领域，缺乏合适的案例进行贯穿问题求解框架的教学。本文对传统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<b。（证明从略）
在除法算法定理中，若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;
熊晓波，教授，硕士，广州涉外经济职业技术学院副校长兼信息工程学院院长。研究方向：计算机课程教学;
钟超婷，讲师，硕士，广州涉外经济职业技术学院华文与国际教育学院专任教师。研究方向：高职教学实践。
【关键词】 计算思维;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<b。（证明从略）
在除法算法定理中，若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;
熊晓波，教授，硕士，广州涉外经济职业技术学院副校长兼信息工程学院院长。研究方向：计算机课程教学;
钟超婷，讲师，硕士，广州涉外经济职业技术学院华文与国际教育学院专任教师。研究方向：高职教学实践。