程序开发和结构化程序设计.ppt

《程序开发和结构化程序设计.ppt》由会员分享，可在线阅读，更多相关《程序开发和结构化程序设计.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章第九章 程序开发和结构化程序设计程序开发和结构化程序设计n n良好的行文格式良好的行文格式n n自顶向下逐步求精的程序设计技术自顶向下逐步求精的程序设计技术n n受限排列组合受限排列组合穷举法与试探法穷举法与试探法n n本章小结本章小结n n作业作业良好的行文格式良好的行文格式n n程序的行文格式不好直接影响程序的可读程序的行文格式不好直接影响程序的可读性、清晰性和外观。性、清晰性和外观。/*A*/#include int i;main()i=25+38;printf(“25+38=%d”,i);/*B*/#include int i;main()i=25+38;printf(“25+3

2、8=%d”,i );/*C*/#include int i;/*声明整型变量声明整型变量i*/int main(void)/*主函数主函数*/i=25+38;/*求和运算求和运算*/printf(“25+38=%d”,i);/*打印打印*/if(b)S1 else S2 switch(expr)case a1:S1 case a2:S2 .case an:sn /*switch*/图图1 函数定义函数定义 图图2 IF语句语句 图图3 SWITCH语句语句 int main(vido)DS DS ./*main*/do S while(b)for(expr1;expr2;expe3)S/*fo

3、r*/while(b)S /*while*/图图4 WHILE语句语句 图图5 FOR语句语句 图图6 DO语句语句用合适的助记名来命名标识符用合适的助记名来命名标识符注释注释自顶向下逐步求精的程序设计技术自顶向下逐步求精的程序设计技术n n自顶向下、逐步求精自顶向下、逐步求精若想让计算机解题必须用清晰而无两义性的若想让计算机解题必须用清晰而无两义性的方式给它提供算法。要求：方式给它提供算法。要求：找出一个算法，它能提供所解问题的从输入到输找出一个算法，它能提供所解问题的从输入到输找出一个算法，它能提供所解问题的从输入到输找出一个算法，它能提供所解问题的从输入到输出所需的映象。出所需的映象。出

4、所需的映象。出所需的映象。选择一种程序语言写出程序，用计算机能接受的选择一种程序语言写出程序，用计算机能接受的选择一种程序语言写出程序，用计算机能接受的选择一种程序语言写出程序，用计算机能接受的方式表述算法。方式表述算法。方式表述算法。方式表述算法。关键是如何找出算法。因为写出程序，只是关键是如何找出算法。因为写出程序，只是表述算法，应该没有困难。表述算法，应该没有困难。求解一个问题求解一个问题粗略的解决方案粗略的解决方案细细 化化第一步子问题第一步子问题第二步子问题第二步子问题第第n步子问题步子问题.前处理前处理 结束条件结束条件后处理后处理进进展展一一步步前处理前处理后处理后处理条条件件处

5、理处理1处理处理2处理处理n.条件条件条件条件 条件条件前处理前处理后处理后处理递归递归条件条件递归递归顺序顺序 连接连接循环循环 分支分支 选择选择 递归递归求精实例求精实例n n测定字母偶的出现频率测定字母偶的出现频率n n三个齿轮啮合问题三个齿轮啮合问题n n验证三角形外心定理验证三角形外心定理编程序，测定字母偶的出现频率编程序，测定字母偶的出现频率测定小写字符串中相邻字母偶出现频率。测定小写字符串中相邻字母偶出现频率。测定小写字符串中相邻字母偶出现频率。测定小写字符串中相邻字母偶出现频率。例如，针对例如，针对例如，针对例如，针对the catthe cat对对对对th th、he he

6、、ca ca、atat计数。设有说明：计数。设有说明：计数。设有说明：计数。设有说明：int conmat2626;int conmat2626;字母偶字母偶字母偶字母偶 he he 的出现次数存入下标变量的出现次数存入下标变量的出现次数存入下标变量的出现次数存入下标变量conmath-ae-aconmath-ae-a首先把该问题分解成如下几步：首先把该问题分解成如下几步：1）初始化计数器数组）初始化计数器数组conmat；2）统计每个字母偶的出现频率；）统计每个字母偶的出现频率；3）输出统计结果。）输出统计结果。initial 初始化初始化statistical 统计统计out 输出输出求精

