@bintou
2019-10-08T22:17:33.000000Z
字数 2051
阅读 2024
CSI
计算思维不是自然形成，而是特别训练的产物。以下简要给出一些建议，围绕这些建议可以进行相关训练。新生只需要关注第一和第二阶段，所以，第三阶段我还没写。或者说，因为我还没写，所以大家可以先关注第一、第二阶段。
计算机专业新生的第一阶段任务就是要强调“面向问题”的思维。把“发现问题、分析问题、解决问题”优先放在你任何思考当中。
考虑一个独立的“问题”，首先问两个问题：
也就是说，在提出问题的初期，把关注点放在数据（Data）上，关注于问题的I/O（输入/输出）。进一步，需要关注数据的表达：长度、类型等。
例子. 给定一个整数n，求n的阶乘。输入是整数n，输出也是一个整数。进一步问，这个整数有多大？这个函数大概长这个模样。
\* Input: integer n* Output: integer res, where res = n*(n-1)...2*1*\int factorial(int n){......return res;}
请注意，你可以不知道这个问题怎么解决，但千万不可不知道你的问题是什么！不知道问题是什么，下一步所谓“解决问题”就免谈。而清楚知道自己的问题，将有助于问题的解决。
以下是常见错误，请大家体会，并尽量避免！为什么我说它错？请问，你的输出是什么？输出就是打印出结果啊！真的是这样吗？
void factorial(int n){......printf("哈哈哈，你的答案是：%d.\n", res);}
另外一个错误，这是一个求a的x次方的程序。源自真实的作业提交。
int pow(int a, int x, int n) {if(n == 0||a ==0 || x <= 0) {printf("输入数据错误：/n");exit(1);//以下省略。。。}
请回答我，为什么我认为这是错误？
习题. 给出以下问题的输入输出分析，并写出函数的雏形。
1. 判断一个整数n是否素数；
2. 求两个整数的最大公因子；
在初学的早期就必须关注这些问题，准确并自觉地应用函数这个概念。千万别到了大二还不能准确写一个函数出来！！！
所谓结构化的方法，即面向特定问题，把该问题“自顶向下”地分解为更小的问题，通过解决小问题来解决大问题。
例子. 编程验证哥德巴赫猜想，即任意大于2的偶数都是两个素数的和。
子问题：整数加法、判断素数、判断两个整数相等......
自觉在编程程序的时候体现以上两种思维。当你接到一个编程任务，首先问输入/输出，其次考虑数据类型，再思考解决这个问题需要分解为解决什么子问题。即，所谓的“结构化编程”。
现在的教学强调“面向对象编程”（OOP），请注意，OOP并不会对冲结构化，它们各司其职，而结构化方法在专业学习初期必须更加强调。
“面向问题”的思维中，解决问题并非最后一步，因为，“解决完”一个问题我们还需要针对解决问题的方法问三个问题（问题系列）：
正确性. 该方法是否正确？为什么？如何证明？
效率. 该方法解决问题的效率如何评估？
优化. 该方法是否最优方案？如果不是，怎么样改进？如果是，如何证明？
例子. 插入排序的效率？快速排序的效率？如何证明？Theta(n log n)是否最优效率？
例子. 寻找峰值. 这篇博客具体展示了以上思想的每一个步骤，可惜阅读者甚少。
计算思维当然不是一成不变的，然而经过一个世纪的发展，到目前已经形成一系列得到广泛认同的方法学。这些方法学当中，某些针对程序（自动化问题求解）的“数据结构”，某些则是特定的思维模式。
数据结构分为两类：初级与高级。不要被“高级”、“初级“这两个看上去有高低评价的字眼迷惑。它们不可以相互替代，各司其职，分别有其特殊的用途。
具体内容参考《算法导论》，请尽快进入“算法”的学习。
计算机的优势是高速，这使得暴力求解往往成为可行的方法。我想提醒的是，无论“暴力求解”这个名字多粗暴，看上去有多“幼稚”，在面向问题的第一时刻请首先想起“暴力”，任何时候！方法就是方法，也许暴力法无法解决很多问题，但它永远是思维的第一步。许多低年级的同学没有经过暴力法的洗礼，盲目追求所谓的“高级”方法，往往得不偿失，失去了训练自己的最好时机。
另外，暴力法也往往是给其他高级方法带来启发。只有明白暴力法无效的本质，才有可能去发现更高效的方法。
例子. 给定一个整数n，判断其是否素数。暴力求解应该如何做？问题：为什么我们需要比暴力法更高效的方法？
例子. 求两个整数的最大公因子。 给出算法描述，如何证明其正确性？其效率是什么？是否最优？如何改进？
二分搜索
归并排序
快速排序
继续强推这关于分治法的小博客，以实例带动思维。