郭元辉 西华师范大学实验中心
摘要：随着计算机技术及应用的普及与提高，计算思维作为新一轮大学计算机基础教育的前沿课题和内容在理论与实践中讨论、尝试和渐进发展，《计算思维导论》单独开设或融合《大学计算机基础》已逐步在一些学校作为选修课、必修课展开。本文就实际教学中的算法选择与语言表现进行初步探讨并给出基本框架。
教育期刊网 http://www.jyqkw.com
关键词 ：计算思维 算法 表现
一、引言
美国卡内基?梅隆大学计算机系主任周以真（Jeannette M. Wing）教授指出：计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。计算思维补充并结合了数学思维与工程思维，在理论上成为一个哲学命题，在实践中回归并指导计算机基础教学。
教育部高教司2012年下发《关于公布大学计算机课程改革项目名单的通知》，确定了22个研究项目，标志着“以计算思维能力培养为切入点的大学计算机课程改革”工作进入一个新的阶段。国内的专家、学者就非计算机专业大学计算机课程教学引入计算思维在理论与实践上进行了深入的研究。许多大学也开始组织研讨、学习，修订教材及教学计划并投入教学运行。
现行大学计算机课程对于非计算机专业而言，一是《大学计算机基础》，普遍开设于文科、师范、财经、医学及艺体；二是《VB/VC程序设计》，普遍开设于理工科。由于中小学教育中《信息技术》的开设，MSOFFICE文字、表格、演示文档及多媒体技术内容的下移，目前计算思维的引入主要体现在用《VB/VC程序设计》的基础算法部分替代《大学计算机基础》的MS-OFFICE章节，陆续有多本教材出版。在实际教学应用中或单独开设《计算思维导论》或合并、融入在《大学计算机基础》课程中。其影响正逐步扩大。
这里就实际教学中的算法选择及语言表现进行初步探讨。
二、问题与解答
将计算思维引入《大学计算机基础》，其核心就是引入算法，培养其使学生能终生受益的计算思维能力。搜狗百科定义：“算法，是求解问题类的、机械的、统一的方法，常用于计算、数据处理和自动推理。可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。”
从计算机专业书籍上可以列出一系列算法目录：基本算法、迭代、递归、排序、查找、穷举法、贪心法、分治法、动态规划、回溯法、P、NP完全性等。
在新版的计算思维导论类教材中也都以不同的方式尽可能多地引入、讲解上述的一些算法，甚至包括网页排序、遗传算法、有限元等具有一定难度、需要较多背景学科知识的新颖算法。由于部分使用了伪代码，对没有计算机语言基础的大一学生，很难具备实际操作、验算领会的意义。
那么如何尝试改进呢？
问题一：π 的计算
π 的计算是一个值得探讨的问题，数学史上关于它可以写厚厚的几本书，第一台计算机ENIAC计算到2037位，现在的计算结果已经上千亿位。这里给出3个算法。
算法1：直接法（精确解）
1914年，印度数学家Srinivasa Ramanujan(1887-1920)给出15位精度的公式：
表现：1、VB、VC程序设计语言（本文选VB）；
2、前导：数据类型、变量、常用函数；
3、print命令求解。此一步，解决计算器的所有计算。算法2：数值算法（近似解）
的级数计算公式有多钟，1637年Leibniz给出的公式:
表现：1、概念：近似解的截断误差[13]。
2、前导：条件分支、循环概念及语句。
3、难点：有限循环、无限循环（死循环）、空循环的处理。已知循环次数与未知循环次数（条件判断）的程序实例。当级数项符号一正一负交替出现时，用-1乘之的技巧。
4、蕴含迭代与递归的形式。
算法3：Monte Carlo method（概率法）、1777年Buffon用投针实验计算了π ，这是一种概率的方法。假设在单位正方形区域画上1/4的单位圆，往正方形里投针m（足够多）次，统计掉在圆内的数目n，那么根据概率的定义，针掉在圆内的概率p = n /m，也等于面积之比：
由此：
π ≈ 4*n / m
表现：1、概念：随机数的产生及应用。
2、利用V B的随机函数编程，圆内的关系为点（x,y）满足：x2 + y2 <=1。
3、蕴含数学问题的求解，不仅仅依赖计算，也依赖于样本的分布。有的问题，例如成绩排序，本生就是处理和实现分布。
问题二：迭代与递归
迭代与递归本质上是与一个无穷序列0 1 2 1 , , , , , , n n s s s s s+ ? ?相关的两种计算方式，同一个关系： 1 ( ) n n s F s + = ，若取n=0,1,2,…则为迭代；取n=n,n-1,…,0则为递归。使用递归，由于函数的自身调用，在未得到初值时会占用内存空间。原则上两种方法可以转换，但对具体问题，有的迭代适合，有的递归适合。
算法1：N!=N*(N-1)*…2*1 分别用迭代与递归求10！。
表现：1、与S=1+2+…+n比较，迭代中初值的不同。
2、概念：递归中内存的占用。
3、N!的值：当N较大时是一个很大的数。由此加深对整形、长整型、双精度等数据类型的认识及处理。
算法2：已知： f (x) = 5.23? x2 , a=2,b=3,f(a)*f(b)<0,用二分法求5.23的平方根，精确到10?6。（迭代进阶）
表现：（程序化的二分法思想）
1、c=(a+b)/2;
2、计算f(c),如果|f(c)|< 10?6那么 结束 否则 下一步；
3、如果 f(a)*f(c)<0 那么 b=c 否则 a=c；
4、转1 。
5、拓展：进一步牛顿迭代法进行计算。将迭代次数两相比较，可以看到牛顿迭代法收敛速度快很多（平方收敛）。
算法3：用欧几里得辗转相除法求（12,26）的最大公因子。(递归进阶)表现：1、设函数为gcd(m,n)，内容：
2、计算m/n=q+r/n，q为商，r为余；（蕴含大量应用实例）
3、如果 r=0 那么 返回 n，结束。否则 下一步；
4、m=n;n=r;递归调用 gcd(m,n)。
5、拓展：可以引申举例著名的汉罗塔递归，对汉罗塔问题，递归是最好的方法。
问题三：整除与求模
在《程序设计》的教科书里基本都会见到求水仙花数、数的拆分、求100以内的素数、十进制数转换成二进制数等，它们都属于整除与求模（余数）的问题，多用穷举法。
算法1：判断一个三位数X是否水仙花数？
表现：1、所谓水仙花数是指一个三位数等于其每位数的立方之和。例：371 = 33 + 73 +13；
2、设x为ab c三位，则：a=x\10 0,b =(x-10 0 *a),a=b mo d10,b=b\10;
3、判断 是否成立。
4 、拓展：x 是否素数的判断归结为循环处理x m o dp,(p=2,3,…,x-1),只要有一个为0便确定不是素数；x 的二进制转换则是不断计算整除与求模：x=x\2, i q =x mod 2；i=0,1,2…n,至x=0结束。将n n 1... 1 0 q q q q ? 记作二进制数。
问题四：排序
排序是计算机处理应用中最常见的工作之一，各国GDP排序，学生成绩排序，字典索引排序等等，对已有数据排列位置根据某一关键字之值重新调整，其方法多样，效率不一，在算法研究中有重要地位。
算法1：数组abc={23,41,6,7,12,9,8,30,34,12}元素排降序。
表现：1、概念：数组的定义与使用；
2、比较法：
3、拓展：冒泡法：相邻两个元素比较，与比较法类似，但一轮比较完，如果没有出现一次数据交换，便可结束；插入法：假设前N个数据已经排好序，第n+1个数据逐一和前面的数据比较，放在相应位置，保持顺序一致。此算法涉及若干数据的移位问题。分治法：任选一个数，比之小的数为一组，比之大的数为一组，重复分，至不可分。
三、总结
本文列出四个问题作为引入计算思维的算法基础，在实际教学中需要20-30学时的保证。讲程序而不是完全的程序设计课；讲算法又不能仅仅用中文与伪代码，必须要能够上机验算。这本身也是一个课程改革中的问题。
进一步的《大学计算机基础》教学改革仍在进行中。本文得到西华师范大学2014教改项目“面向新课改信息技术的师范生技能培养”资助，在此感谢。