入门任意一种编程语言所必须的几道习题

　　版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址

　　http://www.cnblogs.com/Colin-Cai/p/11073938.html 

　　作者：窗户

　　QQ/微信：6679072

　　E-mail：6679072@qq.com

　　每当学习一门计算机语言，我们也要做一些练习以便逐步熟悉。随着我们对这种编程语言本身支持的抽象手段理解的过程，以下这些问题，基本可以在几乎每门编程语言学习的过程中完成，这些语言可以包含但不限于C、C++、Shell、awk、Python、JavaScript、Java、Scala、Ruby、Lisp(Common Lisp、Scheme、Clojure)、Prolog、Haskell等。

汉诺塔(Hanoi Tower)

　　汉诺塔有三个柱子，最开始在第一根柱子上按从小到大的顺序放了n个盘，每次可以移动一个盘，并且只能小盘放在大盘的上面。问如何才能把这些盘从第一根柱子移到第二根柱子。

　　这个基本上是学习所有语言时候学习递归必然要接触的例子，实现了这个，也基本上对所学习语言的递归有了初步的了解。

　　我们可以把问题看成是Hanoi(1->2, 3, n),符号解读为把n个盘从1号柱移动到2号柱，剩余一个柱子是3号柱。

　　很容易把这个大问题拆成三个小问题：

Hanoi(1->2, 3, n) => Hanoi(1->3, 2, n-1), Hanoi(1->2, 3, 1), Hanoi(3->2,1, n-1)

　　也就是先把最上面n-1个盘从1号柱移动到3号柱，再把最大的盘从1号柱移动到2号柱，最后把最3号柱的n-1个盘移动到2号柱，

　　于是就达到了递归的效果。

因数分解/整系数多项式因式分解(factorization)

　　因数分解，是将输入的正整数分解为各个质数的乘积，比如：

　　$300 = 2^{2}\times{3}\times{5^{2}}$

　　因数分解普通情况下的算法并不复杂，只需要一个简单的初等数论证明即可。

　　而整系数多项式因式分解可能比上述还要复杂很多，比如：

　　$2x^{6}+7x^{5}+13x^{4}+15x^{3}+11x^{2}+5x+1 = (x^{2}+x+1)^{2}\times(2x^{2}+3x+1)$

　　这个无论是面向过程还是面向对象还是函数式编程等都值得好好做一做，如果可以，也可以尝试尝试Galois域的多项式环内的分解。

质数表(prime number list)

　　质数表也是一个合适的程序，可以使用好几种方法。

　　最简单的，我们可以依次从2开始判断每个数，对于每个数N判断$2\simN-1$是否是其约数，如果其中没有它的约数，则为质数。

　　当然，上述可以提高效率，我们知道对于任何一个正整数，如果是合数，则一定存在一个整数约数小于自身的平方根。于是我们的判断从$2\simN-1$缩到$2\sim\sqrt{N}$。

　　再往上进一步，我们寻找$1\simN$中的质数可以归结于寻找$1\sim\sqrt{N}$的质数。于是，我们这就可以引入一个递归。

　　另外，还有各类筛法不再细讲，可以自行google。

　　从而以上可以从各个角度来熟悉你所学习的编程语言。

排列/组合(permutation and combination)

　　组合数学的相关知识应该在中学就已经学过，我们通过加法原理和乘法原理(实际上乘法原理也是由加法原理推出)推出了排列/组合的世界。

　　这里，我们可以尝试着去写一个集合的所有排列/组合。

　　比如$\{1,2,3\}$的所有排列有$\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2,1\}$，所有两个元素的组合有${1,2},{1,3},{2,3}$。

　　有很多方法实现输出一个集合的所有排列组合：

　　首先，很多语言都有相关的库支持排列组合，比如Python的itertools库，很多时候正式写程序还是直接用库的。

　　比如$\{1,...n-1\}$的所有排列到$\{1,...n\}$的所有排列存在一个递归，组合也类似。

　　再者，我们可以用字典排列依次输出所需要的排列/组合，只是如何找到下一个稍微大一点的排列/组合需要一点点技巧。

