[关闭]
@bintou 2019-10-08T14:17:33.000000Z 字数 2051 阅读 907

CSI讲义13-- 计算思维训练简要指南

CSI


计算思维不是自然形成,而是特别训练的产物。以下简要给出一些建议,围绕这些建议可以进行相关训练。新生只需要关注第一和第二阶段,所以,第三阶段我还没写。或者说,因为我还没写,所以大家可以先关注第一、第二阶段。

第一阶段: 面向问题

计算机专业新生的第一阶段任务就是要强调“面向问题”的思维。把“发现问题、分析问题、解决问题”优先放在你任何思考当中。

1. 面向数据的思维

考虑一个独立的“问题”,首先问两个问题:

也就是说,在提出问题的初期,把关注点放在数据(Data)上,关注于问题的I/O(输入/输出)。进一步,需要关注数据的表达:长度、类型等。

例子. 给定一个整数n,求n的阶乘。输入是整数n,输出也是一个整数。进一步问,这个整数有多大?这个函数大概长这个模样。

  1. \* Input: integer n
  2. * Output: integer res, where res = n*(n-1)...2*1
  3. *\
  4. int factorial(int n){
  5. ......
  6. return res;
  7. }

请注意,你可以不知道这个问题怎么解决,但千万不可不知道你的问题是什么!不知道问题是什么,下一步所谓“解决问题”就免谈。而清楚知道自己的问题,将有助于问题的解决。

以下是常见错误,请大家体会,并尽量避免!为什么我说它错?请问,你的输出是什么?输出就是打印出结果啊!真的是这样吗?

  1. void factorial(int n){
  2. ......
  3. printf("哈哈哈,你的答案是:%d.\n", res);
  4. }

另外一个错误,这是一个求a的x次方的程序。源自真实的作业提交。

  1. int pow(int a, int x, int n) {
  2. if(n == 0||a ==0 || x <= 0) {
  3. printf("输入数据错误:/n");
  4. exit(1);
  5. //以下省略。。。
  6. }

请回答我,为什么我认为这是错误?

习题. 给出以下问题的输入输出分析,并写出函数的雏形。
1. 判断一个整数n是否素数;
2. 求两个整数的最大公因子;

在初学的早期就必须关注这些问题,准确并自觉地应用函数这个概念。千万别到了大二还不能准确写一个函数出来!!!

2. 结构化方法

所谓结构化的方法,即面向特定问题,把该问题“自顶向下”地分解为更小的问题,通过解决小问题来解决大问题。

例子. 编程验证哥德巴赫猜想,即任意大于2的偶数都是两个素数的和。
子问题:整数加法、判断素数、判断两个整数相等......

3. 与程序设计语言结合的训练

自觉在编程程序的时候体现以上两种思维。当你接到一个编程任务,首先问输入/输出,其次考虑数据类型,再思考解决这个问题需要分解为解决什么子问题。即,所谓的“结构化编程”。

现在的教学强调“面向对象编程”(OOP),请注意,OOP并不会对冲结构化,它们各司其职,而结构化方法在专业学习初期必须更加强调。

4. 问题解决后需要问的三个问题

“面向问题”的思维中,解决问题并非最后一步,因为,“解决完”一个问题我们还需要针对解决问题的方法问三个问题(问题系列):

例子. 插入排序的效率?快速排序的效率?如何证明?Theta(n log n)是否最优效率?

例子. 寻找峰值. 这篇博客具体展示了以上思想的每一个步骤,可惜阅读者甚少。

第二阶段:面向方法

计算思维当然不是一成不变的,然而经过一个世纪的发展,到目前已经形成一系列得到广泛认同的方法学。这些方法学当中,某些针对程序(自动化问题求解)的“数据结构”,某些则是特定的思维模式。

数据结构

数据结构分为两类:初级与高级。不要被“高级”、“初级“这两个看上去有高低评价的字眼迷惑。它们不可以相互替代,各司其职,分别有其特殊的用途。

初级数据结构

高级数据结构

特定的方法

具体内容参考《算法导论》,请尽快进入“算法”的学习。

1. 暴力求解

计算机的优势是高速,这使得暴力求解往往成为可行的方法。我想提醒的是,无论“暴力求解”这个名字多粗暴,看上去有多“幼稚”,在面向问题的第一时刻请首先想起“暴力”,任何时候!方法就是方法,也许暴力法无法解决很多问题,但它永远是思维的第一步。许多低年级的同学没有经过暴力法的洗礼,盲目追求所谓的“高级”方法,往往得不偿失,失去了训练自己的最好时机。

另外,暴力法也往往是给其他高级方法带来启发。只有明白暴力法无效的本质,才有可能去发现更高效的方法。

例子. 给定一个整数n,判断其是否素数。暴力求解应该如何做?问题:为什么我们需要比暴力法更高效的方法?

例子. 求两个整数的最大公因子。 给出算法描述,如何证明其正确性?其效率是什么?是否最优?如何改进?

2. 分治法

继续强推这关于分治法的小博客,以实例带动思维。

3. 贪心法

4. 动态规划

5. 线性规划

第三阶段 面向代数的特定结构

向量空间

代数结构

代数几何

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注