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

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

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

引言

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

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

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

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

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

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

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

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

2 .基于計算思維教育的Euclidean算法研究

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

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

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

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

2.1 Euclidean算法的抽象表達

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

2.1.1 問題背景-丟番圖方程

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

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

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

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

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

2.1.2.1 除法算法定理

定理1 除法算法：對任意給定的整數(shù)a 和b，其中b > 0，存在唯一的整數(shù)對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ù)的嚴格數(shù)學(xué)定義

如果整數(shù)d為a和b的公約數(shù)，且對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é)表達

定理2 Euclidean算法：對任意給定的正整數(shù) a 和 b，計算最大公約數(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 擴展Euclidean算法

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

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

2.2 Euclidean算法的理論分析

首先對算法的正確性和有效性進行證明，再對算法實現(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） 步之后會終止。事實上，已經(jīng)證明，算法的時間復(fù)雜度為O（log b）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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ù)計算最大公約數(shù)

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

2.3.2 xgcd算法的實現(xiàn)（Python實現(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算法的綜合實驗

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

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

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

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

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

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

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

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

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

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

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

4. 結(jié)語

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

參考文獻

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

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

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

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

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

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

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

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

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