C语言程序设计_吉林大学_ch12.ppt

第十二章 程序开发和结构化程序设计 良好的行文格式 自顶向下逐步求精的程序设计技术 受限排列组合——穷举法与试探法 本章小结 作业 良好的行文格式 程序的行文格式不好直接影响程序的可读性、清晰性和外观。 用合适的助记名来命名标识符 自顶向下逐步求精的程序设计技术 自顶向下、逐步求精 若想让计算机解题必须用清晰而无两义性的方式给它提供算法。要求： 找出一个算法，它能提供所解问题的从输入到输出所需的映象。 选择一种程序语言写出程序，用计算机能接受的方式表述算法。 关键是如何找出算法。因为写出程序，只是表述算法，应该没有困难。 求精实例 测定字母偶的出现频率 三个齿轮啮合问题 验证三角形外心定理 编程序，测定字母偶的出现频率 测定小写字符串中相邻字母偶出现频率。例如，针对 the cat 对 th 、he 、ca 、at 计数。设有说明： int conmat[26][26] ; 字母偶 he 的出现次数存入下标变量 conmat[‘h-‘a’][e-’a’] 三个齿轮啮合问题 设有三个齿轮互相衔接，求当三个齿轮的某两对齿互相衔接后到下一次这两对齿再互相衔接，每个齿轮最少各转多少圈。 解:这是求最小公倍数的问题。每个齿轮需转圈数是三个齿轮齿数的最小公倍数除以自己的齿数。设 三个齿轮的齿数分别为: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的最大公因数 验证三角形外心定理 三角形三条边的垂直平分线交于一点，该点是三角形外接圆的圆心。 解：不失一般性，假设三角形的任意一条边都不平行于任意一个坐标轴。依据平面几何知识，该问题的验证步骤应该是： 读入三点a,b,c的坐标(x1,y1)、(x2,y2)、(x3,y3)； 检验三点是否构成一个三角形； 若三点构成三角形，则验证外心定理 。 受限排列组合——穷举法与试探法 有这样一类问题，从若干元素的所有排列(或组合)中选取符合某种条件的一些排列(或组合)。 八皇后问题 八皇后问题 这是一个古老而有趣的游戏。高斯(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 若