7、上述求精上述PAD中的每一个步骤：中的每一个步骤：初始化数组初始化数组conmat,显然应该一行一行的初始化；显然应该一行一行的初始化；对于每行又应该一个元素一个元素的初始化。对于每行又应该一个元素一个元素的初始化。初始化初始化第第c1行行 initial 初始化初始化 for(i=0;i26;i+)结束结束deffor(j=0;j26;j+)conmatij=0考虑统计部分：考虑统计部分：假设被统计的字符串是从终端输入的，则显然我们假设被统计的字符串是从终端输入的，则显然我们应该把该字符串全部读入，并在读入的过程中边读边应该把该字符串全部读入，并在读入的过程中边读边统计。用下图表示。统计。用

8、下图表示。读读(prevchar)statisticalwhile(!EOF)统计统计一次一次结结束束def读读(thischar)再考虑具体统计算法，为统计字母偶的出现频率，显然再考虑具体统计算法，为统计字母偶的出现频率，显然在读入字符串的过程中应该始终保存两个字符在读入字符串的过程中应该始终保存两个字符 prevchar、thischar，并且当该两个字符都是字母时，相应计数，并且当该两个字符都是字母时，相应计数单元加单元加1；最后在读入下一个字符之前还应该把保存的两；最后在读入下一个字符之前还应该把保存的两个字符向前串。个字符向前串。统计统计一次一次conmat prevchar thi

9、schar +结结束束 thischar,prevchar 都是字母都是字母prevchar=thischar最后考虑输出部分最后考虑输出部分,我们把结果输出成两个我们把结果输出成两个 2613 的的表，每个表元素是相应字母偶的出现次数：表，每个表元素是相应字母偶的出现次数：*a b c d e .mab .z*n o p q r .zab .z outone(a,m)输输出出a.m部分部分outone(n,z)输输出出n.z部分部分out 输输出出结结束束def打印一个表（第一个表），显然应该先打印表头再打印下边各行打印一个表（第一个表），显然应该先打印表头再打印下边各行 打印表头打印表头打

10、印表体打印表体outone结束结束beginch ,endch打印表打印表头头可以求精成先可以求精成先输输出一个出一个“*”；再；再顺顺次次输输出各个字符。出各个字符。顺顺次次输输出各个字符是一个循出各个字符是一个循环环。打印表头打印表头打印表体打印表体outone结束结束beginch ,endch输输出出(*)输输出出(n)顺次输出各个字符顺次输出各个字符 for(c1=beginch;c1=endch;c1+)输输出出(c1)打印表体应该一行一行的打印，打印表体应该一行一行的打印，每行应该先打印行头，再打印本行各个元素；每行应该先打印行头，再打印本行各个元素；打印本行各个元素，应该一个元

11、素一个元素的打印，是一个循环打印本行各个元素，应该一个元素一个元素的打印，是一个循环打印表体打印表体outone结束结束beginch ,endch输输出出(*)输输出出(n)for(c1=beginch;c1=endch;c1+)输输出出(c1)for(c1=a;c1=z;c1+)输出一行输出一行输出输出(c1)输出输出(n)输出本行各个元素输出本行各个元素 for(c2=beginch;c2=endch;c2+)输出输出conmatc1c2三个齿轮啮合问题三个齿轮啮合问题设有三个齿轮互相衔接，求当三个齿轮的某两对齿设有三个齿轮互相衔接，求当三个齿轮的某两对齿设有三个齿轮互相衔接，求当三个齿

12、轮的某两对齿设有三个齿轮互相衔接，求当三个齿轮的某两对齿互相衔接后到下一次这两对齿再互相衔接，每个齿互相衔接后到下一次这两对齿再互相衔接，每个齿互相衔接后到下一次这两对齿再互相衔接，每个齿互相衔接后到下一次这两对齿再互相衔接，每个齿轮最少各转多少圈。轮最少各转多少圈。轮最少各转多少圈。轮最少各转多少圈。解解解解:这是求最小公倍数的问题。每个齿轮需转圈数这是求最小公倍数的问题。每个齿轮需转圈数这是求最小公倍数的问题。每个齿轮需转圈数这是求最小公倍数的问题。每个齿轮需转圈数是三个齿轮齿数的最小公倍数除以自己的齿数。设是三个齿轮齿数的最小公倍数除以自己的齿数。设是三个齿轮齿数的最小公倍数除以自己的齿

13、数。设是三个齿轮齿数的最小公倍数除以自己的齿数。设三个齿轮的齿数分别为三个齿轮的齿数分别为三个齿轮的齿数分别为三个齿轮的齿数分别为:na:na、nbnb、nc nc；啮合最小圈数分别为啮合最小圈数分别为啮合最小圈数分别为啮合最小圈数分别为:ma:ma、mbmb、mc mc；三齿轮齿数的最小公倍数为三齿轮齿数的最小公倍数为三齿轮齿数的最小公倍数为三齿轮齿数的最小公倍数为k3 k3。计算步骤表示为：计算步骤表示为：开始开始读入三齿轮齿数读入三齿轮齿数求三齿数的最小公倍数求三齿数的最小公倍数 k3分别计算啮合的最小圈数分别计算啮合的最小圈数输出结果输出结果结束结束读入三齿轮齿数和输出结果，分别只是一

