计算机问题求解

程序开发过程

---

• 分析阶段：程序开发的第一步是弄清问题。在软件开发领域，这一工作阶段通常被称为需求分析。
• 设计阶段：问题的严格描述仍然是描述性的，而计算机求解是一个操作过程。在真正编程之前，需要有一个能解决这个问题的计算过程模型。这种模型包括两个方面，一方面需要表示计算中处理的数据，另一方面必须有求解问题的计算方法，即通常所说的算法。
• 编码阶段：有了解决问题的抽象计算模型，下一步工作就是用某种适当的编程语言实现这个模型，做出一个可能由计算机执行的实际计算模型，也就是一个程序。
• 检查测试阶段：复杂的程序通常不可能一蹴而就，写出的代码中可能有各种错误，最简单的是语法和类型错误。经过反复检查修改，最后得到一个可以运行的程序。
• 测试/调试阶段：程序可以运行并不代表它就是所需的那个程序，还需要通过尝试性的运行确定其功能是否满足需要，这一工作阶段称为测试和调试。测试/调试过程中可能会出现运行时错误和逻辑错误，需要修正，直至得到令人满意的程序。
• 以上即一个从问题出发，最终得到可用程序的开发过程。
• 相对而言，设计阶段的工作更困难一些。编码阶段的工作相对容易一些。

一个简单例子

---

虽然一个问题的说明性描述与其操作性描述表达的是同一个问题，但它们却非常不同。前者说明了需要解决的问题是什么，针对什么样的问题，期望什么样的解；而后者说明通过怎样的操作过程可以得到所要的解。

如：求出任一个非负实数的平方根（牛顿迭代法）。

算法描述

---

1. 对给定正实数 x 和允许误差 e ，令变量 y 取任意正实数值，如令 y=x ；
2. 如果 y*y 与 x 足够接近，即 |y*y-x| < e ，计算结束并把 y 作为结果；
3. 取 z=(y+x/y)/2 ；
4. 将 z 作为 y 的新值，回到步骤 1 。

Python 程序实现

---

def sqrt(x):
    y = 1.0
    while abs(y * y - x) > 1e-6:
        y = (y + x/y) / 2
    return y

其中，变量 y 初值为 1.0，允许误差为 10^-6。通过各种数值测试，可以看到这个函数确实能完成所需要的工作。

总结

---

在上述例子中，最不清晰的是从平方根的定义到求平方根的算法。然而 ......

算法设计是一种创造性工作，依赖于对问题的认识和相关领域的知识，没有放之四海而皆准的路径可循。

摘自北大裘宗燕老师《数据结构与算法》