简单编程问题集

本文为Simple Programming Problems的中文译文，感谢 Adrian Neumann。本文遵循CC-BY-SA协议。

我会不时更新一些自己学习新语言时对这些问题的部分解答。

以下为译文。

---

计算机入门课上学生需要学习一些编程语言，我当助教的时候发现找到好的练习题很麻烦。类似Project Euler 的问题集通常对初学者来说太难了，尤其是在他们没有很强的数学背景时。

这个页面的一系列练习题适合初学者，其难度逐渐提高，我找到新的练习题后会扩充。除了GUI部分，这些练习一般是算法问题，不需要学习任何类库就可以解决。练习题的难度一定程度上与你使用的编程语言相关。比如对于列表相关的练习题，类似C语言等没有内置列表支持的语言处理起来就更复杂。

尽管有些简单了，我想这些练习对有经验的人学习新的语言时也是有用的。

基础问题

1. 写一个程序输出“Hello World” 到屏幕。
2. 写一个程序询问用户的名字，然后带上他的名字问好。
3. 修改上一个程序，使得只有Alice 和 Bob 会被带上名字问好。
4. 写一个程序询问用户一个数字n，然后输出1到n的和。
5. 修改上一个程序，求和时只计入3或5的倍数，比如n=17时，只计入3, 5, 6, 9, 10, 12, 15。
6. 写一个程序询问用户一个数字n，然后用户可以选择计算1到n的和还是乘积。
7. 写一个程序，输出九九乘法表。
8. 写一个程序，输出所有的质数。（注意：如果编程语言不支持任意大小的数值，输出该语言能表达的最大数以内的质数也可以。）
9. 写一个猜谜游戏：用户猜一个数，程序随即告知用户他猜的数太大还是太小，最后需要输出用户猜的总次数。如果用户连续输入同样的数字，则只计一次。
10. 写一个程序，输出未来的20个闰年。
11. 写一个程序计算下式：

列表和字符串

1. 写一个函数，返回列表中的最大元素。

2. 写一个函数反转一个列表，最好就地进行。

3. 写一个函数，检查某个元素是否出现在列表中。

4. 写一个函数，返回列表中奇数位置的元素。

5. 写一个函数计算列表的累计和。

6. 写一个函数，检查一个字符串是否是回文。

7. 写三个函数，计算列表中的数值之和，分别用for循环，while循环和递归实现。

8. 写一个函数on_all ，对列表中的每个元素进行函数变换。使用它输出前20个完全平方数。

9. 写一个函数拼接两个列表。

10. 写一个函数，在两个列表中交替取元素合并，比如[a,b,c], [1,2,3] → [a,1,b,2,c,3]。

11. 写一个函数，将两个有序列表合并成一个新的有序列表。

12. 写一个函数，旋转列表的k个元素，比如列表[1,2,3,4,5,6] 旋转2个元素变为 [3,4,5,6,1,2]。尝试不复制列表实现，需要多少次交换或移动操作？

13. 写一个函数，计算由斐波拉契数的前100个构造的列表。

14. 写一个函数，输入一个数值，输出其各位数字的列表。

15. 写一个函数,计算两个数字列表形式的数值的和、差与积（返回一个新的数字列表）。进一步的，可以实现Karatsuba算法。试一试不同的进制，哪种进制速度最快？如果你在做质数生成练习时因为语言缺乏大数支持能力而无法彻底实现，现在可以考虑使用你自己的库来实现了。

16. 实现下列排序算法：选择排序，插入排序，归并排序，快速排序，臭皮匠排序。可以通过Wikipedia获得算法描述。

17. 实现二分查找算法。

18. 写一个函数，获取字符串列表并输出到一个矩形文本框中，每行一个字符串。比如列表 ["Hello", "World", "in", "a", "frame"]的输出结果如下：

    *********
    * Hello *
    * World *
    * in    *
    * a     *
    * frame *
    *********
    

19. 写一个函数，将一段文本翻译为Pig Latin 并回译，英文翻译为Pig Latin 时，先将每个单词的首字母移到词尾，并加上后缀‘ay’，比如“The quick brown fox” 变为 “Hetay uickqay rownbay oxfay”。

中级问题

