1
?下楼问题
第八讲 递归算法举例
?八皇后问题
2
讨论问题,下楼问
题”
从楼上走到楼下共有 h个台阶，每一步有三种走法
?走一个台阶；
?走二个台阶；
?走三个台阶。
问可走出多少种方案，希望用递归思想来编程。
3
定义,
?Try(i,s)——站在第 i级台阶上往下试走第 s步的过程
?j=1,2,3 —— 在每一步可以试着走的台阶数
?take[s] —— 存储第 s步走过的台阶数
?i<j —— 说明第 i级台阶已比要走的 j级台阶小,j不
可取
?i>j —— 说明站在第 i级台阶上可试走 j个台阶为一步
?i==j —— 说明这一步走完后已到了楼下，这时一条
下楼方案已试成，即可输出这一方案了
4
思路,
1、用枚举的方法，试着一步一步地走，从高到低，让 i
先取 h值从楼上走到楼下，每走一步 i的值会减去每一
步所走的台阶数 j，即 i=h（初值），以后 i=i-j，
(j=1,2,3)，当 i=0时，说明已走到楼下。
2、枚举时，每一步都要试 j或者是为 1，或是为 2，或是
为 3。这时可用 for循环结构。
3、每一步走法都用相同的策略，故可以用递归算法。
5
见图
输出
A tr y(i,s)
i<j
1
j=3
F
2
Lp Lp
Lp
H
Q
B
E
G
P
C
D
tr y(i -j,s+1)
什么也不做
i>=j
take[ s]=j
i==j
i>j
6
在上图中,A结点是被递归调用的结点，
形式参数为 i,s,A结点为一个与结点，
进入 B结点时的三个参数为 i,s,j=3；进
入 C结点的参数为 i,s,j=2；进入 D结点
的参数为 i,s,j=1。 Lp是三个结点都可
用的循环体 Lp。
Lp是一个分支结构的或结点。
7
（ 1）当 i<j时，说明第 i级已经比一步该走的台阶数
小了。这是一个直接可解结点 E，什么也不做。
（ 2）当 i>=j时，要做相关联的 G和 H,G是直接可解
结点，将第 s步走过的台阶数 j记入 take数组，即
take[s]=j；接着做 H,H为或结点，有两个分支,
其一是：当 i==j时，说明经过第 s步，已走到楼下，
输出该下楼行走方案，并将方案号加 1；
其二是：当 i>j时，说明经过第 s步，尚未走到楼下，
尚需再试第 s+1步的走法，注意这时站在第 i-j级
台阶上。因此要调用 try(i-j,s+1)。
8
for ( j =3; j > 0; j= j - 1)
T F i <j
tak e [s]= j;
i= =j
T F
n um = n u m + 1;
输出第 n um 方案下的从第
1 步到第 s 步的走法
tr y( i - j,s + 1);
9
#include <stdio.h> // 预编译命令
int take[11]; // 定义全局变量：数组 take，方案数 num
int num = 0;
void try(int i,int s) // 被调用函数
{
int j,k; // 定义整型变量 j表示每步允许走的台阶数,
// k临时变量
for (j = 3; j > 0; j = j - 1) // 循环
{ // 循环体开始
if (i < j) // 如果所剩台阶数小于允许走的台阶数 j,
{ // 什么也不做
}
// else ……
10
else // 以下是 i>=j的情况
{
take[s] = j; // 记录第 s步走 j个台阶
if (i==j) // 如果已经到了楼下，做下列事情
{
num = num + 1; // 方案数加 1
printf("方案 %d, ",num); // 输出方案数
for (k=1; k<=s; k=k+1) // 输出本方案的每一步
{ // 所走的台阶数
printf("%d ",take[k]);
}
printf("\n"); // 换行
}
else // 尚未走到楼下
{
try(i-j,s+1); // 再试剩下的台阶（递归调用）
}
}
11
} // 循环体结束
} // 函数体结束
void main() // 主函数
{
int h; // 定义整型变量 h是楼梯的台阶数
printf(“请输入楼梯的台阶数,"); // 提示信息
scanf("%d",&h); // 输入楼梯的台阶数
try(h,1); // 调用函数 try(h,1)
printf("总方案数,%d\n",num); // 输出总方案数
}
12
1
3 2 1
1 3 2 1
2 2
1 1 1 1
4
13
八皇后问题
14
在 8× 8的棋盘上，放置 8个皇后（棋子），使两两之
间互不攻击。所谓互不攻击是说任何两个皇后都
要满足,
（ 1）不在棋盘的同一行；
（ 2）不在棋盘的同一列；
（ 3）不在棋盘的同一对角线上。
因此可以推论出，棋盘共有 8行，每行有且仅有一个
皇后，故至多有 8个皇后。这 8个皇后每个应该放
在哪一列上是解该题的任务。我们还是用试探的
方法, 向前走，碰壁回头, 的策略。这就是, 回
溯法, 的解题思路。
15
1、定义 try(i)——试探放第 i行上的皇后。
2、讨论将第 i行上的皇后放在 j列位置上的安全性。
我们可以逐行地放每一个皇后，因此，在做这一
步时，假定第 i行上还没有皇后，不会在行上遭到
其它皇后的攻击。只考虑来自列和对角线的攻击。
我们定义 q(i)=j表示第 i行上的皇后放在第 j列，
一旦这样做了，就要考虑第 i个皇后所在的列不安
全了，这时让 C[j]=false，同时，要考虑通过
(i,j)位置的两条对角线也不安全了。分析看出从
左上到右下的对角线上的每个位置都有 i-j=常数
的特点；从左下到右上的对角线上的每个位置都
有 i+j=常数 的特点。比如下图的两条对角线上的
点，一条有 i-j=-1，一条有 i+j=7的特点。
16
1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
8
17
利用这个特点，我们可以令
L[i-j] = false;
R[i+j] = false;
来表示在 (i,j)位置放皇后之后，通过该位置的两条
对角线上不安全了。
这样我们得出了在 (i,j)位置放皇后的安全条件为
nq=C[j]&&L[i-j]&&R[i+j]
为了判断安全条件，在程序中要用到三个数组
（ 1） C[j]为布尔型的,j=1,2,…,8，初始化时全部
置为 true；
（ 2） L[k]为布尔型的,k=i-j,k=-7,-6,…,7，初始
化时全部置为 true；
（ 3） R[m]为布尔型的,m=i+j,m=2,3,…,16，初始
化时全部置为 true；
18
3、从思路上，在放第 i个皇后时（当然在第 i行），选第 j列，
当 nq为 true时，就可将皇后放在 (i,j)位置，这时做如下 3
件事
（ 1）放皇后 q[i]=j，同时让第 j列和过 (i,j)位置的两条对角
线变为不安全。即让
C[j]=false;L[i-j]=false;R[i+j]=false;
（ 2）之后查一下 i是否为 8，如果为 8，则表明已经放完 8个皇
后，这时让方案数 Num加 1，输出该方案下 8个皇后在棋盘上
的位置。否则，未到 8个，还要让皇后数 i加 1再试着放，这
时还要递归调用 tri(i+1)。
（ 3）是为了寻找不同方案用的。当着一个方案输出之后，要
回溯，将先前放的皇后从棋盘上拿起来，看看还有没有可
能换一处放置。这时要将被拿起来的皇后的所在位置的第 j
列，和两条对角线恢复为安全的。我们用与或图来描述 8皇
后问题的解题思路。
19
try(i+1)
A tr y(i )
不安全
8
j=1
2 …
Lp Lp
Lp
Num=Num+1;
输出一个棋局
什么也不做
安全
i==8
i<8
C[j] =true;
L[i- j] =true;
R[i+j ]=tr ue;
q[i ]=j;
C[j] =fal se;
L[i- j] =fal se;
R[i+j ]=fal se;
20
结 束
?下楼问题
第八讲 递归算法举例
?八皇后问题
2
讨论问题,下楼问
题”
从楼上走到楼下共有 h个台阶，每一步有三种走法
?走一个台阶；
?走二个台阶；
?走三个台阶。
问可走出多少种方案，希望用递归思想来编程。
3
定义,
?Try(i,s)——站在第 i级台阶上往下试走第 s步的过程
?j=1,2,3 —— 在每一步可以试着走的台阶数
?take[s] —— 存储第 s步走过的台阶数
?i<j —— 说明第 i级台阶已比要走的 j级台阶小,j不
可取
?i>j —— 说明站在第 i级台阶上可试走 j个台阶为一步
?i==j —— 说明这一步走完后已到了楼下，这时一条
下楼方案已试成，即可输出这一方案了
4
思路,
1、用枚举的方法，试着一步一步地走，从高到低，让 i
先取 h值从楼上走到楼下，每走一步 i的值会减去每一
步所走的台阶数 j，即 i=h（初值），以后 i=i-j，
(j=1,2,3)，当 i=0时，说明已走到楼下。
2、枚举时，每一步都要试 j或者是为 1，或是为 2，或是
为 3。这时可用 for循环结构。
3、每一步走法都用相同的策略，故可以用递归算法。
5
见图
输出
A tr y(i,s)
i<j
1
j=3
F
2
Lp Lp
Lp
H
Q
B
E
G
P
C
D
tr y(i -j,s+1)
什么也不做
i>=j
take[ s]=j
i==j
i>j
6
在上图中,A结点是被递归调用的结点，
形式参数为 i,s,A结点为一个与结点，
进入 B结点时的三个参数为 i,s,j=3；进
入 C结点的参数为 i,s,j=2；进入 D结点
的参数为 i,s,j=1。 Lp是三个结点都可
用的循环体 Lp。
Lp是一个分支结构的或结点。
7
（ 1）当 i<j时，说明第 i级已经比一步该走的台阶数
小了。这是一个直接可解结点 E，什么也不做。
（ 2）当 i>=j时，要做相关联的 G和 H,G是直接可解
结点，将第 s步走过的台阶数 j记入 take数组，即
take[s]=j；接着做 H,H为或结点，有两个分支,
其一是：当 i==j时，说明经过第 s步，已走到楼下，
输出该下楼行走方案，并将方案号加 1；
其二是：当 i>j时，说明经过第 s步，尚未走到楼下，
尚需再试第 s+1步的走法，注意这时站在第 i-j级
台阶上。因此要调用 try(i-j,s+1)。
8
for ( j =3; j > 0; j= j - 1)
T F i <j
tak e [s]= j;
i= =j
T F
n um = n u m + 1;
输出第 n um 方案下的从第
1 步到第 s 步的走法
tr y( i - j,s + 1);
9
#include <stdio.h> // 预编译命令
int take[11]; // 定义全局变量：数组 take，方案数 num
int num = 0;
void try(int i,int s) // 被调用函数
{
int j,k; // 定义整型变量 j表示每步允许走的台阶数,
// k临时变量
for (j = 3; j > 0; j = j - 1) // 循环
{ // 循环体开始
if (i < j) // 如果所剩台阶数小于允许走的台阶数 j,
{ // 什么也不做
}
// else ……
10
else // 以下是 i>=j的情况
{
take[s] = j; // 记录第 s步走 j个台阶
if (i==j) // 如果已经到了楼下，做下列事情
{
num = num + 1; // 方案数加 1
printf("方案 %d, ",num); // 输出方案数
for (k=1; k<=s; k=k+1) // 输出本方案的每一步
{ // 所走的台阶数
printf("%d ",take[k]);
}
printf("\n"); // 换行
}
else // 尚未走到楼下
{
try(i-j,s+1); // 再试剩下的台阶（递归调用）
}
}
11
} // 循环体结束
} // 函数体结束
void main() // 主函数
{
int h; // 定义整型变量 h是楼梯的台阶数
printf(“请输入楼梯的台阶数,"); // 提示信息
scanf("%d",&h); // 输入楼梯的台阶数
try(h,1); // 调用函数 try(h,1)
printf("总方案数,%d\n",num); // 输出总方案数
}
12
1
3 2 1
1 3 2 1
2 2
1 1 1 1
4
13
八皇后问题
14
在 8× 8的棋盘上，放置 8个皇后（棋子），使两两之
间互不攻击。所谓互不攻击是说任何两个皇后都
要满足,
（ 1）不在棋盘的同一行；
（ 2）不在棋盘的同一列；
（ 3）不在棋盘的同一对角线上。
因此可以推论出，棋盘共有 8行，每行有且仅有一个
皇后，故至多有 8个皇后。这 8个皇后每个应该放
在哪一列上是解该题的任务。我们还是用试探的
方法, 向前走，碰壁回头, 的策略。这就是, 回
溯法, 的解题思路。
15
1、定义 try(i)——试探放第 i行上的皇后。
2、讨论将第 i行上的皇后放在 j列位置上的安全性。
我们可以逐行地放每一个皇后，因此，在做这一
步时，假定第 i行上还没有皇后，不会在行上遭到
其它皇后的攻击。只考虑来自列和对角线的攻击。
我们定义 q(i)=j表示第 i行上的皇后放在第 j列，
一旦这样做了，就要考虑第 i个皇后所在的列不安
全了，这时让 C[j]=false，同时，要考虑通过
(i,j)位置的两条对角线也不安全了。分析看出从
左上到右下的对角线上的每个位置都有 i-j=常数
的特点；从左下到右上的对角线上的每个位置都
有 i+j=常数 的特点。比如下图的两条对角线上的
点，一条有 i-j=-1，一条有 i+j=7的特点。
16
1 2 3 4 5 6 7 8
1
2
3
4
5
6
7
8
17
利用这个特点，我们可以令
L[i-j] = false;
R[i+j] = false;
来表示在 (i,j)位置放皇后之后，通过该位置的两条
对角线上不安全了。
这样我们得出了在 (i,j)位置放皇后的安全条件为
nq=C[j]&&L[i-j]&&R[i+j]
为了判断安全条件，在程序中要用到三个数组
（ 1） C[j]为布尔型的,j=1,2,…,8，初始化时全部
置为 true；
（ 2） L[k]为布尔型的,k=i-j,k=-7,-6,…,7，初始
化时全部置为 true；
（ 3） R[m]为布尔型的,m=i+j,m=2,3,…,16，初始
化时全部置为 true；
18
3、从思路上，在放第 i个皇后时（当然在第 i行），选第 j列，
当 nq为 true时，就可将皇后放在 (i,j)位置，这时做如下 3
件事
（ 1）放皇后 q[i]=j，同时让第 j列和过 (i,j)位置的两条对角
线变为不安全。即让
C[j]=false;L[i-j]=false;R[i+j]=false;
（ 2）之后查一下 i是否为 8，如果为 8，则表明已经放完 8个皇
后，这时让方案数 Num加 1，输出该方案下 8个皇后在棋盘上
的位置。否则，未到 8个，还要让皇后数 i加 1再试着放，这
时还要递归调用 tri(i+1)。
（ 3）是为了寻找不同方案用的。当着一个方案输出之后，要
回溯，将先前放的皇后从棋盘上拿起来，看看还有没有可
能换一处放置。这时要将被拿起来的皇后的所在位置的第 j
列，和两条对角线恢复为安全的。我们用与或图来描述 8皇
后问题的解题思路。
19
try(i+1)
A tr y(i )
不安全
8
j=1
2 …
Lp Lp
Lp
Num=Num+1;
输出一个棋局
什么也不做
安全
i==8
i<8
C[j] =true;
L[i- j] =true;
R[i+j ]=tr ue;
q[i ]=j;
C[j] =fal se;
L[i- j] =fal se;
R[i+j ]=fal se;
20
结 束
