以培养计算思维为导向的《计算机科学导论》实践教学案例设计

袁红娟，朱 晔，郦 丽

(泰州学院 计算机科学与技术学院，江苏 泰州 225300)

0 引言

计算思维是运用计算机科学的基础概念进行问题求解、系统设计，以及人类行为理解等涵盖计算机科学之广度的一系列思维活动[1]。计算思维概念由美国卡内基·卡梅隆大学计算机科学系主任周以真教授于2006年首次提出。

“通过中美高水平大学课堂教学的对比，可以看到一流大学教育的目的：不只是学知识、学能力，而且是学会一种思维方式，培养学生批判性独立思考的能力，并为终身学习打下基础”。《计算机科学导论》课程是计算机专业本科生的入门课程，肩负着引导大一新生正确认知和学习计算机科学知识的重任。除了理论知识的学习，在实践教学设计中，重点培养学生独立的计算思维。

2018年，在广州大学举办的“第十一届中国大学教学论坛”上，吴岩司长提出：“课程是教育最微观问题，解决的是教育最根本问题。各高校要全面梳理各门课程的教学内容，淘汰‘水课’，打造‘金课’，合理提升学业挑战度，拓展课程深度，切实提高课程教学质量”。上述提议，强化了人才培养的核心地位，一流本科教育的基础地位，要求建设中国大学“金课”。

泰州学院计算机科学与技术学院，以《计算机科学导论》作为打造“金课”课程教学改革的先锋，相继申报了校级重点教改课题、校级精品在线开放课程建设项目。课程实践教学设计中，摒弃原先办公软件的学习，引入Raptor流程图软件进行算法设计与验证，提高学生分析问题、抽象建模、解决问题的能力。《计算机科学导论》在线课程进行课程教学视频、题库资源建设的同时，与同期教学的《Python程序设计》课程联动，进行互补教学。通过《计算机科学导论》课程学习并深入理解算法思想，以Raptor工具实现算法抽象、建模、转换，最后用Python语言将算法设计并实现，将学生的计算思维培养贯穿于整个教学过程，让学生获得独立解决问题的综合能力。

1 实践教学内容设计

为培养学生的计算思维，体现“金课”高阶性、创新性、挑战度等特点，《计算机科学导论》在实践教学中合理提升实验挑战度，拓展知识的深度，提高教学质量。实践教学一共设置8个实验，内容如下：

实验1：顺序结构程序设计，掌握Raptor算术、逻辑、关系运算符的使用，掌握常量、变量及常用函数的使用。

实验2：选择结构程序设计，掌握决策表达式的使用，掌握单分支、双分支、多分支的使用。

实验3：循环结构程序设计，掌握循环控制的基本结构，掌握决策语句的3种测试方式，掌握循环结构的嵌套。

实验4：数组，掌握一维数组、二维数组、字符数组的创建和使用。

实验5：子程序和子图，掌握子程序的创建、参数的设置、传递；掌握子图的创建，理解变量的生命周期。

实验6：递归和迭代，掌握递归的方法和思维，掌握迭代的方法和思维。

实验7：查找，掌握顺序查找、二分查找、分块查找等的方法和使用。

实验8：排序，掌握插入排序、冒泡排序、选择排序等的方法和使用。

实验1-4是基本的设计性实验，让学生使用Raptor工具对问题进行抽象和建模，用流程图解决简单问题；实验5-8是综合性实验，由基础到应用，层层递进，将知识、能力、素质有机融合，培养学生解决复杂问题的综合能力和高级思维。

2 实践教学方式创新

为提高教学效果，泰州学院大力推动在线开放课程的建设，打造线上金课、线下金课、线上线下混合式金课等。2018年，《计算机科学导论》被立项为校级在线开放课程。课程教学中，利用现有的在线教学资源，实现线上、线下混合式教学改革。在实践教学设计中，体现高阶性、创新性、挑战度的特点，合理提升实验难度，并及时反馈、总结实验效果，提高实践教学含金量。

例如：实验7递归，首先介绍常规的递归思想，列举典型案例——阶乘、汉诺塔游戏和斐波那契数列，然后结合“蓝桥杯”程序设计大赛，布置出具有挑战性的拓展实验作业，全面锻炼学生思维能力。具体的教学过程如下：

2.1 实践教学案例引入

如果用a b c d这4个字母组成一个串，有4!=24种，如果把它们排个序，每个串都对应一个序号：

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

…

现在有不多于10个两两不同的小写字母，给出它们组成的串，求出该串在所有排列中的序号。

样例输入：bdca

样例输出：11

要求学生基于递归或递推思想，用Raptor工具抽象建模，以流程图方式解决上述问题，并用Python语言编程实现。

2.2 实践教学案例原理

