1难不等于不可能
一道要算一百年的题，属于"难"还是"不可能"？
计算机原理 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2有些永远无解
"以后电脑更强了就能解"，这句话对无解问题成立吗？
3会不会停下
举一个会"永远停不下来"的简单程序想法。
4停机问题
停机问题问的到底是什么？
5自己问自己
捣蛋程序的策略是什么？
6矛盾的证明
出现"怎么都矛盾"时，说明哪一步的假设是错的？
7快与慢
为什么"能解"还不够，我们还关心"解得快不快"？
8P类问题
把一堆数字从小到大排好，属不属于"能快速解决"这类？
9验证很容易
给你一把钥匙，试它能不能开锁，快还是慢？自己配一把能开的钥匙呢？
10NP类问题
一个能快速解决的问题，一定也能快速验证吗？
第 1 页 · 背面（答案）
参考答案（家长）：不成立；无解是本质限制，再强的电脑也解不了。
参考答案（家长）："难"（慢而已，原则上仍可算完），不是"不可能"。
参考答案（家长）：能否有一个程序，对任意程序和输入，都判断它会停下还是永远运行。
参考答案（家长）：如"只要1不等于2，就一直重复打印1"——条件永远成立，永不停下。
参考答案（家长）：说明"存在万能停机检查器"这个假设是错的，它不可能存在。
参考答案（家长）：总跟检查器的预测相反——预测停就不停，预测不停就停。
参考答案（家长）：属于；有又快又稳的办法，数据变大也不会慢到爆炸。
参考答案（家长）：因为太慢的办法在现实中等不起，慢到几百年就跟没法用一样。
参考答案（家长）：一定能；自己都能快速算出来，验证别人的答案自然也快。
参考答案（家长）：试开很快（验证易）；自己配出能开的钥匙很难（求解难）。
第 2 页 · 正面（题目）
11P等于NP吗
用一句话说清P vs NP在问什么。
12百万美元难题
为什么"大家都觉得不相等"还不能算解决了这个问题？
13把问题变问题
你会算长方形面积，怎么把"算正方形面积"归约成它？
14归约的力量
若难题A能归约成B，谁至少和谁一样难？
15最难的一类
解决一个NP完全问题，为什么会牵动一整片问题？
16旅行商与背包
5个城市要走一圈，若一条条路线去试，方案数会随城市增多而怎样变化？
17差不多就好
送快递排路线，一时找不到最短路，用"较短的一条"行不行？
18掷骰子算题
一个随机办法每次出错概率只有一半，独立做3次都错的概率是多少？
19边界在哪里
说出这三类问题各一个例子。
20理论的用处
网上银行的密码为什么难被破解，却容易被验证正确？用今天学的话说说看。
第 2 页 · 背面（答案）
参考答案（家长）：科学讲证明不讲感觉；没有严格证明，觉得再有道理也不算数。
参考答案（家长）：能快速验证答案的问题，是不是也一定能快速找到答案。
参考答案（家长）：B至少和A一样难（会解B就能解A）。
参考答案（家长）：正方形是长宽相等的长方形，直接套长方形面积公式即可。
参考答案（家长）：飞快暴涨（组合爆炸），城市稍多就多到根本试不完。
参考答案（家长）：因为所有NP问题都能归约到它，攻破它等于攻破全部NP问题。
参考答案（家长）：二分之一连乘三次＝八分之一，多试几次错的机会就很小了。
参考答案（家长）：多数情况下行；差不多短就能省不少时间，不必非等最优解。
参考答案（家长）：它属于"验证容易、求解（破解）很难"那类问题，正确密码一验就过，硬猜却难到几乎不可能。
参考答案（家长）：不能解——停机问题；能解但慢——旅行商找最优；又快又好——把数字排序。
第 3 页 · 正面（题目）
21程序会长大
想想你写过最长的程序有多少行？如果过一个月再看，还看得懂吗？
22起个好名字
把 int a = 90; 改个能看出意思的名字。
23注释写什么
给 if (n == 0) return 1; 写一句有用的注释。
24一个函数干一件事
把"读入成绩并算平均分并打印"拆成几个函数？
25不要复制粘贴
找找你以前的代码里有没有复制粘贴的段落。
26代码要有格式
把一行挤在一起的代码手动排整齐。
27程序为什么出错
7 / 0、prnit("hi")、把加号写成减号，各属于哪一种？
28看懂报错信息
故意写错一行代码，读一读报错，找出行号和错误类型。
29打印大法
写个求和程序，在循环里打印每一轮的 sum。
30缩小范围
这个思路像我们学过的哪个算法？
第 3 页 · 背面（答案）
参考答案（家长）：如 int pass_score = 90; —— 一看就知道是及格线。
参考答案（家长）：多数人一个月后看不懂自己的代码，这正是要学工程方法的原因。
参考答案（家长）：至少三个：读入、求平均、输出。各自独立，都好测。
参考答案（家长）：如"// 0 的阶乘规定为 1，是递归的边界"——说明原因而非重复代码。
参考答案（家长）：整齐后错误更容易一眼看出来。
参考答案（家长）：抽成函数后，改一处即可，错的机会少三倍。
参考答案（家长）：报错是帮手不是敌人，读懂它能省下大量时间。
参考答案（家长）：依次是运行错、语法错、逻辑错。
参考答案（家长）：二分查找。排错和找数字，思路是一样的。
参考答案（家长）：看到 sum 逐轮变化，就能发现是哪一轮开始不对。