文档介绍：第二章 程序设计基本策略与方法
递归、逐步求精、分治是基本的算法（程序）设计策略与方法。许多复杂问题，使用它们都可迎刃而解。这几种策略与方法在后面要经常使用，这里先介绍它们的基本思想，进一步的例子将在后面的章节中见到。做为基础，我们先介绍它的功能是求出数组a中各数的大小次序号，存入数组b中的对应位置。例如，若a[]={4, 2, 3, 9, 6, 8, 7}, 则程序结束后，数组b内容为 b[]={3, 1, 2, 7, 4, 6, 5}, 表示4，2，3，9，6，8，7的大小次序分别为3，1，2，7，4，6，5。
void OrderNumbers(int *a, int n, int *b)
{
int i, j;
for (i=0; i<n; i++) b[i]= 1; ………………………..(1)： n
for (i=0 ; i<n-1; i++) ………………………………(2)：n-1
for (j=i+1; j<n ; j++) ………………………………(3)： (n-i-1)
if (a[i] < a[j]) ……………………………… ….(4)： (n-i-1)
b[j]++; …………………………………..(5)：最多为 (n-i-1)
else b[i]++;
return ;
}
10
总的语句频度最大为：
n + (n-1) + 3∑(n-i-1)
= 2n-1 + 3(n-1)n/2
= 3n2/2 +7n/2 – 1
= O(n2)
11
穷举/试探法
穷举法的基本思想是，分别列举出各种可能解，测试（试探）其是否满足条件（是否是欲求的解），若是，则输出之。
这里举一个解不定方程的例子。不定方程（组）是指因为独立方程个数少于变量个数而导致方程有多解的方程。例如，2x+3y=20就是一个不定方程。解这个方程，就是求出所有的解。不定方程一般都有限定条件，我们这里考虑正整数解的情况。解这个方程，一个简单的做法是，让x和y分别遍取0到20内的正整数，并代入方程计算，若值为20，则表示找到一组解。具体的程序片断如下。
for (i=0; i<=20; i++)
for (j=0; j<=20; j++)
if (2*i + 3*j == 20 ) cout<<"\n"<<i<<' '<<j;
12
递推法与迭代法
递推法与迭代法是两种风格类似的方法，它们都是基于分步递增方式进行求解，在许多其他更深入的算法设计方法中，都要结合这两种方法
13
递推法
递推法是针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成，它们都与问题规模相关，是相对于所相关的问题规模的完整解。不同的子解，其所相关的问题规模也随子解不同而递增。我们把这种由前面的子解得出后面的子解的规则称为递推关系。
例如，对于Fibonacci（1175~？，意大利数学家）数列：
1 1 2 3 5 8 13 21 34 …
设f(n)表示数列中第n项，则有：
f(1) = 1
f(2) = 1
f(k) = f(k-1) + f(k-2)
14
递推法的运用有如下两个关键：
寻找递推关系：这是最重要的问题。递推关系有解析和非解析两种。解析递推关系是指能用一般数学公式描述的关系，也称递推公式。非解析递推关系是指不能用一般的数学公式描述的关系，这类关系的描述，也许本身就是一个过程。
递推计算：递推计算的具体实现，可有非递归和递归两种。非递归是自底向上计算，即按子解规模的先小后大的次序递推计算，递归计算是指使用递归法计算，其形式上是自顶向下。关于递归法，我们将在后面集中讨论。
15
迭代法
迭代法和递推法类似，也是递增求解，但不同的是，递推法中，每步得到的解都是相对于对应问题规模的完整解，但对迭代法，中间步骤得到的解一般只是“近似解”，并不代表子问题的解（常常没有明确的子问题）
16
例：求a的平方根
float Sqrt(float a)
{
float precision=; //定义解的精度
float x, x0;
x=1;
do
{
x0=x;
x = 1+(a-1)/(x+1);
}while (x-x0>precision || x0-x>precision);
//当最近两个近似解的差的绝对值小于给定精度时结束
return x;
}
17
递归
递归与递归程序的概念
递归(Recursion)是一种描述与解决问题的基本方法，用来解决一类可归纳描述