高職計(jì)算思維教育視域下Euclidean算法研究

耿江濤 匡增意 熊曉波 鐘超婷

【摘 ?要】大數(shù)據(jù)和人工智能的發(fā)展，促使對(duì)計(jì)算思維更加系統(tǒng)和深刻的認(rèn)知，其本質(zhì)特征是計(jì)算模型和相應(yīng)的算法設(shè)計(jì)，計(jì)算思維是新時(shí)代公民教育的基本內(nèi)容，也是高職學(xué)生計(jì)算思維范式培養(yǎng)的重要內(nèi)容。但在高職教育的算法思維問題求解領(lǐng)域，缺乏合適的案例進(jìn)行貫穿問題求解框架的教學(xué)。本文對(duì)傳統(tǒng)Euclidean算法進(jìn)行計(jì)算思維教育視域下的研究，特別是通過對(duì)算法實(shí)現(xiàn)程序正確性的形式化證明，為高職院校在算法思維問題求解過程提供了適用、完整的案例。

【關(guān)鍵詞】 計(jì)算思維;Euclidean算法;高職教育;程序正確性;形式化證明

引言

陳國(guó)良院士2020年在核心期刊《中國(guó)大學(xué)教學(xué)》發(fā)表《走向計(jì)算思維2.0》指出，自美國(guó)卡內(nèi)基·梅隆大學(xué)周以真教授在權(quán)威期刊ACM通訊上提出計(jì)算思維（Computational Thinking）新概念以來，計(jì)算思維的概念不僅滲透到大學(xué)各學(xué)科的教學(xué)內(nèi)容，且已延伸到中小學(xué)，計(jì)算思維被認(rèn)為是繼數(shù)學(xué)邏輯思維、物理實(shí)證思維后的第三種思維方式，成為新時(shí)代公民教育極為重要的基本內(nèi)容。計(jì)算思維常被形象化的描述為計(jì)算機(jī)科學(xué)家解決問題時(shí)所用的思維，其本質(zhì)特征是抽象與自動(dòng)化。這一時(shí)期為計(jì)算思維1.0時(shí)代。

近年來，在大數(shù)據(jù)和人工智能推動(dòng)下，促進(jìn)了AI賦能的智能時(shí)代發(fā)展，產(chǎn)生眾多新的計(jì)算模型及算法設(shè)計(jì)技術(shù)。2018年，國(guó)際教育技術(shù)學(xué)會(huì)（ISTE）發(fā)布《教育者計(jì)算思維能力標(biāo)準(zhǔn)》，強(qiáng)調(diào)教育者將計(jì)算思維融入學(xué)科教學(xué)的五方面標(biāo)準(zhǔn)。這些工作促進(jìn)了對(duì)計(jì)算思維更加系統(tǒng)和深刻的認(rèn)知，其本質(zhì)是計(jì)算模型和相應(yīng)的算法設(shè)計(jì)，進(jìn)入計(jì)算思維2.0時(shí)代，體現(xiàn)出與1.0時(shí)代的顯著不同的特點(diǎn)。

在此背景下，國(guó)內(nèi)高校積極開展以計(jì)算思維為導(dǎo)向的計(jì)算機(jī)課程改革及研究，戰(zhàn)德臣教授在對(duì)本科計(jì)算思維教育的探索中，使用計(jì)算之樹概括了計(jì)算機(jī)課程計(jì)算思維教育空間，闡明了教學(xué)內(nèi)容體系，并在新工科教育中開展了計(jì)算思維能力培養(yǎng)的實(shí)踐，學(xué)者竇祥國(guó)也在積極探索適合高職教育的計(jì)算思維培養(yǎng)途徑。

1. 高職計(jì)算思維教育的現(xiàn)狀

與普通高校相比，計(jì)算思維培養(yǎng)在高職教育中的研究被嚴(yán)重忽視。在中國(guó)知網(wǎng)以“計(jì)算思維”為關(guān)鍵詞檢索核心期刊，查到文獻(xiàn)超過330篇，其中與高職相關(guān)的文獻(xiàn)僅有6篇。雖然程序設(shè)計(jì)課程被公認(rèn)為實(shí)施計(jì)算思維教育的有力工具，但針對(duì)高職程序設(shè)計(jì)課程研究計(jì)算思維教育，在核心期刊上的文獻(xiàn)僅有2篇，表明這方面的研究欠缺深度和廣度。

