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

淡淡的烟草味﹌ 2024-04-18 20:37 41阅读 0赞

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

**汉诺塔(Hanoi Tower)**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

汉诺塔有三个柱子，最开始在第一根柱子上按从小到大的顺序放了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号柱，

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

**质数表(prime number list)**

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

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

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

再往上进一步，我们寻找1 N1 N中的质数可以归结于寻找1\\widetilde\\sqrt(N)的质数。于是，我们这就可以引入一个递归。

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

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

**排列/组合(permutation and combination)**

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

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

比如1,2,31,2,3的所有排列有1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,11,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1，所有两个元素的组合有1,2,1,3,2,31,2,1,3,2,3。

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

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

比如1,...n−11,...n−1的所有排列到1,...n1,...n的所有排列存在一个递归，组合也类似。

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

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

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

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

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

![640?wx\_fmt=gif][640_wx_fmt_gif]

生命游戏是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。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

以上面的为例，可以有很多答案，比如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，就可以和很多其他语言产生共鸣，我们在实现某些库的时候也会去想想别的语言是如何实现的。

**结束语**

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

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

不得不看

1.[SpringCloud系列博客汇总][SpringCloud]

2.[为啥一线大厂面试必问Redis，有啥好问的？][Redis]

3.[Java多线程面试必备基础知识汇总][Java]

4.[Java集合源码分析汇总][Java 1]

5.[Linux常用命令汇总][Linux]

6.[JVM系列文章汇总][JVM]

7.[MySQL系列文章汇总][MySQL]

8.[RabbitMQ系列文章汇总][RabbitMQ]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

####  ####

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f4bb4f434db8448999a88b32ec370529.png
[640_wx_fmt_gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/45f767c58cf94f02916fd54e58d6a958.gif
[640_wx_fmt_jpeg 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7006dd804dcd41db92b12ca1537c94bc.png
[640_wx_fmt_jpeg 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/edbf4de6c1294a47a165c0f512e46c5c.png
[640_wx_fmt_gif 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/0c70f06132f34f2fa8c6a151ade846a4.gif
[SpringCloud]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484030&idx=1&sn=7ad29239aca876e29155f5b1439281bb&chksm=fe396840c94ee156adfcd44c63a3b5c1cf93805cf592ad7d45bc5222c349ba6f552b553a5c09&scene=21#wechat_redirect
[Redis]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484172&idx=1&sn=cad78126f0367dbd67e0336b0b369b5d&chksm=fe396932c94ee0248ce1527844d9664a01e29a43b11b1910aa415facdc569c82a63cb07e44cf&scene=21#wechat_redirect
[Java]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484030&idx=2&sn=ddf120fcbfc45238e64662fd183156de&chksm=fe396840c94ee156a80b744033ac34d67e331545193d2f9d4f2943995aa4412a53fec023d599&scene=21#wechat_redirect
[Java 1]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484098&idx=1&sn=ba605ae1b35d6f2a8caef5901f0b86f6&chksm=fe3968fcc94ee1ea2493ce7faaab40316fa3954effa1613165b47955f5c097ef96c400b1485b&scene=21#wechat_redirect
[Linux]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484117&idx=1&sn=b4c6eb9b4027390767e92efad018a08e&chksm=fe3968ebc94ee1fdf40b5192f574b0e7cdc176663411c7f9f44c814a71a14139c510b0c35bf2&scene=21#wechat_redirect
[JVM]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484238&idx=1&sn=a30cd56a84f93da11bf916591612ef8d&chksm=fe396970c94ee066ef23c65375f88dd6ff727fd1c03c60ba61d1a9072a879cbb54084f779107&scene=21#wechat_redirect
[MySQL]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484315&idx=1&sn=8aaa78331f58909420c5e1d283d070e1&chksm=fe3969a5c94ee0b38f5152157b187f136a8dcb283039a715e8161d2e5fa98de92b66d0522cb4&scene=21#wechat_redirect
[RabbitMQ]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484392&idx=1&sn=700f4eb1b4b3ca3ac29f1445a3a3f79c&chksm=fe3969d6c94ee0c019e758880cc53d57496f6f104d76231d1e3eea8973558db5cc30611f8154&scene=21#wechat_redirect
[640_wx_fmt_jpeg 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/28a3a839b4644c87846322693450b884.png