第八讲弟归犷法举例 下楼问题 八皇后问题
1 ➢下楼问题 第八讲 递归算法举例 ➢八皇后问题
讨论问题“下楼问 从楼上走到楼下共有h个台阶,每一步有三种走法 >走一个台阶 >走二个台阶; 走三个台阶。 问可走出多少种方案,希望用递归思想来编程
2 讨论问题 “下楼问 题” 从楼上走到楼下共有h个台阶，每一步有三种走法 ➢ 走一个台阶； ➢ 走二个台阶； ➢ 走三个台阶。 问可走出多少种方案，希望用递归思想来编程
定义: >Try(i,s)站在第i级台阶上往下试走第s步的过程 j=1,2,3—在每一步可以试着走的台阶数 >take [s] 存储第s步走过的台阶数 >ii> 说明站在第i级台阶上可试走j个台阶为一步 说明这一步走完后已到了楼下,这时一条 下楼方案已试成,即可输出这一方案了
3 定义： ➢ Try(i,s)——站在第i级台阶上往下试走第s步的过程 ➢ j=1,2,3 —— 在每一步可以试着走的台阶数 ➢ take[s] —— 存储第s步走过的台阶数 ➢ ij —— 说明站在第i级台阶上可试走j个台阶为一步 ➢ i==j —— 说明这一步走完后已到了楼下，这时一条 下楼方案已试成，即可输出这一方案了
思路: 1、用枚举的方法,试着一步一步地走,从高到低,让 先取h值从楼上走到楼下,每走一步i的值会减去每 步所走的台阶数j,即ih(初值),以后i=i-j, (j=1,2,3),当i=0时,说明已走到楼下。 2、枚举时,每一步都要试或者是为1,或是为2,或是 为3。这时可用for循环结构。 3、每一步走法都用相同的策略,故可以用递归算法
4 思路： 1、用枚举的方法，试着一步一步地走，从高到低，让i 先取h值从楼上走到楼下，每走一步i的值会减去每一 步所走的台阶数j，即i=h（初值），以后i=i-j， (j=1,2,3)，当i=0时，说明已走到楼下。 2、枚举时，每一步都要试j或者是为1，或是为2，或是 为3。这时可用for循环结构。 3、每一步走法都用相同的策略，故可以用递归算法
A try(i, s) 见图 B p p p F 什窭也不 H akes]=j 输出 try(i-J,S+1)
5 见图 输出 A try(i,s) i=j take[s]=j i==j i>j
在上图中,A结点是被递归调用的结点, 形式参数为i,s,A结点为一个与结点, 进入B结点时的三个参数为i,s,j=3;进 入0结点的参数为i,s,j=2;进入D结点 的参数为i,s,j=1。Lp是三个结点都可 用的循环体Lp Lp是一个分支结构的或结点
6 在上图中，A结点是被递归调用的结点， 形式参数为i,s，A结点为一个与结点， 进入B结点时的三个参数为i,s,j=3；进 入C结点的参数为i,s,j=2；进入D结点 的参数为i,s,j=1。Lp是三个结点都可 用的循环体Lp。 Lp是一个分支结构的或结点
(1)当ij时,说明第i级已经比一步该走的台阶数 小了。这是一个直接可解结点E,什么也不做。 (2)当i>三时,要做相关联的G和H,G是直接可解 结点,将第s步走过的台阶数j记入take数组,即 take[S]=j;接着做H,H为或结点,有两个分支: 其一是:当ij时,说明经过第s步,已走到楼下, 输出该下楼行走方案,并将方案号加1 其二是:当ij时,说明经过第s步,尚未走到楼下 尚需再试第s+1步的走法,注意这时站在第i-级 台阶上。因此要调用try(i-j,s+1)
7 （1）当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)
for(j=3;]>0;j=j-1) T I<J take]=j; F num= num+l 输出第nm方案下的从第 1步到第s步的走法 try(i-j, S+1);
8 for( j=3; j>0; j=j-1) T i<j F take[s]=j; i==j T F num = num + 1; 输出第 num 方案下的从第 1 步到第 s 步的走法 try(i-j,s+1);
# include∥预编译命令 int take ll; ∥定义全局变量:数组take,方案数nm int num=0 void try(int i, int s) ∥被调用函数 ∥定义整型变量示每步允许走的台阶数, ∥k临时变量 for(=3;j>0;j=j-1)∥循环 ∥循环体开始 if(i<j)∥如果所剩台阶数小于允许走的台阶数j, ∥什么也不做 M/else ●●●●●
9 #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 ……
else ∥以下是=的情况 takes=j;∥记录第s步走个台阶 if(i==j)∥如果已经到了楼下,做下列事情 num= num+l ∥方案数加1 printf("方案%d:";num);∥输出方案数 for(k=1;k<=s;k=k+1)∥输出本方案的每一步 ∥所走的台阶数 printf("%od", take kD; printf("(n) ∥换行 else ∥尚未走到楼下 try(i-1, $+1); ∥再试剩下的台阶(递归调用)
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); // 再试剩下的台阶（递归调用） } }