從現(xiàn)有的研究和教學(xué)實(shí)踐看，針對(duì)程序設(shè)計(jì)課程中算法類問題求解思維的教學(xué)，由于抽象、涉及知識(shí)點(diǎn)多的特點(diǎn)，應(yīng)當(dāng)采取案例化的教學(xué)方法闡釋一般性的思維方式和抽象概念，通過案例教學(xué)培養(yǎng)學(xué)生計(jì)算思維能力。

實(shí)施案例教學(xué)，關(guān)鍵核心案例的選擇，既要適合高職學(xué)生的特點(diǎn)和基礎(chǔ)，避免難度過大;又不能過于簡(jiǎn)單而難以貫穿求解的全過程。然而現(xiàn)有的研究都無法提供適合高職學(xué)生水平、又能貫穿問題求解全過程進(jìn)行計(jì)算思維能力培養(yǎng)的恰當(dāng)案例。

Euclidean算法是非常成熟的算法，易于理解，實(shí)現(xiàn)代碼復(fù)雜度低，有較完善的基礎(chǔ)研究，已有各種程序設(shè)計(jì)語言的實(shí)現(xiàn)代碼。因此選取Euclidean算法作為高職教育培養(yǎng)計(jì)算思維的案例，既能適應(yīng)高職學(xué)生現(xiàn)有的基礎(chǔ)，又能貫穿問題求解過程，是非常理想的典型案例。

2 .基于計(jì)算思維教育的Euclidean算法研究

陳國(guó)良院士指出，計(jì)算思維2.0的本質(zhì)是計(jì)算模型及算法設(shè)計(jì)。具體到計(jì)算學(xué)科算法問題求解框架，抽象表示、理論分析和設(shè)計(jì)實(shí)現(xiàn)是其中重要的三個(gè)過程。設(shè)計(jì)實(shí)現(xiàn)是從工程實(shí)踐的角度，用程序設(shè)計(jì)語言實(shí)現(xiàn)算法、構(gòu)造計(jì)算系統(tǒng)來改造世界的過程;理論分析是從數(shù)學(xué)和計(jì)算理論的角度，對(duì)算法的正確性和有效性進(jìn)行證明，是發(fā)現(xiàn)世界規(guī)律的過程;抽象表示是從科學(xué)抽象和數(shù)學(xué)分析的角度，感性認(rèn)識(shí)世界構(gòu)建計(jì)算模型的過程。認(rèn)識(shí)世界→發(fā)現(xiàn)規(guī)律→改造世界，是計(jì)算學(xué)科發(fā)展的基本過程。

分析現(xiàn)階段職業(yè)高校程序設(shè)計(jì)類課程的教學(xué)實(shí)際，可以看到，由于學(xué)生的數(shù)學(xué)基礎(chǔ)薄弱、教師計(jì)算理論水平有限，特別是缺乏適當(dāng)?shù)慕虒W(xué)案例，導(dǎo)致問題求解思維中的抽象表示和理論分析過程沒有實(shí)質(zhì)地開展，僅是將設(shè)計(jì)實(shí)現(xiàn)作為現(xiàn)階段程序設(shè)計(jì)課程教學(xué)的核心內(nèi)容，這對(duì)開展系統(tǒng)的計(jì)算思維教育極為不利。

Euclidean算法又稱輾轉(zhuǎn)相除法，是求兩個(gè)正整數(shù)最大公約數(shù)（Greatest Common Divisor， gcd）的算法，從表面看僅涉及小學(xué)數(shù)學(xué)知識(shí)，非常容易理解，且Euclidean算法實(shí)現(xiàn)代碼的復(fù)雜度較低，是高職實(shí)施計(jì)算思維教育中極為理想的案例算法。

下面從抽象表示、理論分析和設(shè)計(jì)實(shí)現(xiàn)三個(gè)方面對(duì)Euclidean算法進(jìn)行研究。在此過程中，必須使用嚴(yán)格的數(shù)學(xué)和計(jì)算理論分析，故在研究方法上，充分考慮高職學(xué)生的特點(diǎn)，從簡(jiǎn)單的數(shù)學(xué)基礎(chǔ)出發(fā)，摒棄數(shù)學(xué)家嚴(yán)密的證明過程，以學(xué)生易于理解的方式進(jìn)行推導(dǎo)，在不失正確性基礎(chǔ)上構(gòu)建問題求解框架，以期培養(yǎng)學(xué)生建立完整的算法問題求解思維體系。

2.1 Euclidean算法的抽象表達(dá)