　　然后，我们还可以用数与每个排列/组合一一对应，理论上有各种对应方法。

　　甚至，我们可以基于交换来依次输出所有的排列/组合，当然这里需要一些抽象代数知识。

　　总之，我们有各种实现排列/组合。

生命游戏(Conway's game of life)

　　生命游戏是1970年Conway的发明。

　　MxN的图里，所有的格子都带有一个状态，为生/死。

　　每一次整张图都有一个状态转换，每一个格子都要看周围8个格子生/死的个数。

　　下一代所有格子状态由以下规则确定：

　　1.如果周围有生命格子的数目小于2，则下一代这个格子状态为无生命(解释为太孤单)。

　　2.如果周围有生命格子的数目大于3，则下一代这个格子为无生命(解释为周围生命太多，资源消耗厉害)。

　　3.如果周围有生命格子的数目等于2，则下一代这个格子的状态继续保持当前的状态。

　　4.如果周围有生命格子的数目等于3，则下一代这个格子的状态为有生命。

24点(Count 24 points)

　　我们小的时候基本都玩过24点，就是4张牌使用加减乘除计算出24。

　　这个用程序实现是有点挑战的，我们考虑如何遍历所有的可能，然后依次算出来，看是否等于24，另外，我们可能还要考虑分数，比如下面经典题目5、5、5、1，计算方法是(5-1/5)*5。

　　再者，我们要按照平常的使用习惯，考虑把多余的括号去掉，比如((a*b)-c)/d其实应该是(a*b-c)/d。

　　另外，我们要考虑是否有结构等价，比如a*b+c*d和d*c+b*a，我们如何判断并只保留一种。

　　以上面的为例，可以有很多答案，比如2*8+3*3, 3*3+(8*2), 3*8*(3-2), (3-2)*(8*3), (3*8)/(3-2),(2+3/3)*8, (3/3+2)*8...但我们只考虑计算结构的唯一以及去掉多余括号，合理的只剩下四个答案：2*8+3*3, 3*8*(3-2), 3*8/(3-2), (2+3/3)*8。

　　当然，我们还要考虑更多的牌，更多的运算来计算任意数字。总之，24点这个问题或许不是那么容易，在某些语言下的实现尤其有技巧性。

自输出程序(Quine)

　　解释一下，所谓自输出程序(Quine)，就是程序的输出和程序的代码一模一样，直接用哲学家Quine命名。

　　这样的程序也需要写？怎么感觉是在学习写病毒呢？

　　病毒的确可能需要自输出这样的技术，但是技术这个东西本身就是双刃剑，手术刀是用来救人的，但它依然可以拿来当凶器。

　　每一种编程语言只要是图灵等价的(当然，其实这个条件很基本)，就可以通过不动点存在定理推出Quine是一定存在。记载中，上世纪60年代诞生了第一个Quine，用Atlas Autocode编写。

　　对于Scheme,可能的最短的Quine如下：

　　((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))

标准库的部分实现

　　思考所学语言的一些标准库的实现，也是提高的重要手段。比如C++的STL，我们在学习C++的时候可以去思考STL可能是如何实现的，这样很有助于对C++面向对象、泛型(通过模板实现)的理解。

　　并且，很多时候库的实现一样的语义有多种实现方式，我们可以考虑各种实现方式的不同。比如Scheme这样一种数据、过程完全混在一起的语言，很多基本函数有非常夸张的完全不同的实现。

　　如果Scheme、Common Lisp、Clojure这几种Lisp先后学习，也可以结合在一起，对比着学，想想另外一种是如何实现的。几种Lisp毕竟还是兄弟关系，有很大的相似，这种相似甚至可以扩展到同一编程范式的不同语言之间，它们依然有很多可以相通的地方，这些都可以对比关联。比如两种从设计一开始就冲着多范式支持而去的JavaScript、Python，就可以和很多其他语言产生共鸣，我们在实现某些库的时候也会去想想别的语言是如何实现的。

结束语

　　计算机语言的学习总是循序渐进的，总之本着多思考、多对比，永远不要让新学到的知识形成知识孤岛，而要让所有的知识彼此紧密联系在一起，这样才会不断进步，并更有创造的灵感。