《C++编程递归-[下楼-跳马-分书].ppt》由会员分享，可在线阅读，更多相关《C++编程递归-[下楼-跳马-分书].ppt（39页珍藏版）》请在金锄头文库上搜索。
1、1,第九章 递归思想与相应算法,2,9.2 递 归 算 法 举 例 下楼问题,3,任务：从楼上走到楼下共有 h 个台阶，每一步有三种走法 走一个台阶； 走二个台阶； 走三个台阶。问：一共可以走出多少种方案？即共要多少步？每一步走几级台阶？ 希望用递归思想来编程。,4,5,思路： 1、用枚举的方法，每一步都要试不同的步数j。j 或者是为 1，或是为 2，或是为 3。这可用 for 循环结构来实现。 2、试着一步一步地走，从高到低，让 变量i 先取 h 值（即台阶数）。从楼上走到楼下，每走一步 i 的值会减去每一步所走的台阶数 j。开始时，i = h（初值），以后 i = i-j，( j=1, 2
2、, 3 )。当 i = 0 时，剩余台阶数为0，这说明已走到楼下。 3、每一步走法策略都相同，故可以用递归算法。,6,定义： Try( i, s )站在第 i 级台阶上往下试走第s步的过程 j = 1, 2, 3 在每一步可以试着走的台阶数j i 说明第 i 级台阶已比要走的 j 级台阶小，j 不可取，什么也不做j j时，说明经过第 s 步，尚未走到楼下，尚需再试第 s+1 步的走法，注意这时站在第 i-j 级台阶上。因此要调用 Try( i j , s +1 )。,take s 存储第 s 步走过的台阶数,10,take s 存储第 s 步走过的台阶数,11,/ * / * 程 序：6_8.
3、cpp * / * 作 者：wuwh * / * 编制时间：2002年11月04日 * / * 主要功能：下楼问题 * /*#include / cout using namespace std;/ 定义全局变量：数组take，方案数num int take99; int num = 0;,12,void Try(int i, int s) / 还有i级台阶，从第s步开始 for (int j=3; j0; j-) if (i = j) takes = j; / 记录第s步走j个台阶 if (i=j) / 如果已经到了楼下 num+; / 则 方案数加1 cout =j)_ / _FOR_J_
4、 / 函数体结束,13,int main( ) int h = 0; / h 是楼梯的台阶数 cout h; / 输入楼梯的台阶数 / 从第h级，开始下第一步Try(h,1); / 输出总方案数cout “总方案数：“ num endl;return 0; ,14,思考题： 为什么take数组和num变量需要设成全局的？ 它们能不能设成函数Try内的局部变量？ 为什么？,15,9.2 递 归 算 法 举 例 跳马问题,16,跳 马 问 题：在半张中国象棋的棋盘上，一只马从左下角跳到右上角，只允许往右跳，不允许往左跳，问能有多少种跳步方案。,17,棋盘数字化，使之“可计算”,18,0,0,1,1
5、,2,2,3,3,0,1,2,3,从某点开始，向右跳马的可能性,跳马操作数字化，使之“可计算”,19,/* /* 程序名：cchess.cpp * /* 作 者：wuwh * /* 时 间：2002年11月11日 * /* 功 能：跳马问题 * /*#include / cout using namespace std;const int TARGET_X = 8; / 整型常量 const int TARGET_Y = 4; const int MAXSTEP = 9; / 含起点，最多九步 int dx = 1, 2, 2, 1 ; int dy = 2, 1, -1, -2 ; int
6、Num; int pathMAXSTEP2;,20,void jump(int x, int y, int step) for (int k=0; k=0) ,21,bool t4 = (x1=TARGET_X) /跳下一步 / _if(t1 & t2)_ / _for_k_ ,22,int main() / 主函数 Num = 0; / 方案号置0 path00 = 0; path01 = 0; / 棋盘左下角/ 从(0,0)出发，跳第一步jump(0,0,1); / 输出总方案数 cout “总方案数：“ Num endl;return 0; ,23,带回溯的递归程序的 设计与实现 ,24
7、,9.2 递 归 算 法 举 例 分书问题,25,任务描述：有编号分别为 0，1，2，3，4 的五本书，准备分给 A, B, C, D, E 五个人，每个人阅读兴趣用一个二维数组加以描述：,26,希望你写一个程序，输出所有分书方案，让人人皆大欢喜。假定 5 个人对 5 本书的阅读兴趣如下表：,0 1 2 3 4 A B C D E,人,书,27,1、定义一个整型的二维数组，将表中的阅读喜好用初始化方法赋给这个二维数组。可定义int like55 = 0, 0, 1, 1, 0, 1, 1, 0, 0, 1,0, 1, 1, 0, 1, 0, 0, 0, 1, 0,0, 1, 0, 0, 1 ;
8、2、定义一个整型一维数组book5用来记录书是否已被选用。用下标作为五本书的标号，被选过元素值为1，未被选过元素值为0，初始化皆置0。int book5 = 0, 0, 0, 0, 0 ;,解题思路：,28,3、画出思路图 定义 Try( i )试着给第 i 人分书 ( i=0, 1, 4 ),29,30,说明： （1）试着给第 i 个人分书，先试分 0 号书，再分 1 号书，分 2 号书，因此有一个与结点，让 j 表示书 j = 0, 1, 2, 3 , 4 。 （2）LP 为循环结构的循环体。 （3）条件 C 是由两部分“与”起来的。“第 i 个人喜欢 j 书，且 j 书尚未被分走”。满足
9、这个条件是第 i 人能够得到 j 书的条件。 （4）如果不满足 C 条件，则什么也不做，这是直接可解结点。,31,（5）满足C条件，做三件事。sh1第一件事：将 j书分给 i。用一个数组 take i =j，记住书 j 给了 i ，同时记录j书已被选用，book j = 1。,32,sh2第二件事：查看 i 是否为 4。如果不为 4，表示尚未将所有 5 个人所要的书分完，这时应递归再试下一人，即Try( i+1 )。如果等于4，则应先使方案数加一，然后输出第 n 个方案下的每个人所得之书。,33,sh3第三件事：回溯。让第 i 人退回 j 书，恢复 j 书尚未被选的标志，即 book j =
10、0。这是在已输出第 n 个方案之后，去寻找下一个分书方案所必需的。（6）在有了上述的与或图之后，我们很容易写出一个程序框图。先看被调用函数 Try( i ) 的框图。,34,sh3：回溯,35,/ * / * 程 序：assign_book.cpp * / * 作 者：wuwh * / * 编制时间：2002年10月28日 * / * 主要功能：分书问题 * / * #include / cout using namespace std; int take5, n; /整型变量 int like55 = 0,0,1,1,0, 1,1,0,0,1, 0,1,1,0,1, 0,0,0,1,0, 0
11、,1,0,0,1 ; / 各人对书的喜好 int book5=0,0,0,0,0; /整型变量,定义数组，初始化,下面讨论主程序应该做的事情 1、将分书方案号预置0 2、从第0号人（A）开始试分书，调用Try(0),36,void Try(int i) for (int j=0; j 0) / 记录j书已分,SH1,分书条件C,37,if (i = 4) / 如果i=4,输出分书方案n+; / 输出分书方案cout “第“ n “个方案n“;for (int k=0; k=4; k+) cout takek “号书分给 “; cout char(A+k) endl; cout endl; else Try(i+1); / 如i!=4, 继续给下一人分书bookj = 0; / 回溯“退还”编号为j的书 / _if_ / _for_j_ ,SH2,SH3,38,int main() /主函数 /主函数开始 n=0; /分书方案号预置0/ 从第0个人（A）开始分书Try(0); return 0; /主函数结束,