14、次调用读或写读入三齿轮齿数和输出结果，分别只是一次调用读或写函数，不必求精。函数，不必求精。求精计算三齿数的最小公倍数求精计算三齿数的最小公倍数k3。可以把该问题分解成。可以把该问题分解成 先求两个齿数先求两个齿数na与与nb的最小公倍数的最小公倍数k2，然后再求然后再求k2与第三个齿数与第三个齿数 nc 的最小公倍数的最小公倍数k3，k3即为即为na、nb、nc三个齿轮齿数的最小公倍数。三个齿轮齿数的最小公倍数。设已经有求两个数的最小公倍数的函数设已经有求两个数的最小公倍数的函数 int lowestcm(int x,int y)则该求精过程可表示成则该求精过程可表示成。求三齿数的求三齿数的

15、最小公倍数最小公倍数 k3=lowestcm(lowestcm(na,nb),nc)结束结束求精求两个数的最小公倍数的函求精求两个数的最小公倍数的函lowestcm。x、y的最小公倍数是的最小公倍数是x、y 的积除以的积除以x、y 的最的最大公约数。设已经有求两个数的最大公约数的函数大公约数。设已经有求两个数的最大公约数的函数 int gcd(int x,int y)则该求精过程可表示成：则该求精过程可表示成：int lowestcm(int x,int y)return x*y/gcd(x,y)结束结束def采用展采用展转转相除法求两个数的最大公相除法求两个数的最大公约约数，函数数，函数in

16、t gcd(int x,int y)定定义义如下如下 函数函数gcd是一个递归函数，先采用分支求精过程、再采用是一个递归函数，先采用分支求精过程、再采用递归求精过程，可以求精成下图递归求精过程，可以求精成下图int gcd(int x,int y)结束结束y0return gcd(y,x%y)return x最后，分别计算啮合的最小圈数可以被求精成下图最后，分别计算啮合的最小圈数可以被求精成下图。开始开始ma=na/k3mb=nb/k3mc=nc/k3结束结束验证三角形外心定理验证三角形外心定理n n三角形三条边的垂直平分线交于一点，该点是三角形三条边的垂直平分线交于一点，该点是三角形外接圆的

17、圆心。三角形外接圆的圆心。解：不失一般性，假设三角形的任意一条边都解：不失一般性，假设三角形的任意一条边都不平行于任意一个坐标轴。依据平面几何知识，不平行于任意一个坐标轴。依据平面几何知识，该问题的验证步骤应该是：该问题的验证步骤应该是：读入三点读入三点读入三点读入三点a,b,ca,b,c的坐标的坐标的坐标的坐标(x1,y1)(x1,y1)、(x2,y2)(x2,y2)、(x3,y3)(x3,y3)；检验三点是否构成一个三角形；检验三点是否构成一个三角形；检验三点是否构成一个三角形；检验三点是否构成一个三角形；若三点构成三角形，则验证外心定理若三点构成三角形，则验证外心定理若三点构成三角形，则

18、验证外心定理若三点构成三角形，则验证外心定理 。开始开始验证外心定理验证外心定理结束结束是三角形是三角形读入三点读入三点a,b,c坐标坐标读入三点坐标只是一个读语句，不必求精读入三点坐标只是一个读语句，不必求精，下边求精，下边求精检验是否三角形和验证外心定理。检验是否三角形和验证外心定理。检验三点是否构成三角形使用一个检验三点是否构成三角形使用一个bool型函数型函数isTriange，可以求精成：，可以求精成：求两点求两点p1,p2确定的直线方程确定的直线方程L12；判断若判断若p3在在L12上，上，则则 isTriange 为为false，否则否则isTriange为为true 。求求p1

19、,p2两点直线方程两点直线方程L12：y=a*x+bisTriange结束结束w在在L12上上return falsereturn true求两点间直线方程可以写一个函数求两点间直线方程可以写一个函数 line(x1,y1,x2,y2,*a,*b)并求精成下图并求精成下图。line*b=y1-a*x1结束结束*a=(y2-y1)/(x2-x1)x1,y1,x2,y2：两点坐标：两点坐标*a,*b：直线方程系数：直线方程系数 验证外心定理可以如下进行：验证外心定理可以如下进行：求每条边的垂直平分线；求每条边的垂直平分线；验证该三条直线是否交于一点；验证该三条直线是否交于一点；若交于一点，若交于一

