计算思维与语言技能陈道蓄

1、计算思维与语言技能- 在程序设计课中如何权衡陈道蓄南京大学计算机科学与技术系2014年11月29日 郑州我们经常从教程序设计课的老师口中听到这样的话:“我这个课可不是只教一种语言的，我们教的是思想！”我们能说清楚吗？问题1：什么是思想？问题2：是什么思想？问题3：学生感悟到“思想”了吗？什么是计算思维？或者我们换一个问法：什么不是？计算机文化：为什么“遇到问题上百度”算不上是计算思维？计算机技术：为什么“了解操作系统的功能与结构”也不应该算是计算思维？怎样能让计算机帮我们解题？思维“传递”与“载体”“思想”只能传递, 不能直接“教”。有效的“传递”需要两个条件：合适的“载体”，适当的“例子”按

2、照上述想法来审视我们目前的程序设计课程载体相对复杂；例子相对简单基本想法与改革路线基本想法：显式区分“思维方法”与“编程技能”对不同的目标采用不同的教学方法方法设计基本思路：“思维”靠“悟”；“技能”靠“练”做法：引导学生去“悟”，不依靠特定语言；加大训练强度，不拘泥于语言成分。基本内容载体1，计算机为什么能解题？2，基本的算法结构3，基本的数据结构4，递归及其代价下面提供一些课堂实例片断计算机问题求解计算机问题求解问题1a:计算机究竟能干什么？问题1b:人究竟是如何解题的？问题1：为什么计算机能帮我们解题？Even More Amazing 0 1 0 1 10 1 0 0 10 1 1 0

