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

第九章 程序开发和结构化程序设计,良好的行文格式自顶向下逐步求精的程序设计技术受限排列组合穷举法与试探法本章小结作业,良好的行文格式,程序的行文格式不好直接影响程序的可读性、清晰性和外观。,/*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语句,用合适的助记名来命名标识符,注释,自顶向下逐步求精的程序设计技术,自顶向下、逐步求精若想让计算机解题必须用清晰而无两义性的方式给它提供算法。要求：找出一个算法，它能提供所解问题的从输入到输出所需的映象。选择一种程序语言写出程序，用计算机能接受的方式表述算法。关键是如何找出算法。因为写出程序，只是表述算法，应该没有困难。,求精实例,测定字母偶的出现频率三个齿轮啮合问题验证三角形外心定理,编程序，测定字母偶的出现频率,测定小写字符串中相邻字母偶出现频率。例如，针对the cat对th、he、ca、at计数。设有说明：int conmat2626;字母偶 he 的出现次数存入下标变量conmath-ae-a,首先把该问题分解成如下几步：1）初始化计数器数组conmat；2）统计每个字母偶的出现频率；3）输出统计结果。,求精上述PAD中的每一个步骤：初始化数组conmat,显然应该一行一行的初始化；对于每行又应该一个元素一个元素的初始化。,初始化第c1行,考虑统计部分：假设被统计的字符串是从终端输入的，则显然我们应该把该字符串全部读入，并在读入的过程中边读边统计。用下图表示。,读(prevchar),while(!EOF),统计一次,def,读(thischar),再考虑具体统计算法，为统计字母偶的出现频率，显然在读入字符串的过程中应该始终保存两个字符 prevchar、thischar，并且当该两个字符都是字母时，相应计数单元加1；最后在读入下一个字符之前还应该把保存的两个字符向前串。,最后考虑输出部分,我们把结果输出成两个 2613 的表，每个表元素是相应字母偶的出现次数：*a b c d e.mab.z*n o p q r.zab.z,打印一个表（第一个表），显然应该先打印表头再打印下边各行,打印表头,打印表体,beginch,endch,打印表头可以求精成先输出一个“*”；再顺次输出各个字符。顺次输出各个字符是一个循环。,打印表头,打印表体,beginch,endch,输出(*),输出(n),顺次输出各个字符,打印表体应该一行一行的打印，每行应该先打印行头，再打印本行各个元素；打印本行各个元素，应该一个元素一个元素的打印，是一个循环,打印表体,beginch,endch,输出(*),输出(n),输出一行,输出(c1),输出(n),输出本行各个元素,三个齿轮啮合问题,设有三个齿轮互相衔接，求当三个齿轮的某两对齿互相衔接后到下一次这两对齿再互相衔接，每个齿轮最少各转多少圈。解:这是求最小公倍数的问题。每个齿轮需转圈数是三个齿轮齿数的最小公倍数除以自己的齿数。设三个齿轮的齿数分别为:na、nb、nc；啮合最小圈数分别为:ma、mb、mc；三齿轮齿数的最小公倍数为k3。,计算步骤表示为：,读入三齿轮齿数和输出结果，分别只是一次调用读或写函数，不必求精。,求精计算三齿数的最小公倍数k3。可以把该问题分解成 先求两个齿数na与nb的最小公倍数k2，然后再求k2与第三个齿数 nc 的最小公倍数k3，k3即为na、nb、nc三个齿轮齿数的最小公倍数。设已经有求两个数的最小公倍数的函数 int lowestcm(int x,int y)则该求精过程可表示成。,求精求两个数的最小公倍数的函lowestcm。x、y的最小公倍数是x、y 的积除以x、y 的最大公约数。设已经有求两个数的最大公约数的函数 int gcd(int x,int y)则该求精过程可表示成：,采用展转相除法求两个数的最大公约数，函数int gcd(int x,int y)定义如下,函数gcd是一个递归函数，先采用分支求精过程、再采用递归求精过程，可以求精成下图,最后，分别计算啮合的最小圈数可以被求精成下图。,验证三角形外心定理,三角形三条边的垂直平分线交于一点，该点是三角形外接圆的圆心。解：不失一般性，假设三角形的任意一条边都不平行于任意一个坐标轴。依据平面几何知识，该问题的验证步骤应该是：读入三点a,b,c的坐标(x1,y1)、(x2,y2)、(x3,y3)；检验三点是否构成一个三角形；若三点构成三角形，则验证外心定理。,读入三点坐标只是一个读语句，不必求精，下边求精检验是否三角形和验证外心定理。,检验三点是否构成三角形使用一个bool型函数isTriange，可以求精成：求两点p1,p2确定的直线方程L12；判断若p3在L12上，则 isTriange 为false，否则isTriange为true。,求两点间直线方程可以写一个函数 line(x1,y1,x2,y2,*a,*b)并求精成下图。,验证外心定理可以如下进行：求每条边的垂直平分线；验证该三条直线是否交于一点；若交于一点，则验证该点到三角形各顶点距离是否相等否则 错误命题。,求每条边的垂直平分线方程可以写一个求一条线段的垂直平分线方程的函数，然后分别三次调用该函数。,求一条边的垂直平分线方程可以先调用前述函数 line，求该边的直线方程;再求该边的中点,然后求过该中点的与该边垂直的直线方程，得下图,验证该三条直线是否交于一点编成一个函数isOnePoint，可以先求两条直线的交点，然后再判断第三条直线是否过该点。,设有一个函数 distance(x1,y1,x2,y2)可以计算两点间距离，验证三条垂直平分线的交点到三角形各顶点距离是否相等，是一个布尔表达式。,受限排列组合穷举法与试探法,有这样一类问题，从若干元素的所有排列(或组合)中选取符合某种条件的一些排列(或组合)。八皇后问题Debruijn 问题,八皇后问题,这是一个古老而有趣的游戏。高斯()最早在1850年提出并研究过这个问题，但是没有完全解决。该问题是：在一个8*8格的国际象棋棋盘上放置八个皇后，使任意两个皇后都不能互相攻击。按国际象棋规则，两个皇后可以互相攻击。若在同一行上，或在同一列上,或在同一条斜线上（包括左高右低、右高左低）,如图放置的八个皇后便不能互相攻击。编程序,求出所有符合要求的布局。共有92种满足条件的布局，若除去对称的等类同布局,完全不同者有12种。这里不考虑剔除类同布局，求出全部92种布局。,解这类问题有两条途径:1.穷举法;2.试探法。下边以八皇后问题为例，分别介绍这两种方法。,在具体介绍这两种方法之前，先考虑八皇后问题的表示方法。用一个一维数组表示棋盘。Ai表示棋盘的第i列，若Ai中存放有数k表示第i列中第k行上放置了皇后。例:A3=6表示在棋盘的第3列第6行上放置一个皇后。A0是根据下边算法的需要,多设的一个元素。,八皇后 穷举法,本方法思路是，按某种顺序枚举出全部排列或组合。每当枚举出一种排列或组合之后，便用给定条件判断该种排列或组合是否符合条件。若符合条件，则本种排列或组合被选中，可以输出或记录下来。若不符合条件，则把本种排列或组合舍掉。八个皇后的排列问题，最简单的方法是八重循环，可以编出如下穷举法程序。在下述算法中，用到检验函数check与输出函数out。为简单起见，先省略它们的具体实现细节。,int main(void)int a9，i1,i2,i3,i4,i5,i6,i7,i8;for(i1=1;i1=8;i1+)for(i2=1;i2=8;i2+)for(i3=1;i3=8;i3+)for(i4=1;i4=8;i4+)for(i5=1;i5=8;i5+)for(i6=1;i6=8;i6+)for(i7=1;i7=8;i7+)for(i8=1;i8=8;i8+)a1=i1;a2=i2;a3=i3;a4=i4;a5=i5;a6=i6;a7=i7;a8=i8;if(check()out();,八皇后 试探法,按规律，从一满足条件的初始状态出发，逐步生成满足条件的子排列,不断增加子排列长度。增加子排列长度过程中，每增加一位,生成一个子排列后,便检验它是否满足条件。不满足条件,则换一个子排列即修改当前位置满足条件,则延长子排列,增加子排列长度。子排列的长度满足要求长度,便找到了一个解。若要求找一个解即可，这时便可以结束。若要求找所有解，这时可以输出或记录本解，然后按前述思路，继续修改排列，继续试探，找下个解,在上述试探过程中,修改当前位置时：若当前位置上还有没被试探过的元素，则应该取下一个没被试探过的元素进行试探若当前位置上所有元素都被试探过了，则在当前位置上没办法再修改了这说明前边的某个位置有问题，放置的元素不对，显然应该向回退一位。回溯后,原来的上 一个位置变成了当前位置,则又变成修改当前位置的问题了。这时,同样还应该考虑取下一个没被试探过的元素进行试探,以及是否所有元素在当前位置上都被试探过了并回溯的问题。,如图所示，设要生成一个 n 位的串A；在每个位置上可选择的符号有 K 个；A 应该满足条件 r；m表示当前试探位置。试探法的算法描述为：1.初始时，从第一个位置开始试探，令 m=1;2.然后在第 m 位逐次取可选符号:B1,B2,.,Bk。对某一个Bi有两种可能:,若Bi使A1,A2,.,Am满足r,则进入A的下一个位置。m=m+1,若Bi不能使A1,A2,.,Am满足r,则有两种情况:ik，,若Bi不能使A1,A2,.,Am满足r,则有两种情况:ik，取B中下一个符号继续试探i=i+1,若i=k 说明在当前位置上所有符号都已经被试探过,若i=k 说明在当前位置上所有符号都已经被试探过应该回溯到上一个位置,作 m=m-1 后继续试探直到找到解、m=0结束,*,*,*,*,*,*,*,*,*,*,*,*,*,*,以四皇后问题为例，考察试探过程：,上述试探法思想描述成如下PAD:,程序如下:int A 9,m;bool check(int m);/*检查某格局是否合格的函数*/void out();/*输出函数*/void change(void)/*修正*/while(Am=8)m=m-1;Am=Am+1;void extend(void)/*延长*/m=m+1;Am=1;,int main(void)/*主程序*/A0=0;A1=1;m=1;while(m 0)if(check(m)if(m=8)out();change();else extend();else change();,从上例可以看出,穷举法与试探法的着眼点及主要区别在于:穷举法是举出全部可能的格局，对每种格局进行检验,使合格者入选，不合格者淘汰。试探法是从初始满足条件的格局开始，逐步前进。每前进一步都判断子格局是否合适。若当前子格局合适则进入下一级;若当前子格局不合适则选同一级的下一个子格局;但是若同级子格局已全部试探完毕,则回溯到上一级直到当前子格局够长为止。,显然穷举法的运算量比试探法要大的多。因为它要考虑一切情况的排列，而试探法可以在中间丢掉大量的不合格排列。事实上许多问题的穷举法是不适用的,八皇后问题穷举法有88种排列，把每一种情况都排出来，并检验其是否合格显然是不可能的。在上述算法中,不论是穷举法还是试探法，都是用循环迭代的方式给出的解法。循环程序可以用递归来表示。不论穷举法还是试探法都可以写成递归形式:,八皇后 穷举法的递归实现,用穷举法实现八皇后问题,可以抽象的描述为：在数组A的8个位置上分别排列一个1到8的整数。设想,如果有一个函数queen(r)能够完成“在数组A后部的r个位置（从第8-r+1到8）上,分别排列一个1到8的整数”。则八皇后问题便是 queen(8),“在数组A后部的r个位置上,分别排列一个1到8的整数”可以分解成:先在第8-r+1位上分别排列一个1到8的整数；然后再在剩余的后部的r-1个位置上分别排列一个1到8的整数。步骤2便是对queen的递归调用 queen(r-1)。最后考虑递归出口,显然应该在 r=1 时检验输出并退出递归。由此得递归实现八皇后问题的穷举算法及递归程序,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为止,便找到了一个解。设想,如果有一个函数queen(r)能够“合理的排列数组A后部的r个(从第n-r+1到n)元素”并保证序列满足给定条件,则八皇后问题便是对queen的调用 queen(8),“合理的排列数组A后部的r个（从第n-r+1到n）元素”可以分解成:首先在第n-r+1位上排列一个合格的元素,然后在合理的排列从n-(r-1)+1开始的后部的r-1个元素。步骤1“在第n-r+1位上排列一个合格的元素”，即是把8个元素顺次的排列在第n-r+1位上,并对每个元素检验是否合格，使合格者入选。步骤2“合理的排列后部的r-1个元素”显然与“合理的排列后部的r个元素”具有相同的特征属性,只是排列的元素个数减少了,也就是说它表现为对queen的递归调用。,在该算法中,试探法的“延长”体现在继续递归调用上；“修正本位”体现在从 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),分析检验条件:纵向,每列只有一个皇后:由数据结构保证每列只能放一个皇后。横向，每行放置一个皇后:显然要求数组 A 中不能有重复的数值。设当前为第m步，由于前m-1步是合格的,所以只要检验Am不等于所有的 A1、.、Am-1。左高右低对角线(共有2*n-1即15条)：这样对角线上不同位置的行列号之差相等。设当前为第m步，由于前m-1步是合格的，所以只要对一切im检验：Am-m Ai-i。左高右低对角线:与左高右低对角线类似。只不过这里该检查Am+m Ai+i。,试探法检验函数 check 如下，bool check(int m)int i;for(i=1;im;i+)if(Am=Ai)return false;if(Am-m=Ai-i)return false;if(Am+m=Ai+i)return false;return true;,穷举法的检验函数应该多加一层循环。bool check()int i,j;for(i=1;i8;i+)for(j=i+1;j=8;j+)if(Aj=Ai)return false;if(Aj-j=Ai-i)return false;if(Aj+j=Ai+i)return false;return true;,Debruijn 问题,如图由 个二进制数字0、1组成一个环。使 个3位的二进制数:000 0 001 1 010 2 011 3 100 4 101 5110 6 111 7正好在环中各出现一次。本例目前的顺序是：0、1、2、5、3、7、6、4。设计生成这样环的程序。环由 2n个二进制数字组成，恰好包含2n个互不相同的n位二进制数。,解:还是分别用试探法和穷举法来解该题。先考虑环的表示，对任意n，环上有2 n个0、1。用一维数组A保存环上的数据。A的长度nn=2 n。并且认为Ann-1与A0相接构成环。,Debruijn 问题 递归实现穷举法,int nn,outnum=0;/记录环的长度int A 256;/*保存环,限制输入 n 最大为 8*/void next(int m)/*穷举*/int i;if(m nn)for(i=0;i=1;i+)Am=i;next(m+1);else if(check(nn-1),Debruijn 问题 试探法迭代实现,环上一定有n个连续0组成的n位二进制数0。作为初值把n个0放在最前边，从第m=n位开始试探。找到一个解输出后，令m=nn,使循环终止。算法如图：,/*PROGRAM Debruijn2*/*声明部分同前，略*/void extend(int*m)/*延长函数*/(*m)+;A*m=0;void back(int*m)/*修正本位函数*/while(A*m=1)(*m)-；/*回朔*/A*m=1；/*修正本位*/,int main(void)int n,i;int m;/m 记录当前处理位置。注意m是局部量，/为了在子程序中修正它，使用指针参数。printf(“n please input n=”);scanf(“%d”,Debruijn 问题 试探法递归实现,初始状态仍用前 n 个 0。从第 n+1 位开始递归试探。,/*PROGRAM Debruijn3*/void next(int m)if(flag)/*试探结束*/if(mnn)Am=0;if(check(m)next(m+1);/*延长*/Am=1;/*修正本位*/if(check(m)next(m+1);/*延长*/else out();flag=false;,int main(void)printf(“n pleace input n=”);scanf(“%d”,检验函数 check为了检验环上已存在哪些n位二进制数，用一个数组B，保存已检验过的互不相同的n位二进制数。check的参数u为当前放入数组A中的“0、1”个数。在穷举法中用nn作实在参数对应该u，在试探法中用每步试探时的序列长度m为实在参数对应该u。,check函数的两种情况当前所生成环长度小于条件unn-1A1 Au不能构成环当前所生成环长度满足条件u=nn-1A1 Ann-1没有扣圈扣圈,A0,A4,A1,A2下标是n-1,A3,A6,A5,b0,b1,b2,b3,b4,A7,u6,A0,A4,A1,A2下标是n-1,A3,A6,A5,b0,b1,b2,b3,b4,b5,下标是(u+1)%nn,b6,b7,unn-1 A7,A0,A4,A1,A2下标是n-1,A3,A6,A5,unn-1 A7,b0,b1,b2,b3,b4,b5,v=0,for(i=n-1;i=u;i+),return false,Ai-n+1Ai翻译成 10 进制=k;,B中有k,Bv=k;v+,return true,u=nn-1,for(i=u+1;i=u+n-1;i+),return false,A(i-n+1)%nnAi%nn 翻译成 10 进制=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)/*检验b0 bv中有kk*/int j;for(j=0;jv;j+)if(kk=bj)return false;return true;,本章小结,本章讲述不太重要的两种 C 语句以及极其重要的结构化程序设计思想，最后讲述一类问题的程序设计方法。重点掌握自顶向下逐步求精的程序设计技术。穷举法和试探法。,作业,9.19.20,