计算机程序设计基础——第八讲

《计算机程序设计基础——第八讲》由会员分享，可在线阅读，更多相关《计算机程序设计基础——第八讲（20页珍藏版）》请在装配图网上搜索。

1、会计学1计算机程序设计基础计算机程序设计基础第八讲第八讲2从楼上走到楼下共有h个台阶，每一步有三种走法 走一个台阶； 走二个台阶； 走三个台阶。问可走出多少种方案，希望用递归思想来编程。第1页/共20页3定义： Try(i,s)站在第i级台阶上往下试走第s步的过程 j=1,2,3 在每一步可以试着走的台阶数 takes 存储第s步走过的台阶数 ij 说明站在第i级台阶上可试走j个台阶为一步 i=j 说明这一步走完后已到了楼下，这时一条下楼方案已试成，即可输出这一方案了第2页/共20页4思路：1、用枚举的方法，试着一步一步地走，从高到低，让i先取h值从楼上走到楼下，每走一步i的值会减去每一步所走

2、的台阶数j，即i=h（初值），以后i=i-j，(j=1,2,3)，当i=0时，说明已走到楼下。2、枚举时，每一步都要试j或者是为1，或是为2，或是为3。这时可用for循环结构。3、每一步走法都用相同的策略，故可以用递归算法。第3页/共20页5见图输出输出A try(i,s)i=jtakes=ji=jij第4页/共20页6在上图中，A结点是被递归调用的结点，形式参数为i,s，A结点为一个与结点，进入B结点时的三个参数为i,s,j=3；进入C结点的参数为i,s,j=2；进入D结点的参数为i,s,j=1。Lp是三个结点都可用的循环体Lp。Lp是一个分支结构的或结点。第5页/共20页7（1）当i=j时

3、，要做相关联的G和H，G是直接可解结点，将第s步走过的台阶数j记入take数组，即takes=j；接着做H，H为或结点，有两个分支：其一是：当i=j时，说明经过第s步，已走到楼下，输出该下楼行走方案，并将方案号加1；其二是：当ij时，说明经过第s步，尚未走到楼下，尚需再试第s+1步的走法，注意这时站在第i-j级台阶上。因此要调用try(i-j,s+1)。第6页/共20页8 for( j=3; j0; j=j-1) T F ij takes=j; i=j T F num = num + 1; 输输出出第第num方方案案下下的的从从第第1 步步到到第第s 步步的的走走法法 try(i-j,s+1)

4、; 第7页/共20页9#include / 预编译命令int take11; / 定义全局变量：数组take，方案数numint num = 0;void try(int i, int s)/ 被调用函数int j,k;/ 定义整型变量j表示每步允许走的台阶数, / k临时变量 for (j = 3; j 0; j = j - 1)/ 循环/ 循环体开始if (i =j的情况takes = j;/ 记录第s步走j个台阶if (i=j) / 如果已经到了楼下，做下列事情num = num + 1;/ 方案数加1printf(方案%d : ,num);/ 输出方案数for (k=1; k=s; k

5、=k+1) / 输出本方案的每一步 / 所走的台阶数printf(%d ,takek);printf(n);/ 换行else/ 尚未走到楼下try(i-j, s+1);/ 再试剩下的台阶（递归调用）第9页/共20页11/ 循环体结束/ 函数体结束void main()/ 主函数int h;/ 定义整型变量h是楼梯的台阶数printf(“请输入楼梯的台阶数：); / 提示信息scanf(%d,&h);/ 输入楼梯的台阶数 try(h,1);/ 调用函数try(h,1)printf(总方案数：%dn,num);/ 输出总方案数第10页/共20页121 13 3 2 21 11 13 32 21 1

6、2 22 21 11 11 11 14 4第11页/共20页13八皇后问题第12页/共20页14在88的棋盘上，放置8个皇后（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：（1）不在棋盘的同一行；（2）不在棋盘的同一列；（3）不在棋盘的同一对角线上。因此可以推论出，棋盘共有8行，每行有且仅有一个皇后，故至多有8个皇后。这8个皇后每个应该放在哪一列上是解该题的任务。我们还是用试探的方法“向前走，碰壁回头”的策略。这就是“回溯法”的解题思路。第13页/共20页151、定义try(i)试探放第i行上的皇后。2、讨论将第i行上的皇后放在j列位置上的安全性。我们可以逐行地放每一个皇后

7、，因此，在做这一步时，假定第i行上还没有皇后，不会在行上遭到其它皇后的攻击。只考虑来自列和对角线的攻击。我们定义q(i)=j表示第i行上的皇后放在第j列，一旦这样做了，就要考虑第i个皇后所在的列不安全了，这时让Cj=false，同时，要考虑通过(i,j)位置的两条对角线也不安全了。分析看出从左上到右下的对角线上的每个位置都有i-j=常数的特点；从左下到右上的对角线上的每个位置都有i+j=常数的特点。比如下图的两条对角线上的点，一条有i-j=-1，一条有i+j=7的特点。第14页/共20页16 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8第15页/共20页17利用这个特点，我们

8、可以令Li-j = false;Ri+j = false;来表示在(i,j)位置放皇后之后，通过该位置的两条对角线上不安全了。这样我们得出了在(i,j)位置放皇后的安全条件为nq=Cj&Li-j&Ri+j为了判断安全条件，在程序中要用到三个数组（1）Cj为布尔型的，j=1,2,8，初始化时全部置为true；（2）Lk为布尔型的，k=i-j,k=-7,-6,7，初始化时全部置为true；（3）Rm为布尔型的，m=i+j,m=2,3,16，初始化时全部置为true；第16页/共20页183、从思路上，在放第i个皇后时（当然在第i行），选第j列，当nq为true时，就可将皇后放在(i,j)位置，这时

9、做如下3件事（1）放皇后qi=j，同时让第j列和过(i,j)位置的两条对角线变为不安全。即让Cj=false;Li-j=false;Ri+j=false;（2）之后查一下i是否为8，如果为8，则表明已经放完8个皇后，这时让方案数Num加1，输出该方案下8个皇后在棋盘上的位置。否则，未到8个，还要让皇后数i加1再试着放，这时还要递归调用tri(i+1)。（3）是为了寻找不同方案用的。当着一个方案输出之后，要回溯，将先前放的皇后从棋盘上拿起来，看看还有没有可能换一处放置。这时要将被拿起来的皇后的所在位置的第j列，和两条对角线恢复为安全的。我们用与或图来描述8皇后问题的解题思路。第17页/共20页19try(i+1)try(i+1)A try(i)不安全不安全8j=12LpLpLpNum=Num+1;输出一个棋局输出一个棋局什么也不做什么也不做安全安全i=8i8Cj=true;Li-j=true;Ri+j=true;qi=j;Cj=false;Li-j=false;Ri+j=false;第18页/共20页20结 束第19页/共20页