高職計算思維教育視域下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;

熊曉波，教授，碩士，廣州涉外經濟職業技術學院副校長兼信息工程學院院長。研究方向：計算機課程教學;

鐘超婷，講師，碩士，廣州涉外經濟職業技術學院華文與國際教育學院專任教師。研究方向：高職教學實踐。