文档介绍：下楼问题
第八讲递归算法举例
八皇后问题
1
讨论问题“下楼问题”
从楼上走到楼下共有h个台阶,每一步有三种走法
走一个台阶;
走二个台阶;
走三个台阶。
问可走出多少种方案,希望用递归思想来编程。
2
定义:
Try(i,s)——站在第i级台阶上往下试走第s步的过程
j=1,2,3 ——在每一步可以试着走的台阶数
take[s] ——存储第s步走过的台阶数
i<j ——说明第i级台阶已比要走的j级台阶小,j不可取
i>j ——说明站在第i级台阶上可试走j个台阶为一步
i==j ——说明这一步走完后已到了楼下,这时一条下楼方案已试成,即可输出这一方案了
3
思路:
1、用枚举的方法,试着一步一步地走,从高到低,让i先取h值从楼上走到楼下,每走一步i的值会减去每一步所走的台阶数j,即i=h(初值),以后i=i-j,(j=1,2,3),当i=0时,说明已走到楼下。
2、枚举时,每一步都要试j或者是为1,或是为2,或是为3。这时可用for循环结构。
3、每一步走法都用相同的策略,故可以用递归算法。
4
见图
5
在上图中,A结点是被递归调用的结点,形式参数为i,s,A结点为一个与结点,进入B结点时的三个参数为i,s,j=3;进入C结点的参数为i,s,j=2;进入D结点的参数为i,s,j=1。Lp是三个结点都可用的循环体Lp。
Lp是一个分支结构的或结点。
6
(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)。
7
8
#include <> // 预编译命令
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 ……
9
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); // 再试剩下的台阶(递归调用)
}
}
10