袁紅娟，朱 曄，酈 麗

(泰州學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，江蘇 泰州 225300)

0 引言

計算思維是運用計算機科學(xué)的基礎(chǔ)概念進行問題求解、系統(tǒng)設(shè)計，以及人類行為理解等涵蓋計算機科學(xué)之廣度的一系列思維活動[1]。計算思維概念由美國卡內(nèi)基·卡梅隆大學(xué)計算機科學(xué)系主任周以真教授于2006年首次提出。

“通過中美高水平大學(xué)課堂教學(xué)的對比，可以看到一流大學(xué)教育的目的：不只是學(xué)知識、學(xué)能力，而且是學(xué)會一種思維方式，培養(yǎng)學(xué)生批判性獨立思考的能力，并為終身學(xué)習(xí)打下基礎(chǔ)”。《計算機科學(xué)導(dǎo)論》課程是計算機專業(yè)本科生的入門課程，肩負著引導(dǎo)大一新生正確認知和學(xué)習(xí)計算機科學(xué)知識的重任。除了理論知識的學(xué)習(xí)，在實踐教學(xué)設(shè)計中，重點培養(yǎng)學(xué)生獨立的計算思維。

2018年，在廣州大學(xué)舉辦的“第十一屆中國大學(xué)教學(xué)論壇”上，吳巖司長提出：“課程是教育最微觀問題，解決的是教育最根本問題。各高校要全面梳理各門課程的教學(xué)內(nèi)容，淘汰‘水課’，打造‘金課’，合理提升學(xué)業(yè)挑戰(zhàn)度，拓展課程深度，切實提高課程教學(xué)質(zhì)量”。上述提議，強化了人才培養(yǎng)的核心地位，一流本科教育的基礎(chǔ)地位，要求建設(shè)中國大學(xué)“金課”。

泰州學(xué)院計算機科學(xué)與技術(shù)學(xué)院，以《計算機科學(xué)導(dǎo)論》作為打造“金課”課程教學(xué)改革的先鋒，相繼申報了校級重點教改課題、校級精品在線開放課程建設(shè)項目。課程實踐教學(xué)設(shè)計中，摒棄原先辦公軟件的學(xué)習(xí)，引入Raptor流程圖軟件進行算法設(shè)計與驗證，提高學(xué)生分析問題、抽象建模、解決問題的能力?！队嬎銠C科學(xué)導(dǎo)論》在線課程進行課程教學(xué)視頻、題庫資源建設(shè)的同時，與同期教學(xué)的《Python程序設(shè)計》課程聯(lián)動，進行互補教學(xué)。通過《計算機科學(xué)導(dǎo)論》課程學(xué)習(xí)并深入理解算法思想，以Raptor工具實現(xiàn)算法抽象、建模、轉(zhuǎn)換，最后用Python語言將算法設(shè)計并實現(xiàn)，將學(xué)生的計算思維培養(yǎng)貫穿于整個教學(xué)過程，讓學(xué)生獲得獨立解決問題的綜合能力。

1 實踐教學(xué)內(nèi)容設(shè)計

為培養(yǎng)學(xué)生的計算思維，體現(xiàn)“金課”高階性、創(chuàng)新性、挑戰(zhàn)度等特點，《計算機科學(xué)導(dǎo)論》在實踐教學(xué)中合理提升實驗挑戰(zhàn)度，拓展知識的深度，提高教學(xué)質(zhì)量。實踐教學(xué)一共設(shè)置8個實驗，內(nèi)容如下：

實驗1：順序結(jié)構(gòu)程序設(shè)計，掌握Raptor算術(shù)、邏輯、關(guān)系運算符的使用，掌握常量、變量及常用函數(shù)的使用。

實驗2：選擇結(jié)構(gòu)程序設(shè)計，掌握決策表達式的使用，掌握單分支、雙分支、多分支的使用。

實驗3：循環(huán)結(jié)構(gòu)程序設(shè)計，掌握循環(huán)控制的基本結(jié)構(gòu)，掌握決策語句的3種測試方式，掌握循環(huán)結(jié)構(gòu)的嵌套。

實驗4：數(shù)組，掌握一維數(shù)組、二維數(shù)組、字符數(shù)組的創(chuàng)建和使用。

實驗5：子程序和子圖，掌握子程序的創(chuàng)建、參數(shù)的設(shè)置、傳遞；掌握子圖的創(chuàng)建，理解變量的生命周期。