20、点，则验证该点到三角形各顶点距离是否相等则验证该点到三角形各顶点距离是否相等否则否则 错误命题。错误命题。验证验证外心定理外心定理求每条求每条边边的垂直平分的垂直平分线线方程方程结结束束三条直三条直线线交于一点交于一点印印 O.K该该点到三角形点到三角形各各顶顶点距离相等点距离相等印印 false求每条边的垂直平分线方程可以写一个求一条线段的垂直求每条边的垂直平分线方程可以写一个求一条线段的垂直平分线方程的函数，然后分别三次调用该函数平分线方程的函数，然后分别三次调用该函数。每条边的垂直每条边的垂直平分线方程平分线方程结束结束求边求边L12的垂直平分线：的垂直平分线：vline(ax,ay,b

21、x,by,&a_a,&a_b)求边求边L23的垂直平分线：的垂直平分线：vline(bx,by,cx,cy,&b_a,&b_b)求边求边L13的垂直平分线：的垂直平分线：vline(cx,cy,ax,ay,&c_a,&c_b)求一条边的垂直平分线方程可以先调用前述函数求一条边的垂直平分线方程可以先调用前述函数 line，求该边的直线方程，求该边的直线方程;再求该边的中点再求该边的中点,然后求过该中然后求过该中点的与该边垂直的直线方程，得下图点的与该边垂直的直线方程，得下图 vline直线方程直线方程:line(x1,y1,x2,y2,&ta,&tb)结束结束中点中点:x=(x1+x2)/2;y

22、=(y1+y2)/2垂直平分线方程：垂直平分线方程：*a=-1/ta;*b=y-(*ta)*xx1,y1,x2,y2：两点：两点*a,*b：垂线方程：垂线方程验证该三条直线是否交于一点编成一个函数验证该三条直线是否交于一点编成一个函数isOnePoint，可以，可以先求两条直线的交点，先求两条直线的交点，然后再判断第三条直线是否过该点。然后再判断第三条直线是否过该点。三条直线交于一点三条直线交于一点结束结束求求L12与与L23交点交点:*x=(b1-b2)/(a1-a2);*y=a1*(*x)+b1return falsereturn truefabs(a3*(*x)+b3-y)eps设有一个

23、函数设有一个函数 distance(x1,y1,x2,y2)可以计算两点间距离，验证三条垂直平分线的交点到三可以计算两点间距离，验证三条垂直平分线的交点到三角形各顶点距离是否相等，是一个布尔表达式。角形各顶点距离是否相等，是一个布尔表达式。distance结束结束 return sqrt(x2-x1)2+(y2-y1)2)x1,y1,x2,y2：两点坐标：两点坐标受限排列组合受限排列组合穷举法与试探法穷举法与试探法有这样一类问题，从若干元素的所有排列有这样一类问题，从若干元素的所有排列(或组合或组合)中选取符合某种条件的一些排列中选取符合某种条件的一些排列(或组合或组合)。n n八皇后问题八皇

24、后问题n nDebruijn Debruijn 问题问题八皇后问题八皇后问题 这是一个古老而有趣的游戏。高斯这是一个古老而有趣的游戏。高斯这是一个古老而有趣的游戏。高斯这是一个古老而有趣的游戏。高斯()()最早在最早在最早在最早在18501850年提年提年提年提出并研究过这个问题，但是没有完全解决。该问题是：出并研究过这个问题，但是没有完全解决。该问题是：出并研究过这个问题，但是没有完全解决。该问题是：出并研究过这个问题，但是没有完全解决。该问题是：在一个在一个在一个在一个8*88*8格的国际象棋棋盘上放置八个皇后，使任意格的国际象棋棋盘上放置八个皇后，使任意格的国际象棋棋盘上放置八个皇后，使

25、任意格的国际象棋棋盘上放置八个皇后，使任意两个皇后都不能互相攻击。两个皇后都不能互相攻击。两个皇后都不能互相攻击。两个皇后都不能互相攻击。按国际象棋规则，两个皇后可以互相攻击。若按国际象棋规则，两个皇后可以互相攻击。若按国际象棋规则，两个皇后可以互相攻击。若按国际象棋规则，两个皇后可以互相攻击。若l在同一行上，在同一行上，在同一行上，在同一行上，l或在同一列上或在同一列上或在同一列上或在同一列上,l或在同一条斜线上（包括左高右低、右高左低）或在同一条斜线上（包括左高右低、右高左低）或在同一条斜线上（包括左高右低、右高左低）或在同一条斜线上（包括左高右低、右高左低）*如图放置的八个皇后便不能互相