1. 写一个程序，在数字1,2,…,9（不改变顺序）中添加+或-或什么也不添加，找到所有结果为100的等式，比如1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100。
2. 写一个程序，已知一个假想的行星的一年的周期（以小数表示的天数），输出一个该行星的闰年历法规则，使其历法年与回归年的差异最小化。
3. 实现一个图的数据结构，它支持修改（插入、删除）。它应当能存储边和节点。最简单的实现方法之一是使用字典（节点，边列表）。
4. 写一个函数，生成图的DOT 格式表达式。
5. 写一个自动生成文章的程序。
6. 使用样本文本生成有向图，每一个单词是一个节点，如果在样本文本中单词v在单词u之后，则u和v之间有一条有向边。不同的单词组合出不同的边。
7. 在这个图上随机遍历，任选一个节点随机选择它的后继节点。如果没有后继节点，则随机选择另一个节点。
8. 写一个程序，翻译英文为摩斯码以及反过来。
9. 写一个程序，在字符串中找到最长的回文子字符串。尝试尽可能提高效率。
10. 设计一个列表(list)接口。一般典型的操作包括哪些？你可能需要研究你使用的语言的list接口实现或其他流行语言的实现。
11. 使用固定长度的内存实现列表，比如100个元素的数组。如果用户添加元素超过了内存限制，则输出一个错误信息，比如如果语言支持的话可以抛出异常。
12. 改进你的前一个实现，使列表能存储任意数量的元素。比如当列表增长时可以分配更大块的内存，把原来的元素拷贝过来并释放原来的内存块。当列表收缩时，可以考虑释放部分内存。考虑每次分配内存时的容量，以免分配内存成为程序的瓶颈，每次分配时增加长度为1的内存就不是一个好方法。
13. 如果你的上一实现使用了正确的内存增长方法，则不会经常进行内存分配。然而在一个大的列表中增加元素可能消耗太多的时间，这在某些应用中会成为问题。当列表满需要增加元素时，新分配一个长度为100的内存块，而不是将原来的元素拷贝过来。这时，需要对列表占据的内存块进行记录。不同的记录策略会验证影响列表的性能表现。
14. 实现二叉堆。分别基于列表和链表二叉树实现。使用其实现堆排序。
15. 实现非平衡二分查找树。
16. 实现平衡二分查找树。比如 (a,b)树。
17. 比较你实现的非平衡二分查找树、平衡二分查找树和有序列表中插入、删除和查找的的性能。考虑好的输入序列。如果实现了 (a,b)树，考虑好的a、b值。

高级问题

1. 给定两个字符串，写一个程序高效的查找其最长公共子序列。
2. 给定一个数值数组，写一个程序高效的回答下述问题："离位置i的数值最近的较大的数是哪个？"数值间的距离指的是它们在列表中的索引的距离。比如数组[1,4,3,2,5,7]中离数值4最近的较大的数是5。 经过线性时间的处理，可以以常数时间回答该问题。
3. 给定两个字符串，找到一个最短的字符插入和删除的变换序列，使一个字符串变为另一个。
4. 写一个函数实现矩阵乘法。尽可能提高效率并与该语言中的出色的线性代数库函数做比较。你可能需要学习Strassen算法和CPU的缓存效应。尝试矩阵的不同布局看会发生什么。
5. 实现 van Emde Boas 树. 和你之前实现的搜索树结构作比较。
6. 给定一系列的d维矩形盒，写一个程序计算它们的并集的容积。从二维开始考虑逐步提高。

GUI问题

1. 写一个程序，显示一个跳动的球。
2. 实现记忆游戏。
3. 实现俄罗斯方块游戏。

开放问题

1. 写一个程序玩猜单词游戏。比如可以使用像[这样]的大型词典，选择排除仍然可能的解决方案的大部分单词的字母。尽量提高程序的效率，不要每个回合都扫描整个词典。
2. 写一个程序和人玩石头、剪刀、布的游戏，它使用的策略应优于随机选择。注意人不善于生成随机数。
3. 写一个程序和人玩海战棋。它输入被攻击的坐标报告是否击中，并输出自己的攻击坐标。

其他的问题集

显然我不是构建类似问题集的第一人。

• John Dalbey的问题集
  • Several small problems Programming Practice
  • CPE 101 Projects
• Code Kata
• 99 Lisp Problems, 99 Haskell Problems. 大部分问题也可以用其他语言解决。
• Rosetta Code Programming Tasks. 这些问题可以用很多语言解决。
• Code Golf Challenges. 目标是用最少的字符解决问题。
• SPOJ Problems. 这是一个超过13000个问题的列表！
• Code Abbey 据称相比Project Euler不需要太多的数学功底。