程序设计基础－张长海－ch12.pptVIP

第十二章 程序开发 自顶向下、逐步求精 结构化程序设计原则 程序风格 穷举和试探 本章小结 §12.1 验证三角形外心定理 ----自顶向下、逐步求精 例12.1 验证三角形外心定理：三角形三条边的垂直平分线交于一点，该点是三角形外接圆的圆心。 解：不失一般性，假设三角形的任意一条边都不平行于任意一个坐标轴。依据解析几何知识，该问题的验证步骤应该是： 读入三点a,b,c的坐标(x1,y1)、(x2,y2)、(x3,y3)； 检验三点是否构成一个三角形； 若三点构成三角形，则验证外心定理 。 例12.2 三个齿轮啮合问题 设有三个齿轮互相衔接，求当三个齿轮的某两对齿互相衔接后到下一次这两对齿再互相衔接，每个齿轮最少各转多少圈。 解:这是求最小公倍数的问题。每个齿轮需转圈数是三个齿轮齿数的最小公倍数除以自己的齿数。设 三个齿轮的齿数分别为:na、nb、nc ； 啮合最小圈数分别为:ma、mb、mc ； 三齿轮齿数的最小公倍数为k3 。 欧几里德辗转相除法 u % v → R1 v % R1 → R2 R1 % R2 → R3 R2 % R3 → R4 … … … … Rn-2 % Rn-1 → Rn=0 Rn-1 % Rn → Rn 为正整数u 、v的最大公因数 §12.3.1 良好的行文格式 程序的行文格式不好直接影响程序的可读性、清晰性和外观。 §12.4 八皇后—穷举与试探 这是一个古老而有趣的游戏。高斯(C.F.Gauss)最早在1850年提出并研究过这个问题，但是没有完全解决。该问题是： 在一个8*8格的国际象棋棋盘上放置八个皇后，使任意两个皇后都不能互相攻击。 按国际象棋规则，两个皇后可以互相攻击。若 在同一行上， 或在同一列上, 或在同一条斜线上（包括左高右低、右高左低） 一、八皇后 穷举法 本方法思路是，按某种顺序枚举出全部排列或组合。每当枚举出一种排列或组合之后，便用给定条件判断该种排列或组合是否符合条件。 若符合条件，则本种排列或组合被选中，可以输出或记录下来。 若不符合条件，则把本种排列或组合舍掉。 八个皇后的排列问题，最简单的方法是八重循环，可以编出如下穷举法程序。 在下述算法中，用到检验函数check与输出函数out。为简单起见，先省略它们的具体实现细节。 二、八皇后 试探法 按照一定的规律，从一满足条件的初始状态出发，逐步生成满足条件的子排列, 不断增加子排列长度。 增加子排列长度过程中，每增加一位, 生成一个子排列后, 便检验它是否满足条件。 不满足条件, 则换一个子排列－即修改当前位置 满足条件, 则延长子排列, 增加子排列长度。 子排列的长度满足要求长度,便找到了一个解。 若要求找一个解即可，这时便可以结束。 若要求找所有解，这时可以输出或记录本解，然后按前述思路，继续修改排列，继续试探，找下个解 在上述试探过程中, 修改当前位置时： 若当前位置上还有没被试探过的元素，则应该取下一个没被试探过的元素进行试探 若当前位置上所有元素都被试探过了，则在当前位置上没办法再修改了 这说明前边的某个位置有问题，放置的元素不对，显然应该向回退一位。 回溯后, 原来的上 一个位置变成了当前位置, 则又变成修改当前位置的问题了。 这时, 同样还应该考虑取下一个没被试探过的元素进行试探, 以及是否所有元素在当前位置上都被试探过了并回溯的问题。 若B[i]使A[1],A[2], ... ,A[m]满足r, 则进入A的下一个位置。 m=m+1 若B[i]不能使A[1],A[2], ... ,A[m]满足r, 则有两种情况: ik ， 若B[i]不能使A[1],A[2], ... ,A[m]满足r, 则有两种情况: ik ，取B中下一个符号继续试探 i=i+1 若i=k 说明在当前位置上所有符号都已经被试探过 若i=k 说明在当前位置上所有符号都已经被试探过 应该回溯到上一个位置, 作 m=m-1 后继续试探 直到找到解、m=0结束 三、八皇后 穷举法的递归实现 用穷举法实现八皇后问题, 可以抽象的描述为：在数组A的8个位置上分别排列一个1到8的整数。设想, 如果有一个函数 queen(r) 能够完成 “在数组A后部的r个位置（从第8-r+1到8）上, 分别排列一个1到8的整数”。 则八皇后问题便是 queen(8) “在数组A后部的r个