26、攻击。编程序如图放置的八个皇后便不能互相攻击。编程序,求出所有符合要求求出所有符合要求的布局。的布局。共有共有92种满足条件的布局，若除去对称的等类同布局种满足条件的布局，若除去对称的等类同布局,完全不同者完全不同者有有12种。这里不考虑剔除类同布局，求出全部种。这里不考虑剔除类同布局，求出全部92种布局。种布局。解这类问题有两条途径解这类问题有两条途径:1.穷举法穷举法;2.试探法。试探法。下边以八皇后问题为例，分别介绍这两种方法。下边以八皇后问题为例，分别介绍这两种方法。在具体介绍这两种方法之前，先考虑八皇后问题的表在具体介绍这两种方法之前，先考虑八皇后问题的表示方法。用一个一维数组表示棋

27、盘。示方法。用一个一维数组表示棋盘。Ai表示棋盘的表示棋盘的第第i列，若列，若Ai中存放有数中存放有数k表示第表示第i列中第列中第k行上放置了行上放置了皇后。例皇后。例:A3=6表示在棋盘的第表示在棋盘的第3列第列第6行上放置一个皇后。行上放置一个皇后。A0是根是根据下边算法的需要据下边算法的需要,多设的一个元素。多设的一个元素。0 01 12 23 34 45 56 67 78 8 A:A:八皇后八皇后 穷举法穷举法 本方法思路是，按某种顺序枚举出全部排列或组合。本方法思路是，按某种顺序枚举出全部排列或组合。本方法思路是，按某种顺序枚举出全部排列或组合。本方法思路是，按某种顺序枚举出全部排列

28、或组合。每当枚举出一种排列或组合之后，便用给定条件判断每当枚举出一种排列或组合之后，便用给定条件判断每当枚举出一种排列或组合之后，便用给定条件判断每当枚举出一种排列或组合之后，便用给定条件判断该种排列或组合是否符合条件。该种排列或组合是否符合条件。该种排列或组合是否符合条件。该种排列或组合是否符合条件。l若符合条件，则本种排列或组合被选中，可以输出若符合条件，则本种排列或组合被选中，可以输出若符合条件，则本种排列或组合被选中，可以输出若符合条件，则本种排列或组合被选中，可以输出或记录下来。或记录下来。或记录下来。或记录下来。l若不符合条件，则把本种排列或组合舍掉。若不符合条件，则把本种排列或组

29、合舍掉。若不符合条件，则把本种排列或组合舍掉。若不符合条件，则把本种排列或组合舍掉。八个皇后的排列问题，最简单的方法是八重循环，可八个皇后的排列问题，最简单的方法是八重循环，可八个皇后的排列问题，最简单的方法是八重循环，可八个皇后的排列问题，最简单的方法是八重循环，可以编出如下穷举法程序。以编出如下穷举法程序。以编出如下穷举法程序。以编出如下穷举法程序。在下述算法中，用到检验函数在下述算法中，用到检验函数在下述算法中，用到检验函数在下述算法中，用到检验函数checkcheck与输出函数与输出函数与输出函数与输出函数outout。为简单起见，先省略它们的具体实现细节。为简单起见，先省略它们的具体

30、实现细节。为简单起见，先省略它们的具体实现细节。为简单起见，先省略它们的具体实现细节。int main(void)int main(void)int a9 int a9，i1,i2,i3,i4,i5,i6,i7,i8 ;i1,i2,i3,i4,i5,i6,i7,i8 ;for(i1=1;i1=8;i1+)for(i1=1;i1=8;i1+)for(i2=1;i2=8;i2+)for(i2=1;i2=8;i2+)for(i3=1;i3=8;i3+)for(i3=1;i3=8;i3+)for(i4=1;i4=8;i4+)for(i4=1;i4=8;i4+)for(i5=1;i5=8;i5+)for

