SimpleProgrammingProblems

KO | EN

gitlite — search

#python #hacktoberfest #react #llm #android #machine-learning #nodejs #windows #cli #awesome-list #vue #security #ios #openai

SimpleProgrammingProblems

(★ 39)

简单编程问题集中译版

SimpleProgrammingProblems 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# 简单编程问题集

本文为[Simple Programming Problems](https://adriann.github.io/programming_problems.html)的中文译文，感谢 Adrian Neumann。本文遵循[CC-BY-SA](https://creativecommons.org/licenses/by-sa/3.0/cn/)协议。

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

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

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

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

## 开始之前

学习编程就是学习如何使用代码解决问题。从概念上来说，如果你能够不通过编程手动解决一个问题，那么通过编程解决也不难。你需要掌握的技巧是精确的思考自己是如何解决这个问题的，然后把过程切分到足够简单，简单到计算机能执行。面对问题时，我建议你先尝试手动解决，想想为了解决问题你都做了什么工作。比如任务是给列表排序，那么就手动给一些短的列表排序看看。一个可行的方法是找到最小的元素，写下来，并在原来的列表上划掉这个数，重复这个过程直到完成排序。然后你就可以教导计算机： 1）如何找到最小的数，2）如何把它写下来，3）如何划掉这个数，以及循环这些流程。持续这个分解任务的过程，直到你确信知道如何编写必要的程序。

为了让你的编程任务进展顺利，你需要尽早彻底的测试。每个人编程时都会犯错误，找错误花费了程序员相当部分的工作时间。在小而简单的程序中找错误，要比在大型程序中找错误简单得多。所以在任务分解的过程中，你要测试每一个子任务。这样你才能对工作的每个部分都有信心，然后尝试把它们拼到一起。同时你也需要对程序做整体测试，因为某些错误只有在不同的部分交互时参会发现。测试要尽量自动化。测试程序越轻松，试验性修改程序时就越自由。

最后一个重点是如何使用代码表达你的想法。正如可以在文章中用不同的语言表达相同的意思，也可以用不同的代码来表达相同的问题解决方法。试着写得简洁一些。那些没有写下的代码，是百分之百不会有bug的。在自己尝试之后，可以用google搜索更地道的表达。记住代码不是写给机器看的，而是写给人看的。（也许那个人就是以后的你！）使用能表达含义的命名，通过命名无法充分说清的就需要写注释。注释一定不能写成代码在做什么，而应该解释为什么这么做。

这是一个错误的示范：

```
// 这个函数检查一个数是不是偶数
def f(x):
  // 计算x除以2的余数，检查它是不是0
  if modulo(x,2) == 0:
    // 这个数是偶数
    return True
  else:
    // 这个数是奇数
    return False
```

同样的想法，如果你这样写会更好理解：

```
def is_divisible(number, divisor):
  return modulo(number, divisor) == 0

def is_even(number):
  return is_divisible(number, 2)
```

有更好的命名和更好的任务分解，注释都是多余的。像修订论文一样修订代码。不断的重复打草稿、写下来、删除掉、重新组织的过程，问问其它人的看法，直到你的想法只剩下最清晰的表达。重新审查你前一段时间写的代码，看看能不能用你新学到的知识去改进它。

## 基础问题
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. 写一个程序计算下式：

## 列表和字符串
如何你学习的语言灭有内置的列表或字符串类型（比如C语言），下面的练习也可以用数组来解决。不过有些解决方案视乎列表是基于数组（比如C++的`vector`）还是基于指针（比如C++的`list`）差别很大，尤其是你关心效率的时候。所以如果你学习的语言没有` linked list `，你可能需要找一个库，或者自己研究实现一个。

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算法。试一试不同的[进制](https://en.wikipedia.org/wiki/Radix)，哪种进制速度最快？如果你在做质数生成练习时因为语言缺乏大数支持能力而无法彻底实现，现在可以考虑使用你自己的库来实现了。

16. 写一个函数，输入一个数字列表，代表b1进制的数，把它转换b2进制的数。（都以数字列表的形式）。比如三进制的数字列表[2,1,0]变成十进制的数字列表[2, 1]。（都代表十进制数21 ）

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

18. 实现二分查找算法。

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

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

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

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

## GUI问题
1. 写一个程序，显示一个跳动的球。
2. 实现[记忆游戏](https://en.wikipedia.org/wiki/Memory_%28game%29)。
3. 实现俄罗斯方块游戏。

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

## 其他的问题集
显然我不是第一个构建类似问题集的人。
* [John Dalbey](http://users.csc.calpoly.edu/~jdalbey/)的问题集
  * Several small problems [Programming Practice](http://users.csc.calpoly.edu/~jdalbey/103/Projects/ProgrammingPractice.html)
  * CPE 101 [Projects](http://users.csc.calpoly.edu/~jdalbey/101/index.html)
* [Code Kata](http://codekata.pragprog.com/)
* [99 Lisp Problems](http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html), [99 Haskell Problems](http://www.haskell.org/haskellwiki/99_Haskell_exercises). 大部分问题也可以用其他语言解决。
* [Rosetta Code Programming Tasks](http://rosettacode.org/wiki/Category:Programming_Tasks). 这些问题可以用很多语言解决。
* [Code Golf Challenges](http://codegolf.com/competition/browse). 目标是用最少的字符解决问题。
* [SPOJ Problems](http://www.spoj.com/problems/classical/). 这是一个超过13000个问题的列表！
* [Code Abbey](http://codeabbey.com/) 据称相比Project Euler不需要太多的数学功底。

SimpleProgrammingProblems

SimpleProgrammingProblems 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

SimpleProgrammingProblems

SimpleProgrammingProblems 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README