實驗6：遞歸和迭代，掌握遞歸的方法和思維，掌握迭代的方法和思維。

實驗7：查找，掌握順序查找、二分查找、分塊查找等的方法和使用。

實驗8：排序，掌握插入排序、冒泡排序、選擇排序等的方法和使用。

實驗1-4是基本的設(shè)計性實驗，讓學(xué)生使用Raptor工具對問題進行抽象和建模，用流程圖解決簡單問題；實驗5-8是綜合性實驗，由基礎(chǔ)到應(yīng)用，層層遞進，將知識、能力、素質(zhì)有機融合，培養(yǎng)學(xué)生解決復(fù)雜問題的綜合能力和高級思維。

2 實踐教學(xué)方式創(chuàng)新

為提高教學(xué)效果，泰州學(xué)院大力推動在線開放課程的建設(shè)，打造線上金課、線下金課、線上線下混合式金課等。2018年，《計算機科學(xué)導(dǎo)論》被立項為校級在線開放課程。課程教學(xué)中，利用現(xiàn)有的在線教學(xué)資源，實現(xiàn)線上、線下混合式教學(xué)改革。在實踐教學(xué)設(shè)計中，體現(xiàn)高階性、創(chuàng)新性、挑戰(zhàn)度的特點，合理提升實驗難度，并及時反饋、總結(jié)實驗效果，提高實踐教學(xué)含金量。

例如：實驗7遞歸，首先介紹常規(guī)的遞歸思想，列舉典型案例——階乘、漢諾塔游戲和斐波那契數(shù)列，然后結(jié)合“藍橋杯”程序設(shè)計大賽，布置出具有挑戰(zhàn)性的拓展實驗作業(yè)，全面鍛煉學(xué)生思維能力。具體的教學(xué)過程如下：

2.1 實踐教學(xué)案例引入

如果用a b c d這4個字母組成一個串，有4!=24種，如果把它們排個序，每個串都對應(yīng)一個序號：

abcd 0

abdc 1

acbd 2

acdb 3

adbc 4

adcb 5

bacd 6

badc 7

bcad 8

bcda 9

bdac 10

bdca 11

cabd 12

cadb 13

cbad 14

cbda 15

cdab 16

cdba 17

…

現(xiàn)在有不多于10個兩兩不同的小寫字母，給出它們組成的串，求出該串在所有排列中的序號。

樣例輸入：bdca

樣例輸出：11

要求學(xué)生基于遞歸或遞推思想，用Raptor工具抽象建模，以流程圖方式解決上述問題，并用Python語言編程實現(xiàn)。

2.2 實踐教學(xué)案例原理

該實踐教學(xué)案例反映的是康托展開式，該公式實現(xiàn)了由字符c1到cn組成的全排列序列到其編號之間的一種映射，常用于構(gòu)建哈希表時的空間壓縮[4]。

康托公式：X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+…+a2*1!+a1*0!

由c1到cn這n個字符組成的全排列，共n!個，按每個全排列組成的字符從小到大進行排列，并對每個序列進行編號，記為X(從0開始)。

比如說a到d組成的全排列中，abcd對應(yīng)編號0，abdc對應(yīng)編號1。

對于ai的理解：

對a到d的全排列中，考察cbad，則

a4={c在集合(c,b,a,d)中是第幾大的元素}=2

a3={b在集合(b,a,d)中是第幾大的元素}=1

a2={a在集合(a,d)中是第幾大的元素}=0

a1={d在集合(d)中是第幾大的元素}=0

康托公式中的每一項依次對應(yīng)全排列序列中的每個元素，并按上述規(guī)則映射,則X=2*3!+1*2!+0*1!+0*0!=14，即cbad對應(yīng)的編號為14。

教學(xué)要求：分別用遞推和遞歸方法解決該問題。

3 遞推算法實現(xiàn)

遞推算法以初始值為基礎(chǔ)，用相同的運算規(guī)律，逐次重復(fù)運算，直至運算結(jié)束。從“起點”重復(fù)相同的方法直至到達一定“邊界”，用循環(huán)可以實現(xiàn)[2]。其思想是把一個復(fù)雜龐大的計算過程轉(zhuǎn)化為簡單過程的多次重復(fù)。

3.1 問題分析

若字母長度為3，排列及序號如下：

abc 0

bcb 1

bac 2

bca 3

cab 4

cba 5