抽象表達(dá)是對(duì)客觀事物進(jìn)行描述、建立具體問題的計(jì)算模型的過程，是由感性認(rèn)識(shí)到理性認(rèn)識(shí)飛躍的關(guān)鍵環(huán)節(jié)。以下從Euclidean算法解決問題的背景出發(fā)，經(jīng)過數(shù)學(xué)抽象處理，得到算法的抽象數(shù)學(xué)描述和具體的ANSI流程圖表示。

2.1.1 問題背景-丟番圖方程

丟番圖方程是指求解一個(gè)或多個(gè)變量的整系數(shù)方程的整數(shù)解，是由代數(shù)之父、古希臘的大數(shù)學(xué)家丟番圖（Diophantine）提出，是數(shù)論中基礎(chǔ)的研究?jī)?nèi)容，其可解性被希爾伯特列為著名的23個(gè)數(shù)學(xué)問題中的第10題。

對(duì)于一元線性丟番圖方程：ax=b，只要a能整除b，則方程有整數(shù)解，且解為b/a。

對(duì)于二元線性丟番圖方程：ax+by=c，其可解性由Bézout定理給出，即先求a和b 的最大公約數(shù)d=gcd（a，b），若d能整除c，則此方程有整數(shù)解。

可見，整除、最大公約數(shù)是丟番圖方程的研究基礎(chǔ)，也是數(shù)論基礎(chǔ)的研究?jī)?nèi)容。

2.1.2 數(shù)論基礎(chǔ)

2.1.2.1 除法算法定理

定理1 除法算法：對(duì)任意給定的整數(shù)a 和b，其中b > 0，存在唯一的整數(shù)對(duì)q（商）和r（余數(shù)）使得 a=qb+r，且0≤r

在除法算法定理中，若r=0，則 a=qb，則稱a可被b整除，記為 b | a 。

如果整數(shù)d滿足d | a ?且d | b ，則稱 d 為a ?和 b 的公約數(shù)。

2.1.2.2 最大公約數(shù)的嚴(yán)格數(shù)學(xué)定義

如果整數(shù)d為a和b的公約數(shù)，且對(duì)a ?和 ?b的其他公約數(shù) d′，都有d′|d ，則稱 d 為 a 和 ?b的最大公約數(shù)，記為d=gcd（a，b） 。

2.1.3 Euclidean算法表述

2.1.3.1 Euclidean算法數(shù)學(xué)表達(dá)

定理2 Euclidean算法：對(duì)任意給定的正整數(shù) a 和 b，計(jì)算最大公約數(shù)的算法過程為：gcd （a，b）=gcd（b，a mo d b） 其中a mo d b ，表示用a ?除b ?所得到的余數(shù)r 。

2.1.3.2 Euclidean算法的ANSI流程圖表示

圖1為Euclidean算法的ANSI流程圖（Flowchart）表示，見算法程序的正確性證明部分。

2.1.3.3 擴(kuò)展Euclidean算法

定理3 Bézout定理：對(duì)非零整數(shù) a和b ?，存在整數(shù)r ?和 s ，使得gcd（a，b）=ar+bs， ?r 和s ?稱為Bézout系數(shù)。（證明從略）

Bézout定理表明，非零整數(shù) a 和b ?的最大公約數(shù)一定能表達(dá)為 ?a和 b 的線性組合。據(jù)此對(duì)Euclidean算法進(jìn)行推廣，得到擴(kuò)展Euclidean算法（extended Euclidean algorithm，xgcd），不但能計(jì)算出兩個(gè)非零整數(shù) a 和 b 的最大公約數(shù)，還同時(shí)計(jì)算出這個(gè)最大公約數(shù)如何表達(dá)為 a 和 b 的線性組合，即Bézout系數(shù)。

2.2 Euclidean算法的理論分析

首先對(duì)算法的正確性和有效性進(jìn)行證明，再對(duì)算法實(shí)現(xiàn)程序給予正確性的形式化證明。

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

以下用數(shù)論基礎(chǔ)理論證明Euclidean算法的正確性和有效性。

2.2.1.1 Euclidean算法的正確性證明

要證明 gcd（a，b）=gcd（b，a mo d b） ，不失一般性，不妨設(shè) a>b>0，則只要證明gcd（a，b）=gcd（a-b，b） ?即可。

根據(jù)模除消減定理，算法在連續(xù)兩次迭代后，a 和 ?b的值都至少消減了一半，意味著算法在O（log a） 步之后會(huì)終止。事實(shí)上，已經(jīng)證明，算法的時(shí)間復(fù)雜度為O（log b）。

