袁紅娟,朱 曄,酈 麗
(泰州學(xué)院 計算機科學(xué)與技術(shù)學(xué)院,江蘇 泰州 225300)
計算思維是運用計算機科學(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é)生獲得獨立解決問題的綜合能力。
為培養(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ù)雜問題的綜合能力和高級思維。
為提高教學(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é)過程如下:
如果用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)。
該實踐教學(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é)要求:分別用遞推和遞歸方法解決該問題。
遞推算法以初始值為基礎(chǔ),用相同的運算規(guī)律,逐次重復(fù)運算,直至運算結(jié)束。從“起點”重復(fù)相同的方法直至到達一定“邊界”,用循環(huán)可以實現(xiàn)[2]。其思想是把一個復(fù)雜龐大的計算過程轉(zhuǎn)化為簡單過程的多次重復(fù)。
若字母長度為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ù)值。
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
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 #返回字符排列序號
在數(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)
若字母長度為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ù)值。
fun(s)
輸入:字符串s
輸出:字符串s的排列序號
計算字符串s的長度n=len(s)
若n==1,則返回0
否則:
將s升序排列,存儲與t中
找出s[0]在t中的索引值,放在m中
返回m*fac(n-1)+fun(s[1:])
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ù),計算出排列序號
上述遞推和遞歸算法,均實現(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)了“金課”的高階性。