该实践教学案例反映的是康托展开式，该公式实现了由字符c1到cn组成的全排列序列到其编号之间的一种映射，常用于构建哈希表时的空间压缩[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对应编号0，abdc对应编号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

康托公式中的每一项依次对应全排列序列中的每个元素，并按上述规则映射,则X=2*3!+1*2!+0*1!+0*0!=14，即cbad对应的编号为14。

教学要求：分别用递推和递归方法解决该问题。

3 递推算法实现

递推算法以初始值为基础，用相同的运算规律，逐次重复运算，直至运算结束。从“起点”重复相同的方法直至到达一定“边界”，用循环可以实现[2]。其思想是把一个复杂庞大的计算过程转化为简单过程的多次重复。

3.1 问题分析

若字母长度为3，排列及序号如下：

abc 0

bcb 1

bac 2

bca 3

cab 4

cba 5

字符串s，用n=len(s)计算字符串s的长度。定义计算字符串s序号的递推函数func(s)。

若s=“cba”。

用i逐个遍历s字符串的索引，循环：

当i=0时，首字母c在字符串“cba”中排列为2，序号变化幅度为：2！，因此得到首字母c在字符串“cba”中的排列序号：2*2！，即4。

当i=1时，字母b在剩余字符串“ba”中的排列为1，序号变化幅度为：1！，因此得到字母b在字符串“ba”中的排列序号为：1*1！，即1。

当i=2时，字母a在剩余字符串“a”中的排列为0，序号变化幅度为：0！，因此得到字母a在字符串“a”中的排列序号为0*0！，即0。

直至i>=len(s)结束。

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

算法中要多次调用阶乘函数，比如计算n!,用fac(n)表示，下文均如此调用。

正确计算出当前字母在剩余字符串中排列位置，即阶乘的系数值，首先将字符串s，自索引i开始截取剩余的字符串，放置到t中；然后对字符串t升序排列；最后查找出字母s[i]在字符串t中索引值m，m即为阶乘的系数值。

3.2 递推函数伪代码

func(s)

输入：字符串s

输出：字符串s的排列序号

计算字符串s的长度n=len(s)

字符序号初始值sum=0

遍历字符串s的每个索引i：

用t截取字符串s从索引i开始的剩余字符串

对t升序排列

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

计算当前字符s[i]在排列中的序号sum=sum+m*fac(n-(i+1))

返回排列序号sum

3.3 python语言实现递推函数

def func(s): #定义函数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)) #计算当前s[0:i+1]在字符排列中的序号

return sum #返回字符排列序号

4 递归算法实现

在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身的方法[3]。递归是一种奇妙的思维方式，主要分为两个阶段：

(1)递推归纳。把问题转化为比原问题规模小的同类问题。如计算n!，可以递推归纳到计算n*(n-1)!;计算(n-1)!，可以递推归纳到计算(n-1)*(n-1)!……。

(2)递归终止。当问题小到一定规模时，结束递归，逐层返回。如当递推归纳到计算1!，得到1!=1或0!=1，则开始逐层返回。

因此，计算n!的函数，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的长度。用递归函数fun(s)来计算字符串s的排列序号。

通过观察，可以归纳得出：

当字符串长度n=1时，返回字符串排列序号为0。

当字符串长度n>1时，字符串的排列序号由绝对序号加上相对序号求得。绝对序号，即以首字母开头的最小字符串的排列序号；相对序号，是首字母相同时，长度为n-1的后续字符串的排列序号。

例如，长度为3的字符串“cba”中：

以‘c’开头的最小字符串“cab”，序号为4，即2*2！。

去除首字母‘c’，剩余字符串“ba”，以‘b’开头的最小字符串“ba”,序号为1，即1*1！。

去除首字母‘b’，剩余字符串“a”，以‘a’开头的最小字符串“a”，序号为0。这些可以看作各长度字符串在排列中的绝对序号。

在首字母相同的字符串中，排列序号的变化，则依据长度为n-1的后续字符串的排列，可称之为相对序号，用fun(s[1:])递归调用计算。

然后将绝对序号+相对序号，作为字符串的排列序号返回。

根据递推归纳，计算如下：

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

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

计算“a”的排列序号，fun(“a”)=0

当字符串长度为1时，fun(“a”)=0,递归终止，然后逐层返回，依次得到fun(“ba”)=1,fun(“cba”)=5。

这里需要考虑首字母不同时，长度为n的最小字符串，其排列序号以(n-1)!幅度变化。正确计算出变化幅度,即(n-1)!的系数值，可以先将字符串s升序排列后的结果放在t中，然后查找出首字母s[0]在字符串t中索引值m，将m作为阶乘的系数值。

4.2 递归函数伪代码

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语言实现递归函数

def fun(s): #定义函数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:]) #递归调用fun()函数，计算出排列序号

5 总结及拓展

上述递推和递归算法，均实现了计算字符串排列序号的功能。用Python程序实现算法的过程中，很方便地调用了Python的字符串排序函数、查找指定字符索引值的函数，以及字符串切片的使用，体现了《计算机科学导论》课程重点培养计算思维的特点。在后续《C程序设计》及《数据结构》课程学习中，要进一步着眼于降低算法的时间、空间复杂度，提高程序运行的效率，逐步优化程序代码。

针对上述例子，还可以进一步拓展思维。比如，给出排列序号61，要求计算出字符串的排列组合。

由于康托展开是一个全排列到一个自然数的双射，因此是可逆的。由上述递推算法的计算过程，可以很容易地将计算结果逆推回来，具体过程如下：

用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。

康托展开的逆运算，可以作为课后拓展实验，布置给学生，让学生深入理解该公式的原理并加以应用。

本实践案例具有先进性和互动性，学习结果具有探究性和个性化，体现了“金课”的创新性。实践案例同时具备前沿性和时代性，具有一定难度，需要通过认真思考才能解决，体现了“金课”的挑战度。同时，实践案例分别使用递归、递推思想，来解决现实问题，需要学生综合运用问题分析、抽象建模的能力，并使用Raptor工具及Python语言实现该问题，培养学生解决复杂问题的综合能力和高级思维，体现了“金课”的高阶性。