字符串s，用n=len(s)計算字符串s的長度。定義計算字符串s序號的遞推函數(shù)func(s)。

若s=“cba”。

用i逐個遍歷s字符串的索引，循環(huán)：

當(dāng)i=0時，首字母c在字符串“cba”中排列為2，序號變化幅度為：2！，因此得到首字母c在字符串“cba”中的排列序號：2*2！，即4。

當(dāng)i=1時，字母b在剩余字符串“ba”中的排列為1，序號變化幅度為：1！，因此得到字母b在字符串“ba”中的排列序號為：1*1！，即1。

當(dāng)i=2時，字母a在剩余字符串“a”中的排列為0，序號變化幅度為：0！，因此得到字母a在字符串“a”中的排列序號為0*0！，即0。

直至i>=len(s)結(jié)束。

綜合以上得到字符串s=“cba”的排列序號為：4+1+0=5。

算法中要多次調(diào)用階乘函數(shù)，比如計算n!,用fac(n)表示，下文均如此調(diào)用。

正確計算出當(dāng)前字母在剩余字符串中排列位置，即階乘的系數(shù)值，首先將字符串s，自索引i開始截取剩余的字符串，放置到t中；然后對字符串t升序排列；最后查找出字母s[i]在字符串t中索引值m，m即為階乘的系數(shù)值。

3.2 遞推函數(shù)偽代碼

func(s)

輸入：字符串s

輸出：字符串s的排列序號

計算字符串s的長度n=len(s)

字符序號初始值sum=0

遍歷字符串s的每個索引i：

用t截取字符串s從索引i開始的剩余字符串

對t升序排列

找出s[i]在t中的索引值m

計算當(dāng)前字符s[i]在排列中的序號sum=sum+m*fac(n-(i+1))

返回排列序號sum

3.3 python語言實現(xiàn)遞推函數(shù)

def func(s): #定義函數(shù)fun(s)，計算字符串s的排列序號

n=len(s) #n計算字符串s的長度

sum=0 #sum計算字符串的排列序號

for i in range(n): #遍歷字符串s的各索引

t=s[i:] #用t截取索引i開始的剩余字符串

t=sorted(t) #對字符串t進行升序排列

m=t.index(s[i]) #找出字符s[i]在t中的索引值

sum=sum+m*fac(n-(i+1)) #計算當(dāng)前s[0:i+1]在字符排列中的序號

return sum #返回字符排列序號

4 遞歸算法實現(xiàn)

在數(shù)學(xué)與計算機科學(xué)中，遞歸(Recursion)是指在函數(shù)的定義中使用函數(shù)自身的方法[3]。遞歸是一種奇妙的思維方式，主要分為兩個階段：

(1)遞推歸納。把問題轉(zhuǎn)化為比原問題規(guī)模小的同類問題。如計算n!，可以遞推歸納到計算n*(n-1)!;計算(n-1)!，可以遞推歸納到計算(n-1)*(n-1)!……。

(2)遞歸終止。當(dāng)問題小到一定規(guī)模時，結(jié)束遞歸，逐層返回。如當(dāng)遞推歸納到計算1!，得到1!=1或0!=1，則開始逐層返回。

因此，計算n!的函數(shù)，python代碼如下：

def fac(n):

if n==1 or n==0:

return 1

else:

return n*fac(n-1)

4.1 問題分析

若字母長度為3，排列及序號如下：

abc 0

bcb 1

bac 2

bca 3

cab 4

cba 5

若字母長度為2，排列及序號如下：

ab 0

ba 1

若字母長度為1，排列及序號如下：

a 0

字符串s，用n=len(s)計算字符串s的長度。用遞歸函數(shù)fun(s)來計算字符串s的排列序號。

通過觀察，可以歸納得出：

當(dāng)字符串長度n=1時，返回字符串排列序號為0。

當(dāng)字符串長度n>1時，字符串的排列序號由絕對序號加上相對序號求得。絕對序號，即以首字母開頭的最小字符串的排列序號；相對序號，是首字母相同時，長度為n-1的后續(xù)字符串的排列序號。

例如，長度為3的字符串“cba”中：

以‘c’開頭的最小字符串“cab”，序號為4，即2*2！。

去除首字母‘c’，剩余字符串“ba”，以‘b’開頭的最小字符串“ba”,序號為1，即1*1！。

去除首字母‘b’，剩余字符串“a”，以‘a(chǎn)’開頭的最小字符串“a”，序號為0。這些可以看作各長度字符串在排列中的絕對序號。

