袁紅娟，朱 曄，酈 麗

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)6：遞歸和迭代，掌握遞歸的方法和思維，掌握迭代的方法和思維。

實(shí)驗(yàn)7：查找，掌握順序查找、二分查找、分塊查找等的方法和使用。

實(shí)驗(yàn)8：排序，掌握插入排序、冒泡排序、選擇排序等的方法和使用。

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

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

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

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

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

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

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個(gè)兩兩不同的小寫(xiě)字母，給出它們組成的串，求出該串在所有排列中的序號(hào)。

樣例輸入：bdca

樣例輸出：11

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

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

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

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

由c1到cn這n個(gè)字符組成的全排列，共n!個(gè)，按每個(gè)全排列組成的字符從小到大進(jìn)行排列，并對(duì)每個(gè)序列進(jìn)行編號(hào)，記為X(從0開(kāi)始)。

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

對(duì)于ai的理解：

對(duì)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

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

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

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

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

3.1 問(wèn)題分析

若字母長(zhǎng)度為3，排列及序號(hào)如下：

abc 0

bcb 1

bac 2

bca 3

cab 4

cba 5

字符串s，用n=len(s)計(jì)算字符串s的長(zhǎng)度。定義計(jì)算字符串s序號(hào)的遞推函數(shù)func(s)。

若s=“cba”。

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

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

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

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

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

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

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

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

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

func(s)

輸入：字符串s

輸出：字符串s的排列序號(hào)

計(jì)算字符串s的長(zhǎng)度n=len(s)

字符序號(hào)初始值sum=0

遍歷字符串s的每個(gè)索引i：

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

對(duì)t升序排列

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

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

返回排列序號(hào)sum

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

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

n=len(s) #n計(jì)算字符串s的長(zhǎng)度

sum=0 #sum計(jì)算字符串的排列序號(hào)

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

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

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

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

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

return sum #返回字符排列序號(hào)

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

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

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

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

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

def fac(n):

if n==1 or n==0:

return 1

else:

return n*fac(n-1)

4.1 問(wèn)題分析

若字母長(zhǎng)度為3，排列及序號(hào)如下：

abc 0

bcb 1

bac 2

bca 3

cab 4

cba 5

若字母長(zhǎng)度為2，排列及序號(hào)如下：

ab 0

ba 1

若字母長(zhǎng)度為1，排列及序號(hào)如下：

a 0

字符串s，用n=len(s)計(jì)算字符串s的長(zhǎng)度。用遞歸函數(shù)fun(s)來(lái)計(jì)算字符串s的排列序號(hào)。

通過(guò)觀察，可以歸納得出：

當(dāng)字符串長(zhǎng)度n=1時(shí)，返回字符串排列序號(hào)為0。

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

例如，長(zhǎng)度為3的字符串“cba”中：

以‘c’開(kāi)頭的最小字符串“cab”，序號(hào)為4，即2*2！。

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

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

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

然后將絕對(duì)序號(hào)+相對(duì)序號(hào)，作為字符串的排列序號(hào)返回。

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

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

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

計(jì)算“a”的排列序號(hào)，fun(“a”)=0

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

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

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

fun(s)

輸入：字符串s

輸出：字符串s的排列序號(hào)

計(jì)算字符串s的長(zhǎng)度n=len(s)

若n==1,則返回0

否則：

將s升序排列，存儲(chǔ)與t中

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

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

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

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

n=len(s) #n計(jì)算字符串s的長(zhǎng)度

if n==1: #若長(zhǎng)度為1，返回排列序號(hào)0

return 0

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

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

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

5 總結(jié)及拓展

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

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

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

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

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

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

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

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

通過(guò)以上分析，排列序號(hào)為61時(shí)，所求排列組合為cdaeb。

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

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