1.2. 利用计算机求解问题的基本方法和步骤¶

问题抽象、数据抽象、算法抽象

1.2.1. 一个简单的例子: 求任一非负实数 \(x\) 的平方根¶

数学定义: 满足等式 \(y\times y = x\) 的非负实数 \(y\)
考虑到通常计算机只能得到实数的平方根近似值, 上述问题可修改为: 对任意非负实数 \(x\), 寻找非负实数 \(y\), 使得 \(|y\times y-x|<e\), 其中 \(e\) 是给定的允许误差
这样就有了问题的一个严格描述. 但这个描述是说明性的, 并没有告诉如何得到这个 \(y\)

求任一正实数平方根的牛顿迭代法:

首先这是一个算法, 因为它描述了一个计算过程. 只要能做实数的算术运算、求绝对值和比较大小, 就可以执行上面描述的计算过程.
但是, 要确定这个算法能求出正实数的平方根, 还需要证明:
1. 对任意正实数 \(x\), 如果算法结束, 它一定能给出 \(x\) 的平方根的近似值;
2. 对任意给定的误差 \(e\), 这个算法一定能结束.

有了上面的算法, 我们可以很容易定义一个计算平方根的 Python 函数:

输入:
- 灯的状态由一个 \(5\times 6\) 的 \(0-1\) 矩阵表示
  - \(0\) 表示灯的状态是熄灭的
  - \(1\) 表示灯的状态是点亮的
输出:
- 需要按下的按钮由一个 \(5\times 6\) 的 \(0-1\) 矩阵表示
  - \(0\) 表示不需要按对应的按钮
  - \(1\) 表示需要把对应的按钮按下

枚举所有可能的按钮(开关)状态,对每个状态计算一下最后灯的情况,看是否都熄灭
- 每个按钮有两种状态(按下或不按下)
- 一共有30个开关,则状态数是 \(2^{30}\), 计算量太大
如何减少枚举的状态数目呢? 基本思路: 如果存在某个局部,一旦这个局部的状态被确定,那么剩余其他部分的状态只能是确定的一种,或者不多的n种,则只需要枚举这个局部的状态即可
对于本问题, 第1行就是这样一个”局部”
- 在第1行的各个状态确定的情况下, 这些开关作用后, 将导致第1行某些灯是亮的,某些灯是灭的
- 要熄灭第1行某个亮着的灯, 则唯一的办法就是按下第2行对应的开关. 为了使第1行的灯全部熄灭, 第2行的合理开关状态就是唯一的.
- 第2行确定后, 第3行的合理开关状态也就唯一确定了. 以此类推, 最后一行的开关状态也是唯一确定的.
- 推算出最后一行的开关状态, 然后看最后一行的开关作用后, 最后一行的所有灯是否都熄灭.
  - 如果是, 则这就是一个可行解得状态
  - 如果不是, 则第1行换个状态重新试试
- 枚举第1行所有的状态, 共有 \(2^6\)
思考: 有没有状态数更少的做法?

国际象棋的棋盘为 \(8*8\) 的方格棋盘, 现将“马”放在任意指定的方格中, 按照“马”走棋的规则将“马”进行移动. 要求每个方格只能进入一次, 最终使得“马”走遍棋盘64个方格.