3、 10 1 0 1 10 1 0 0 10 1 0 0 10 1 0 1 10 1 0 1 10 0 0 1 1FlippingZeroingTesting(if 1, flipping)问题2：我们可以让计算机“间接地”执行什么操作？你试试让计算机比较两个1-bit二进制数是否相等，只用前面提到的运算，如果需要，你可以使用辅助的bits.xyeqEquality test (x,y)zero eq;flip eq;/* equality ontest x flip eq;test y flip eq;/* equality on only turn twiceIf x=y eq=1Other

4、wise eq=0你能将这个操作扩展到, 比如, 32位内的整数吗?稍微增加一点操作计算两个1-bit二进制数的和xyz1z0tx+yadd (x,y)1. zero z0; 2. zero z1;3. equality test(x,y);4. test eq goto 75. flip z0;6. exit;7. zero t;8. flip t; 9. equality test(x, t);10. test eq flip z1; 如果只允许原来三个基本操作, 能完成这个任务吗?多层次抽象 用一位的加法“间接操作”可以实现普通加法操作；加法操作又可以作为一步操作用在更复杂的“间接操作”

5、中。实际上现在计算机内部电路能提供的操作远不只是那几个最简单的“直接”操作。问题1:你会吃蟹黄汤包吗?轻轻提, 慢慢移, 先开窗, 再喝汤。吃一只蟹黄汤包的“算法”顺序很重要：将包子从蒸笼中轻轻提起，and then将包子慢慢移动到面前的小碟子中，and then 在包子的正上方咬开一个小口，and then通过小口吸食包子里的汤(当心别烫着)，and then将包子送入口中。完成！问题2：你如何确保过程无误？假如我们认为在步骤4和5执行前要确保前面的结果是正确的，可以在相应的地方设个“监视哨” “guard”。问题3：但是我们并不只是吃一只，那怎么办呢？策略一：控制数量假如规定吃8只：开始设

6、一个计数器，并将其值设定为0。吃一只汤包计数器值加1，并判断其是否为8否是结束注意：这个过程的“结构”与计数器的初始值没有关系！策略二：吃饱为止是否已饱？是否 问题4：如果即使饱了，也希望至少品尝一只，该怎么办？上下颠倒如何确定循环过程是正确的？循环不变式这是一个逻辑表达式在循环体中它应该始终为“真”例如：用一个逐项累加的循环计算a*b, 循环不变式可以是：“存放中间结果的量的值=a*“循环变量的当前值”问题5：你能为上述两种吃蟹黄汤包的策略选定一个循环不变式吗？“冒泡”排序 循环的嵌套自下往上这一段干的是什么事情?问题6:是否可以将“冒泡”中的内层循环表示成一个procedure/subro

7、utine, 形式上成为单层循环？Max(E, low, high): 找出指定范围内的最大元素有人知道饱不饱，但有人不知道！开始要吃汤包的人不到5岁吗？是选用策略1选用策略2否结束问题7：如果要判断的不止是两种可能，那怎么办？分类定量控制开始要吃汤包的人不到5岁吗？否参数设为2是结束要吃汤包的人不到60岁吗？参数设为8是参数设为4否选用策略1(带参数)对包含“money”一词的句子计数搜索“money”一词搜索句子结尾标记问题8：前面的例子中“搜索”两次，尽管对象不同，动作确是一样的，有可能只描述一次吗？回想一下前面讨论“冒泡”排序时提出的问题？问题9：你能总结一下采用subroutine的

8、好处吗以“递归”的思维用于证明：数学归纳法教你一个小“魔术”：用一副扑克牌（不用“大小鬼”）事先按照红黑相间排列好将牌大致分为两份，确保下面可见的两张牌颜色不同请一位观者按常规方法洗牌1次（只是1次！）现在你可以不用看，保证“随便”抽出的两张牌一定是“一红一黑”。基于“递归”的推理：怎么能做到以上效果的？不过是数学归纳法而已！递归：一种思维方式从数学归纳法到利用递归的思想解题往前跨一小步 只是一小步而已数学归纳法奠基：直接确认假设：假设对较小的目标值（比如k），待证结论成立归纳：你的任务是从“对于k成立”推导出“对于k+1”仍然成立。用递归手段解题Base case：直接给出结果假设：假设对较

9、小的目标值（比如n-1或者n/2），“有人”帮你算出结果了归纳：你的任务是从“那个结果”推算出对于n的结果书写形式，其实不难！Hanoi Tower Easy or Difficult?还记得前页上那个“假设”吗？但是，“那个结果”在哪儿呢？这才是“真实”的执行过程！你看到的算法问题11：你能比较一下递归方法与数学归纳法吗？为什么计算机出现之前只流行数学归纳法，却没有广泛使用的“递归解题法”？递归和数学归纳法写一个程序真得很容易！证明它正确其实也不难！移64个盘子试试Hanoi Tower问题1:“变量”是不是“量”？x x + 1 该如何理解？什么是“结构”？问题2：你认为这段话中哪些词最关

10、键？你会想到什么儿时的游戏吗?数据和“位置”“全班同学排好队！”是什么意思？每人有了一个“位置”。其实这个“位置”是相对的。如果安排一种按照位置进行的“游戏”，“到了什么位置就知道该做什么”。如何以前面的观点来理解vector, 或称为list, 或称为one-dimensional array是一种数据结构？问题3：数组（向量）和循环是什么关系？“随意”和“受限”在书架的一层上取一本书在机场的饮水机旁取一个纸杯问题5：你能说出这两者的差别吗？更复杂的“位置”关系 “树”用树排序： 第1步：将数组表示为“二分搜索树”问题7:你能看出这个树是如何生成的吗?用树排序： 第2步：以“某种”方式遍历树

11、“ left-first traversal”“ second-visit output:问题8:为什么输出肯定是从小到大的?问题9：树和递归有什么关系？课堂示例片断到此为止编程技能 自学加训练Programming Tasks以周为单位安排，每周1-2个；在整个“计算机问题求解”课程中按照18*4周安排。.Documents教学珠峰计划班教学资料2012级第1学期计算机问题求解-课程指南-2012级第1学期.docx.Documents教学珠峰计划班教学资料2012级第2学期计算机问题求解-课程指南-2012级第2学期.docx第2周的编程任务题意概要:3，某公司员工提高工资7.6%，并从6个月前开始实施并补发。输入每人的原来的年收入，输出该补发的数额、新的年收入和月收入。允许用户计算任意多次。10，输入10个整数，输出所有大于0的数的和、所有不大于0的数的和以及全体数的和。每个数只输入一次，不能要求用户按照是否大于0等条件分类输入。 结束语取得的