2.2.2 Euclidean算法實(shí)現(xiàn)程序的正確性

采用軟件測(cè)試方法可以發(fā)現(xiàn)程序中的錯(cuò)誤，卻不能證明程序中沒有錯(cuò)誤。而程序正確性理論則可以證明程序的正確性。程序正確性的形式化方法能夠嚴(yán)格分析、證明程序及其性質(zhì)，對(duì)于確保程序正確性和提高可信性具有基礎(chǔ)性的作用。

根據(jù)程序正確性理論，程序的完全正確，等價(jià)于該程序是部分正確，同時(shí)又是終止的。因此，以下通過Floyd不變式斷言法先證明Euclidean算法程序的部分正確性，再使用Knuth計(jì)數(shù)器法證明Euclidean算法程序的終止性，從而證明了Euclidean算法程序的完全正確性。

2.2.2.1 Floyd斷言法證明程序的部分正確性

Floyd的不變式斷言法是證明程序部分正確性的方法，主要通過以下三個(gè)步驟進(jìn)行證明。

完全正確性：綜合上述證明，程序是部分正確的且也是終止的，故程序是完全正確的。

2.3 Euclidean算法的設(shè)計(jì)實(shí)現(xiàn)

Euclidean算法gcd及擴(kuò)展Euclidean算法xgcd都可以使用迭代和遞歸兩種方式實(shí)現(xiàn)。另外，既可以使用C/C++語言實(shí)現(xiàn)，也可以使用Python語言實(shí)現(xiàn)。

2.3.1 gcd算法的實(shí)現(xiàn)示例

（1）遞歸實(shí)現(xiàn)gcd算法的C/C++版

（2）迭代實(shí)現(xiàn)gcd算法的C/C++版

（3） 高效二進(jìn)制實(shí)現(xiàn)gcd算法（Stein算法）的C++版

算法核心是避免使用復(fù)雜的乘除法計(jì)算，而使用減法和更高效的移位操作來提高效率。

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包中函數(shù)計(jì)算最大公約數(shù)

在Python中，還可以使用函數(shù) ?或 ?計(jì)算最大公約數(shù)。

2.3.2 xgcd算法的實(shí)現(xiàn)（Python實(shí)現(xiàn)）

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算法的綜合實(shí)驗(yàn)

為測(cè)試Euclidean算法在各種實(shí)現(xiàn)下的效率即時(shí)間性能，設(shè)計(jì)了兩組實(shí)驗(yàn)進(jìn)行性能統(tǒng)計(jì)。

3.1 Euclidean算法C++版各種實(shí)現(xiàn)的實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)集：隨機(jī)生成200對(duì)隨機(jī)數(shù)，分別采用Euclidean算法的遞歸、迭代和二進(jìn)制等三種實(shí)現(xiàn)程序，對(duì)每對(duì)隨機(jī)數(shù)進(jìn)行一百萬次的求最大公約數(shù)。

實(shí)驗(yàn)結(jié)果：由于采用隨機(jī)數(shù)，每次運(yùn)行的結(jié)果有細(xì)微的差距，但以秒為單位時(shí)，運(yùn)行時(shí)間基本穩(wěn)定。具體情況是，遞歸實(shí)現(xiàn)運(yùn)行約16.5秒，迭代實(shí)現(xiàn)運(yùn)行約15.1秒，二進(jìn)制實(shí)現(xiàn)運(yùn)行約13.6秒。

結(jié)果分析：Euclidean算法的二進(jìn)制實(shí)現(xiàn)最為高效，遞歸實(shí)現(xiàn)耗時(shí)最長(zhǎng)，效率最低，這是由于會(huì)使用函數(shù)的遞歸調(diào)用，增加了額外的開銷所致。

3.2 Euclidean算法C++與Python各種實(shí)現(xiàn)的實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)集：對(duì)兩個(gè)大整數(shù)1160718174、316258250，分別采用Euclidean算法在C++、Python的遞歸、迭代和二進(jìn)制等各三種實(shí)現(xiàn)程序，以及Python的語言包中的函數(shù)對(duì)這對(duì)大整數(shù)進(jìn)行二千萬次的求最大公約數(shù)。

實(shí)驗(yàn)結(jié)果：由于隨機(jī)干擾，每次運(yùn)行的結(jié)果有細(xì)微的差距，但以秒為單位時(shí)，運(yùn)行時(shí)間基本穩(wěn)定。具體情況是：