31、(i5=1;i5=8;i5+)for(i6=1;i6=8;i6+)for(i6=1;i6=8;i6+)for(i7=1;i7=8;i7+)for(i7=1;i7=8;i7+)for(i8=1;i8=8;i8+)for(i8=1;i8=8;i8+)a1=i1;a2=i2;a1=i1;a2=i2;a3=i3;a4=i4;a3=i3;a4=i4;a5=i5;a6=i6;a5=i5;a6=i6;a7=i7;a8=i8;a7=i7;a8=i8;if(check()out();if(check()out();八皇后八皇后 试探法试探法n n按规律，从一满足条件的初始状态出发，逐步生成按规律，从一满足条件的

32、初始状态出发，逐步生成按规律，从一满足条件的初始状态出发，逐步生成按规律，从一满足条件的初始状态出发，逐步生成满足条件的子排列满足条件的子排列满足条件的子排列满足条件的子排列,不断增加子排列长度。不断增加子排列长度。不断增加子排列长度。不断增加子排列长度。n n增加子排列长度过程中，每增加一位增加子排列长度过程中，每增加一位增加子排列长度过程中，每增加一位增加子排列长度过程中，每增加一位,生成一个子生成一个子生成一个子生成一个子排列后排列后排列后排列后,便检验它是否满足条件。便检验它是否满足条件。便检验它是否满足条件。便检验它是否满足条件。不满足条件不满足条件不满足条件不满足条件,则换一个子排

33、列即修改当前位置则换一个子排列即修改当前位置则换一个子排列即修改当前位置则换一个子排列即修改当前位置满足条件满足条件满足条件满足条件,则延长子排列则延长子排列则延长子排列则延长子排列,增加子排列长度。增加子排列长度。增加子排列长度。增加子排列长度。n n子排列的长度满足要求长度子排列的长度满足要求长度子排列的长度满足要求长度子排列的长度满足要求长度,便找到了一个解。便找到了一个解。便找到了一个解。便找到了一个解。n n若要求找一个解即可，这时便可以结束。若要求找一个解即可，这时便可以结束。若要求找一个解即可，这时便可以结束。若要求找一个解即可，这时便可以结束。n n若要求找所有解，这时可以输出

34、或记录本解，然后若要求找所有解，这时可以输出或记录本解，然后若要求找所有解，这时可以输出或记录本解，然后若要求找所有解，这时可以输出或记录本解，然后按前述思路，继续修改排列，继续试探，找下个解按前述思路，继续修改排列，继续试探，找下个解按前述思路，继续修改排列，继续试探，找下个解按前述思路，继续修改排列，继续试探，找下个解n n在上述试探过程中在上述试探过程中在上述试探过程中在上述试探过程中,修改当前位置时：修改当前位置时：修改当前位置时：修改当前位置时：若当前位置上还有没被试探过的元素，则应该若当前位置上还有没被试探过的元素，则应该若当前位置上还有没被试探过的元素，则应该若当前位置上还有没被

35、试探过的元素，则应该取下一个没被试探过的元素进行试探取下一个没被试探过的元素进行试探取下一个没被试探过的元素进行试探取下一个没被试探过的元素进行试探若当前位置上所有元素都被试探过了，则在当若当前位置上所有元素都被试探过了，则在当若当前位置上所有元素都被试探过了，则在当若当前位置上所有元素都被试探过了，则在当前位置上没办法再修改了前位置上没办法再修改了前位置上没办法再修改了前位置上没办法再修改了这说明前边的某个位置有问题，放置的元素这说明前边的某个位置有问题，放置的元素这说明前边的某个位置有问题，放置的元素这说明前边的某个位置有问题，放置的元素不对，显然应该向回退一位。不对，显然应该向回退一位。

36、不对，显然应该向回退一位。不对，显然应该向回退一位。回溯后回溯后回溯后回溯后,原来的上原来的上原来的上原来的上 一个位置变成了当前位置一个位置变成了当前位置一个位置变成了当前位置一个位置变成了当前位置,则又变成修改当前位置的问题了。则又变成修改当前位置的问题了。则又变成修改当前位置的问题了。则又变成修改当前位置的问题了。这时这时这时这时,同样还应该考虑取下一个没被试探过同样还应该考虑取下一个没被试探过同样还应该考虑取下一个没被试探过同样还应该考虑取下一个没被试探过的元素进行试探的元素进行试探的元素进行试探的元素进行试探,以及是否所有元素在当前以及是否所有元素在当前以及是否所有元素在当前以及是否

37、所有元素在当前位置上都被试探过了并回溯的问题。位置上都被试探过了并回溯的问题。位置上都被试探过了并回溯的问题。位置上都被试探过了并回溯的问题。如图所示，设要生成一个如图所示，设要生成一个 n 位的串位的串A；在每个位置上可；在每个位置上可选择的符号有选择的符号有 K 个；个；A 应该满足条件应该满足条件 r；m表示当前试表示当前试探位置。试探法的算法描述为：探位置。试探法的算法描述为：1.初始时，从第一个位置开始试探，令初始时，从第一个位置开始试探，令 m=1;2.然后在第然后在第 m 位逐次取可选符号位逐次取可选符号:B1,B2,.,Bk。对某一个。对某一个Bi有两种可能有两种可能:0 01

38、 12 2n n A:A:B:B:1 12 2k kn n若若若若BiBi使使使使A1,A2,.,AmA1,A2,.,Am满足满足满足满足r,r,则进入则进入则进入则进入A A的的的的下一个位置。下一个位置。下一个位置。下一个位置。m=m+1 m=m+10 01 12 2mmm+1m+1n n A:A:B:B:1 12 2k kn n若若若若BiBi不能使不能使不能使不能使A1,A2,.,AmA1,A2,.,Am满足满足满足满足r,r,则有两种情况则有两种情况则有两种情况则有两种情况:ik ik，0 01 12 2mmn n A:A:BiBiB:B:1 1i ii+1i+1k kn n若若若若

39、BiBi不能使不能使不能使不能使A1,A2,.,AmA1,A2,.,Am满足满足满足满足r,r,则有两种情况则有两种情况则有两种情况则有两种情况:ik i 0)while(m 0)if(check(m)if(check(m)if(m=8)if(m=8)out();out();change();change();else else extend();extend();else else change();change();从上例可以看出从上例可以看出,穷举法与试探法的着眼点及主要区别穷举法与试探法的着眼点及主要区别在于在于:穷举法是举出全部可能的格局，对每种格局进行检验穷举法是举出全部可能的格局

40、，对每种格局进行检验,使合格者入选，不合格者淘汰。使合格者入选，不合格者淘汰。试探法是从初始满足条件的格局开始，逐步前进。每试探法是从初始满足条件的格局开始，逐步前进。每前进一步都判断子格局是否合适。前进一步都判断子格局是否合适。若当前子格局合适则进入下一级若当前子格局合适则进入下一级;若当前子格局不合适则选同一级的下一个子格局若当前子格局不合适则选同一级的下一个子格局;但但是若同级子格局已全部试探完毕是若同级子格局已全部试探完毕,则回溯到上一级则回溯到上一级直到当前子格局够长为止。直到当前子格局够长为止。显然穷举法的运算量比试探法要大的多。因为它显然穷举法的运算量比试探法要大的多。因为它要考

41、虑一切情况的排列，而试探法可以在中间丢掉要考虑一切情况的排列，而试探法可以在中间丢掉大量的不合格排列。大量的不合格排列。事实上许多问题的穷举法是不适用的事实上许多问题的穷举法是不适用的,八皇后问八皇后问题穷举法有题穷举法有88种排列，把每一种情况都排出来，并检种排列，把每一种情况都排出来，并检验其是否合格显然是不可能的。验其是否合格显然是不可能的。在上述算法中在上述算法中,不论是穷举法还是试探法，都是不论是穷举法还是试探法，都是用循环迭代的方式给出的解法。循环程序可以用递用循环迭代的方式给出的解法。循环程序可以用递归来表示。归来表示。不论穷举法还是试探法都可以写成递归形式不论穷举法还是试探法都

42、可以写成递归形式:八皇后八皇后 穷举法的递归实现穷举法的递归实现n n用穷举法实现八皇后问题用穷举法实现八皇后问题用穷举法实现八皇后问题用穷举法实现八皇后问题,可以抽象的描述为：可以抽象的描述为：可以抽象的描述为：可以抽象的描述为：在数组在数组在数组在数组A A的的的的8 8个位置上分别排列一个个位置上分别排列一个个位置上分别排列一个个位置上分别排列一个1 1到到到到8 8的整数。的整数。的整数。的整数。设想设想设想设想,如果有一个函数如果有一个函数如果有一个函数如果有一个函数queen(r)queen(r)能够完成能够完成能够完成能够完成 “在数组在数组在数组在数组A A后部的后部的后部的后

43、部的r r个位置（从第个位置（从第个位置（从第个位置（从第8-r+18-r+1到到到到8 8）上）上）上）上,分别排列一个分别排列一个分别排列一个分别排列一个1 1到到到到8 8的整数的整数的整数的整数”。则八皇后问题便是则八皇后问题便是则八皇后问题便是则八皇后问题便是 queen(8)queen(8)n n“在数组在数组在数组在数组A A后部的后部的后部的后部的r r个位置上个位置上个位置上个位置上,分别排列一个分别排列一个分别排列一个分别排列一个1 1到到到到8 8的的的的整数整数整数整数”可以分解成可以分解成可以分解成可以分解成:先在第先在第先在第先在第8-r+18-r+1位上分别排列一

44、个位上分别排列一个位上分别排列一个位上分别排列一个1 1到到到到8 8的整数；的整数；的整数；的整数；然后再在剩余的后部的然后再在剩余的后部的然后再在剩余的后部的然后再在剩余的后部的r-1r-1个位置上分别排列一个个位置上分别排列一个个位置上分别排列一个个位置上分别排列一个1 1到到到到8 8的整数。的整数。的整数。的整数。n n步骤步骤步骤步骤2 2便是对便是对便是对便是对queenqueen的递归调用的递归调用的递归调用的递归调用 queen(r-1)queen(r-1)。n n最后考虑递归出口最后考虑递归出口最后考虑递归出口最后考虑递归出口,显然应该在显然应该在显然应该在显然应该在 r=

45、1r=1 时检验输出并时检验输出并时检验输出并时检验输出并退出递归。退出递归。退出递归。退出递归。n n由此得递归实现八皇后问题的穷举算法及递归程序由此得递归实现八皇后问题的穷举算法及递归程序由此得递归实现八皇后问题的穷举算法及递归程序由此得递归实现八皇后问题的穷举算法及递归程序八皇后穷举法八皇后穷举法结束结束queen(8)queen(r)结束结束for(i=1;i1输出输出检验检验 int A 9 ;int A 9 ;bool check();/*bool check();/*检查某格局是否合格的函数检查某格局是否合格的函数检查某格局是否合格的函数检查某格局是否合格的函数,分程序略分程序略

46、分程序略分程序略*/*/void out();/*void out();/*输出函数输出函数输出函数输出函数,分程序略分程序略分程序略分程序略*/*/void queen(int r)void queen(int r)int i;int i;for(i=1;i=8;i+)for(i=1;i1 r1)queen(r-1);queen(r-1);else if(cheek()else if(cheek()out();out();int main(void)int main(void)queen(8)queen(8)八皇后八皇后 试探法的递归实现试探法的递归实现n n试探方法的思路是，按一定规律，从

47、某一满足条件的初始试探方法的思路是，按一定规律，从某一满足条件的初始试探方法的思路是，按一定规律，从某一满足条件的初始试探方法的思路是，按一定规律，从某一满足条件的初始状态出发，逐步试探生成满足条件的子排列状态出发，逐步试探生成满足条件的子排列状态出发，逐步试探生成满足条件的子排列状态出发，逐步试探生成满足条件的子排列,不断增加子不断增加子不断增加子不断增加子排列长度排列长度排列长度排列长度,直到子排列的长度满足问题的要求长度直到子排列的长度满足问题的要求长度直到子排列的长度满足问题的要求长度直到子排列的长度满足问题的要求长度n n为止为止为止为止,便找到了一个解。设想便找到了一个解。设想便找

48、到了一个解。设想便找到了一个解。设想,如果有一个函数如果有一个函数如果有一个函数如果有一个函数queen(r)queen(r)能够能够能够能够“合理的排列数组合理的排列数组合理的排列数组合理的排列数组A A后部的后部的后部的后部的r r个个个个(从第从第从第从第n-r+1n-r+1到到到到n)n)元素元素元素元素”并保证序列满足给定条件并保证序列满足给定条件并保证序列满足给定条件并保证序列满足给定条件,则八皇后问题便是对则八皇后问题便是对则八皇后问题便是对则八皇后问题便是对queenqueen的的的的调用调用调用调用 queen(8)queen(8)n n“合理的排列数组合理的排列数组合理的排

49、列数组合理的排列数组A A后部的后部的后部的后部的r r个（从第个（从第个（从第个（从第n-r+1n-r+1到到到到n n）元素）元素）元素）元素”可以分可以分可以分可以分解成解成解成解成:首先在第首先在第首先在第首先在第n-r+1n-r+1位上排列一个合格的元素位上排列一个合格的元素位上排列一个合格的元素位上排列一个合格的元素,然后然后然后然后在合理的排列在合理的排列在合理的排列在合理的排列从从从从n-(r-1)+1n-(r-1)+1开始的后部的开始的后部的开始的后部的开始的后部的r-1r-1个元素。个元素。个元素。个元素。n n步骤步骤步骤步骤1“1“在第在第在第在第n-r+1n-r+1位

50、上排列一个合格的元素位上排列一个合格的元素位上排列一个合格的元素位上排列一个合格的元素”，即是把，即是把，即是把，即是把8 8个元个元个元个元素顺次的排列在第素顺次的排列在第素顺次的排列在第素顺次的排列在第n-r+1n-r+1位上位上位上位上,并对每个元素检验是否合格，并对每个元素检验是否合格，并对每个元素检验是否合格，并对每个元素检验是否合格，使合格者入选。使合格者入选。使合格者入选。使合格者入选。n n步骤步骤步骤步骤2“2“合理的排列后部的合理的排列后部的合理的排列后部的合理的排列后部的r-1r-1个元素个元素个元素个元素”显然与显然与显然与显然与“合理的排列后合理的排列后合理的排列后合