在首字母相同的字符串中，排列序號的變化，則依據(jù)長度為n-1的后續(xù)字符串的排列，可稱之為相對序號，用fun(s[1:])遞歸調(diào)用計算。

然后將絕對序號+相對序號，作為字符串的排列序號返回。

根據(jù)遞推歸納，計算如下：

計算“cba”的排列序號，fun(“cba”)=2*2！+fun(“ba”)

計算“ba”的排列序號，fun(“ba”)=1*1！+fun(“a”)

計算“a”的排列序號，fun(“a”)=0

當(dāng)字符串長度為1時，fun(“a”)=0,遞歸終止，然后逐層返回，依次得到fun(“ba”)=1,fun(“cba”)=5。

這里需要考慮首字母不同時，長度為n的最小字符串，其排列序號以(n-1)!幅度變化。正確計算出變化幅度,即(n-1)!的系數(shù)值，可以先將字符串s升序排列后的結(jié)果放在t中，然后查找出首字母s[0]在字符串t中索引值m，將m作為階乘的系數(shù)值。

4.2 遞歸函數(shù)偽代碼

fun(s)

輸入：字符串s

輸出：字符串s的排列序號

計算字符串s的長度n=len(s)

若n==1,則返回0

否則：

將s升序排列，存儲與t中

找出s[0]在t中的索引值，放在m中

返回m*fac(n-1)+fun(s[1:])

4.3 Python語言實現(xiàn)遞歸函數(shù)

def fun(s): #定義函數(shù)fun(s)，計算s字符串排列序號

n=len(s) #n計算字符串s的長度

if n==1: #若長度為1，返回排列序號0

return 0

t=sorted(s) #將字符串s升序排列到t中

m=t.index(s[0]) #計算字符串s的首字母在字符串t中的索引m

return m*fac(n-1)+fun(s[1:]) #遞歸調(diào)用fun()函數(shù)，計算出排列序號

5 總結(jié)及拓展

上述遞推和遞歸算法，均實現(xiàn)了計算字符串排列序號的功能。用Python程序?qū)崿F(xiàn)算法的過程中，很方便地調(diào)用了Python的字符串排序函數(shù)、查找指定字符索引值的函數(shù)，以及字符串切片的使用，體現(xiàn)了《計算機科學(xué)導(dǎo)論》課程重點培養(yǎng)計算思維的特點。在后續(xù)《C程序設(shè)計》及《數(shù)據(jù)結(jié)構(gòu)》課程學(xué)習(xí)中，要進一步著眼于降低算法的時間、空間復(fù)雜度，提高程序運行的效率，逐步優(yōu)化程序代碼。

針對上述例子，還可以進一步拓展思維。比如，給出排列序號61，要求計算出字符串的排列組合。

由于康托展開是一個全排列到一個自然數(shù)的雙射，因此是可逆的。由上述遞推算法的計算過程，可以很容易地將計算結(jié)果逆推回來，具體過程如下：

用61/4!=2余13，說明比首位小的字符有2個，所以首位為c。

用13/3!=2余1，說明除去(c)后，比第二位字符小的字符有2個，所以第二位為d。

用1/2!=0余1，說明除去(c,d)后，比第三位字符小的字符有0個，所以第三位為a。

用1/1!=1余0，說明除去(c,d,a)后，比第四位字符小的字符有1個，所以第四位為e。

說明除去(c,d,a,e)后，最后一位自然就是剩下的字符b。

通過以上分析，排列序號為61時，所求排列組合為cdaeb。

康托展開的逆運算，可以作為課后拓展實驗，布置給學(xué)生，讓學(xué)生深入理解該公式的原理并加以應(yīng)用。

本實踐案例具有先進性和互動性，學(xué)習(xí)結(jié)果具有探究性和個性化，體現(xiàn)了“金課”的創(chuàng)新性。實踐案例同時具備前沿性和時代性，具有一定難度，需要通過認真思考才能解決，體現(xiàn)了“金課”的挑戰(zhàn)度。同時，實踐案例分別使用遞歸、遞推思想，來解決現(xiàn)實問題，需要學(xué)生綜合運用問題分析、抽象建模的能力，并使用Raptor工具及Python語言實現(xiàn)該問題，培養(yǎng)學(xué)生解決復(fù)雜問題的綜合能力和高級思維，體現(xiàn)了“金課”的高階性。