C++編程遞歸實(shí)現(xiàn)運(yùn)行約2.7秒，迭代實(shí)現(xiàn)運(yùn)行約1.5秒，二進(jìn)制實(shí)現(xiàn)運(yùn)行約1.5秒;

Python編程遞歸實(shí)現(xiàn)運(yùn)行約31.1秒，迭代實(shí)現(xiàn)運(yùn)行約21.0秒，二進(jìn)制實(shí)現(xiàn)運(yùn)行約13.5秒，函數(shù)包中的 運(yùn)行約7.2秒，運(yùn)行27.8秒。

結(jié)果分析：Euclidean算法的C++實(shí)現(xiàn)都非常高效，而各種Python實(shí)現(xiàn)都較C++慢幾倍以上，在這些實(shí)現(xiàn)中，只有 ?運(yùn)行程序時(shí)間最短，可以優(yōu)先使用。

4. 結(jié)語

算法思維是典型的計(jì)算思維，也是其核心概念。掌握算法類問題的求解過程，樹立完整的問題求解框架，對(duì)計(jì)算思維的培養(yǎng)具有重要的意義。以上對(duì)Euclidean算法的研究，旨在為高職計(jì)算思維教育提供典型的案例。在案例使用中，框架和求解的過程、結(jié)構(gòu)是教學(xué)的核心內(nèi)容;而證明和分析，則是建立計(jì)算模型的基礎(chǔ);算法實(shí)現(xiàn)的正確性和效率，則是計(jì)算思維實(shí)際應(yīng)用的指南。

參考文獻(xiàn)

[1] 陳國(guó)良，李廉，董榮勝.走向計(jì)算思維2.0[J].中國(guó)大學(xué)教學(xué)，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] 戰(zhàn)德臣，王浩.面向計(jì)算思維的大學(xué)計(jì)算機(jī)課程教學(xué)內(nèi)容體系[J].中國(guó)大學(xué)教學(xué)， 2014（07）：59-66.

[6] 鄧?yán)?，?zhàn)德臣，姜學(xué)鋒.新工科教育中計(jì)算思維能力培養(yǎng)的價(jià)值探索與實(shí)踐[J].高等工程教育研究，2020（02）：49-53.

[7] 竇祥國(guó).面向計(jì)算思維培養(yǎng)的高職C程序設(shè)計(jì)案例教學(xué)研究[J]. 中國(guó)職業(yè)技術(shù)教育， 2019（32）：93-96.

[8] 王戟等. 形式化方法概貌[J]. 軟件學(xué)報(bào)， 2019， 30（01）：33-61.

基金項(xiàng)目： 1. 廣東省教育廳2019年度普通高校特色創(chuàng)新類項(xiàng)目（2019GKTSCX152）;2. 廣東省教育廳2018年度廣東省特色創(chuàng)新項(xiàng)目（2018GWTSCX055）; 3. 廣東省教育廳2018年省高職質(zhì)量工程教改項(xiàng)目（GDJG2019309）;4. 廣州涉外經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院2020年校級(jí)質(zhì)量工程重點(diǎn)項(xiàng)目（SWZL202001）;5. 廣州涉外經(jīng)濟(jì)職業(yè)技術(shù)學(xué)教育研究院2020年度專項(xiàng)研究重點(diǎn)課題（SWJY202001）; 6. 廣州涉外經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院2020年度校級(jí)重點(diǎn)科研項(xiàng)目（2018KY01）; 7. 廣州涉外經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院2018年校級(jí)教研項(xiàng)目（2018JY25）

作者簡(jiǎn)介：耿江濤，副教授，高級(jí)工程師，華南師范大學(xué)博士生，廣州涉外經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院華文與國(guó)際教育學(xué)院院長(zhǎng)。研究方向：大數(shù)據(jù)應(yīng)用，程序設(shè)計(jì)雙語教學(xué);

*通訊作者：匡增意，副教授，碩士，廣州涉外經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院常務(wù)副校長(zhǎng)。研究方向：高職教育管理。E-mail： 2801756492@qq.com;

熊曉波，教授，碩士，廣州涉外經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院副校長(zhǎng)兼信息工程學(xué)院院長(zhǎng)。研究方向：計(jì)算機(jī)課程教學(xué);

鐘超婷，講師，碩士，廣州涉外經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院華文與國(guó)際教育學(xué)院專任教師。研究方向：高職教學(xué)實(shí)踐。