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

第九章 程序开发和结构化程序设计 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+38=%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 /* for */ while ( b ) S /* while */ 图4 WHILE语句 图5 FOR语句 图6 DO语句 用合适的助记名来命名标识符 注释 自顶向下逐步求精的程序设计技术 n自顶向下、逐步求精 若想让计算机解题必须用清晰而无两义性 的方式给它提供算法。要求： 找出一个算法，它能提供所解问题的从输入到 输出所需的映象。 选择一种程序语言写出程序，用计算机能接受 的方式表述算法。 关键是如何找出算法。因为写出程序，只 是表述算法，应该没有困难。 求解一个问题 粗略的解决方案 细 化 第一步子问题 第二步子问题 第n步子问题 . 前处理 结束条件 后处理 进 展 一 步 前处理 后处理 条 件 处理1 处理2 处理n . . 条件 条件 条件 前处理 后处理 递归 条件 递归 顺序 连接 循环 分支 选择 递归 求精实例 n测定字母偶的出现频率 n三个齿轮啮合问题 n验证三角形外心定理 编程序，测定字母偶的出现频率 测定小写字符串中相邻字母偶出现频率。 例如，针对 the cat 对 th 、he 、ca 、at 计数。设有说明： int conmat2626 ; 字母偶 he 的出现次数存入下标变量 conmath-ae-a 首先把该问题分解成如下几步： 1）初始化计数器数组conmat ； 2）统计每个字母偶的出现频率； 3）输出统计结果。 initial 初始化 statistical 统计 out 输出 求精上述PAD中的每一个步骤： 初始化数组conmat ,显然应该一行一行的初始化； 对于每行又应该一个元素一个元素的初始化。 初始化 第c1行 initial 初始化 for( i=0; i 0 ) if ( check(m) ) if ( m=8 ) out() ; change() ; else extend() ; else change(); 从上例可以看出, 穷举法与试探法的着眼点及主要区别 在于: 穷举法是举出全部可能的格局，对每种格局进行检验, 使合格者入选，不合格者淘汰。 试探法是从初始满足条件的格局开始，逐步前进。每 前进一步都判断子格局是否合适。 若当前子格局合适则进入下一级; 若当前子格局不合适则选同一级的下一个子格局; 但 是若同级子格局已全部试探完毕, 则回溯到上一级 直到当前子格局够长为止。 显然穷举法的运算量比试探法要大的多。因为它 要考虑一切情况的排列，而试探法可以在中间丢掉 大量的不合格排列。 事实上许多问题的穷举法是不适用的, 八皇后问 题穷举法有88种排列，把每一种情况都排出来，并检 验其是否合格显然是不可能的。 在上述算法中, 不论是穷举法还是试探法，都是 用循环迭代的方式给出的解法。循环程序可以用递 归来表示。 不论穷举法还是试探法都可以写成递归形式: 八皇后 穷举法的递归实现 n用穷举法实现八皇后问题, 可以抽象的描述为： 在数组A的8个位置上分别排列一个1到8的整数 。设想, 如果有一个函数 queen(r) 能够完成 “在数组A后部的r个位置（从第8-r+1到8）上, 分别排列一个1到8的整数”。 则八皇后问题便是 queen(8) n“在数组A后部的r个位置上, 分别排列一个1到8的整 数”可以分解成: 先在第8-r+1位上分别排列一个1到8的整数； 然后再在剩余的后部的r-1个位置上分别排列一个 1到8的整数。 n步骤2便是对queen的递归调用 queen(r-1)。 n最后考虑递归出口, 显然应该在 r=1 时检验输出并 退出递归。 n由此得递归实现八皇后问题的穷举算法及递归程序 八皇后穷举法 结束 queen(8) queen(r) 结束 for (i=1; i1 输出 检验 int A 9 ; bool check(); /* 检查某格局是否合格的函数, 分程序略 */ void out() ; /* 输出函数, 分程序略 */ void queen( int r ) int i ; for ( i=1; i1 ) queen(r-1); else if ( cheek() ) out(); int main(void) queen(8) 八皇后 试探法的递归实现 n试探方法的思路是，按一定规律，从某一满足条件的初 始状态出发，逐步试探生成满足条件的子排列, 不断增加 子排列长度, 直到子排列的长度满足问题的要求长度n为 止,便找到了一个解。设想, 如果有一个函数 queen(r) 能够“合理的排列数组A后部的r个(从第n-r+1到n)元素” 并保证序列满足给定条件, 则八皇后问题便是对queen的 调用 queen(8) n“合理的排列数组A后部的r个（从第n-r+1到n）元素”可以分 解成: 首先在第n-r+1位上排列一个合格的元素, 然后在合理的排列从n-(r-1)+1开始的后部的r-1个元素。 n步骤1 “在第n-r+1位上排列一个合格的元素”，即是把8个元 素顺次的排列在第n-r+1位上, 并对每个元素检验是否合格， 使合格者入选。 n步骤2 “合理的排列后部的r-1个元素” 显然与 “合理的排列后 部的r个元素”具有相同的特征属性, 只是排列的元素个数减 少了,也就是说它表现为对queen的递归调用。 queen(r) 结束 for (i=1; i1 在该算法中, 试探法的 “延长” 体现在继续递归调用上； “修正本位” 体现在从 1 到 8 作 i 的循环上； “回溯” 则体现在递归出口的返回上。 int A 9 ; bool check( int m ); /*检查某格局是否合格的函数 */ void out(void) ; /* 输出函数 */ void queen( int r ) /* 试探法 */ int i; for ( i=1; i1 ) queen(r-1) ; else out(); int main(void) /* 主程序 */ queen(8) n分析检验条件: 纵向, 每列只有一个皇后: 由数据结构保证每列只能 放一个皇后。 横向，每行放置一个皇后: 显然要求数组 A 中不能有 重复的数值。设当前为第m步，由于前m-1步是合格 的, 所以只要检验Am不等于所有的 A1、. 、Am -1。 左高右低对角线(共有2*n-1即15条)：这样对角线上 不同位置的行列号之差相等。设当前为第m步，由于 前m-1步是合格的，所以只要对一切inn 输入n 结束 枚举(0) 枚举(m) Am=i; 枚举(m+1); 返回 m k ; B中有k Bv=k; v+ return true u = nn-1 for( i=u+1; i k ; B中有k Bv=k; v+ int trans( int e , int f ) /* AeAf 翻译成10进制整数 */ int kk , j ; kk=0; for ( j=e; j=f; j+ ) kk = kk*2 + Aj%nn ; return kk; bool test_b( int kk, int b, int v ) /* 检验