第 07 章　程序设计方法

学习目标

理解过程式、函数式和生态式编程。
用自顶向下的方法拆分问题。
使用蒙特卡洛方法估计随机问题。
使用递归表达可以分解的计算问题。

1. IPO 方法

程序可以分成输入 Input、处理 Process 和输出 Output。例如，输入长和宽，处理面积公式，输出面积。先确定输入输出，再设计处理步骤。

2. 过程式编程

过程式编程按照解决问题的步骤编写语句：

total = 0
for score in [88, 92, 76]:
    total += score
print(total / 3)

它强调顺序、分支和循环，适合步骤清楚的问题。

3. 函数式编程

函数式编程把问题拆成若干功能明确的函数：

def total(values):
    result = 0
    for value in values:
        result += value
    return result

def average(values):
    return total(values) / len(values)

print(average([88, 92, 76]))

每个函数只承担一种功能，主程序负责组合这些函数。

4. 自顶向下

估算班级成绩时，可以先写成：

scores = read_scores()
result = average(scores)
show_result(result)

然后再分别实现读取、计算和显示。先写整体流程，再实现每个部分，这就是自顶向下设计。

5. 生态式编程

生态式编程直接使用成熟的标准库或第三方库。例如，随机数使用 random，绘图使用 turtle，中文分词使用 jieba。库能够可靠完成任务时，不必从零编写全部代码。

6. 蒙特卡洛方法

蒙特卡洛方法通过大量随机试验估计结果。单位正方形中随机投点，点到原点距离不超过 1 的比例，可用来估计四分之一圆面积：

import random

times = 10000
inside = 0
for i in range(times):
    x = random.random()
    y = random.random()
    if x * x + y * y <= 1:
        inside += 1
print(4 * inside / times)

随机次数越多，结果通常越接近圆周率，但每次结果不一定完全相同。

7. 递归计算方法

递归把问题分成相同形式、规模更小的问题。计算阶乘时，n! = n * (n - 1)!，而 1! = 1：

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

必须先写停止条件，否则递归不会结束。

本章练习

用 IPO 描述温度转换程序的输入、处理和输出。
把平均分计算拆成两个函数。
用 1000 次随机试验估计掷骰子得到 6 点的比例。
用递归计算 1 到 n 的和。

本章小结

过程式强调步骤，函数式强调功能拆分，生态式强调使用现有库。
自顶向下先设计总体，再实现细节。
蒙特卡洛方法用大量随机试验估计结果。
递归方法需要基例和规模递减的递归关系。

第 07 章 程序设计方法