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

第九章 程序开发和结构化程序设计,goto和标号 空语句 结构化程序设计原则 程序风格 程序的正确性 可移植性,文档 自顶向下逐步求精的程序设计技术 受限排列组合 穷举法与试探法 本章小结,goto和标号,goto 语句是强制改变程序正常执行顺序的手段。但是我们事先声明 频繁使用goto语句不是好的程序设计习惯，不符合结构化程序设计原则 除有特殊需要外，尽量不要使用goto语句和标号 标号的语句 标号 : 语句 label1: statement;,goto 语句 goto 标号 goto label1; 标号就是带标号语句中用的标号，是一个标识符； goto 是保留字，表示转向。 goto 语句的意义是中断正常的程序执行顺序，转到本函数内标号标出的语句处，并从其开始继续向下执行 goto 语句与带标号语句配合使用，达到改变程序正常执行顺序的目的。,【例9-1】前述第5章例5-8中迭代法求解方程根的问题,不改造流程图, 可以用如下右端的程序片段表示,x0=0.9; /* 1 */ r1:x1=f(x0); /* 2 */ if ( abs(x1-x0)1e-5 ) /* 3 */ goto r2 ; /* 4 */ x0=x1; /* 5 */ goto r1; /* 6 */ r2: ; /* 7 */,虽然C允许使用 goto 语句转向本函数内任何语句，但是下述转向是极其不好的程序设计习惯。它使程序逻辑混乱，同时也给编译优化带来麻烦。 从if语句外转入if语句的“then”或“else”子句之中； 在if语句的“then”或“else”子句之间转向； 从switch语句之外转入switch语句之内； 从循环语句之外转入循环语句之内； 从复合语句之外转入复合语句之内。,空语句,空语句（empty-statement）只由一个分号“；”组成，表记没有任何操作动作。其语法是： 空语句 ； 空语句也是一种语句。只不过在程序正文上看它只有一个分号。在语义上看它没有任何操作动作，其作用只是占据一个语句的位置。,空语句有时起很大作用,例: for ( . ) . goto r0 ; . r0: ; ,结构化程序设计原则,由于计算机硬件技术的不断发展，以及计算机的广泛应用，计算机软件系统也日益发展 软件在计算机系统中所占比重也越来越大 使得作为软件主要组成部分的程序系统越来越庞大，复杂度越来越高，造价也越来越昂贵，同时出错率也不断增加，系统的可靠性越来越难以保证，维护也越来越困难。 最后终于在20世纪60年代中期引起了一场所谓的软件危机。在该背景下，1968 年 Dijkstra 提出了结构化程序设计思想。这种思想的基点是： “清晰，易懂地书写程序逻辑，使程序结构表现得简单、明快”,从这点出发，人们经过艰苦实践，总结出了一套结构化程序设计原则。这套原则要求程序员写出的程序应该是结构良好的，即: 易于保证和验证程序的正确性 易于阅读、维护和调试。 这种良好结构的程序具体体现在：对任意程序段来讲 仅有一个入口，一个出口 没有死循环 没有死码区。,为了达到上述目的，强调程序员在写程序时应该: 利用自顶向下、逐步求精的技术设计程序 具有良好的程序设计风格 尽量利用标准的顺序、分支、重复控制结构。保证程序仅有一个入口、一个出口。 限制使用 GOTO 语句。可能一个坏程序的缺点都是由 GOTO 语句引起的。,结构化程序设计的发展，使程序设计从技艺走向工程，为软件工程学发展奠定了有力基础。使软件生产由个体作坊式的艺术创作方式发展成为千千万万人参加的工程方式，达到了“系列化、产品化 、工程化 、标准化”。“软件工程”也从这一时期开始逐步发展起来。 能够反映结构化程序设计要求，便于书写结构化程序的程序设计语言，称结构化程序设计语言。可以认为C是结构化程序设计语言。,结构化程序设计方法是20世纪60年代末70年代初逐渐发展起来的，目前程序设计领域的热点是“面向对象程序设计”和“基于构件的程序设计”等。但是它们的主要特长在于程序的组织、信息封装、软件重用等，而最终对于足够小程序模块的编码，它们没有给人们带来益处。 结构化程序设计方法针对每个小模块的设计起着十分关键的作用。所以尽管目前面向对象程序设计技术和基于构件的程序开发技术受到人们广泛关注与重视，但是结构化程序设计技术仍然是十分重要和不可缺少的。可以说结构化程序设计是一切程序设计技术的基础，是任何软件工作者必须掌握的技术。,程序风格,程序风格是指程序的书写格式等与易读性、清晰性、互相交流有关的，而与程序执行无关或关系不大的一些的问题。 写程序不仅仅是为了与计算机进行交流，而且也是为了与人进行交流，进一步还为了给自己或别人阅读，同时程序员自己也需要不断地查阅自己编出的程序，更何况程序的维护很可能由别人来做。 在写程序时要考虑到：程序既是为了在计算机上运行，也是为了今后的交流和阅读，同时还是为了留下有用的参考文件。,为此，程序必须是宜于阅读的，也就是必须是结构良好或风格优美的。 程序设计风格不好不利于产生正确、高效、易读、易维护的程序。风格不好的程序会使程序维护费用与时间增加，甚至导致整个编程过程失败。 程序设计风格是程序员必须的修养。良好的程序设计风格是程序员在长期的编程实践中逐步发展，积累和提炼出来的。它是产生正确、高效、易读、易维护程序的一种重要的手段。 程序风格主要涉及程序的行文格式、注释和空白的合适用法、尽量使用合适的助记名来命名标识符、明白地表示出程序结构和数据结构等。,良好的行文格式,程序的行文格式不好直接影响程序的可读性、清晰性和外观。如下完全相同的程序写成 A 和 B 的格式显然都没有写成 C 的格式好。因为C的格式层次分明，格式清晰，意义明确。,/* A */ #include stdio.h int i;main ()i=25+38;printf(“25+38=%d”,i); /* B */ #include stdio.h int i;main () i = 25+38; printf ( “25+38=%d” , i ); /* C */ #include stdio.h int i; /* 声明整型变量i */ int main (void) /* 主函数 */ i = 25+38; /* 求和运算 */ printf ( “25+38=%d” , i ); /* 打印 */ ,下面给出“适当使用空行、空格”一般方法的建议: 在 #编译预处理命令、typedef类型定义、变量声明之前加一个空行，并把这些部分分别集中写在一起； 在运算符的两边、赋值运算符“=”的两边，可以各加一个空格。 在函数定义之前加两个或更多的空行。 每个常量定义占一行。 每个类型声明均另起一新行。,每个变量声明均另起一新行。并注意一个变量声明中的每个变量说明符之间的排列。 在结构和联合声明中，各成员声明向右缩进几列。 复合语句的 左花括号“”放在函数定义说明符、if、else、switch、while、for、do、struct、union的起始行末尾 ； 右花括号“”与相应语句或声明引导词的第一个字符对齐，并以注释标明，例：“/* if */” ； 各成分语句或声明向右缩进几列并对齐,函数定义中，函数定义说明符另起一行，函数体部分各个语句和声明向右缩进几列。呈图1格式。 IF语句把if 、else对齐，并且内含的子语句向右缩进几列。呈图2格式。 SWITCH语句内部各个case标号分别占一行，“:”互相对齐，并比switch缩进几列；“:”后的语句开始符对齐。呈图3格式。,if （ b ） S1 else S2,switch ( expr ) case a1: S; case a2: S2 . case an: sn /* switch */,图1 函数定义 图2 IF语句 图3 SWITCH语句,int main ( vido ) DS DS . /* main */,WHILE语句把while 、条件b写在一行上，而把循环体S另起一行并相对于while 缩进几列。呈图4格式。 FOR 语句把循环描述部分的for表达式写在一行上，而把循环体S另起一行,并相对于 for缩进几列。呈图5格式。 DO语句把do和while对齐，循环体中的各个成分语句向右缩进几列并对齐。呈图6格式。,do S while (b),for(expr1;expr2;expe3) S /* for */,while ( b ) S /* while */,图4 WHILE语句 图5 FOR语句 图6 DO语句,用合适的助记名来命名标识符,标识符是程序员给自己引进的常量、类型、变量、函数等起的名字。程序设计语言对如何命名标识符没有限制，标识符也没有固定的含义。 但是从使用角度看，标识符表记的每个对象都有具体的含义。为了提高可读性和有助于记忆，应该使标识符在拼写上尽量和它所标记对象的物理、数学等含义相一致，并且要避免与系统预定义的标准标识符重名。,例如， 表示圆周率用 pai 就比用一个一般的 a 要好 表示面积用 area 就比用 s 要好 表示长度用 length 就比用 l 要好 表示某一角度 a 的正弦值用 sin_of_a 就比用 sin 要好 .,注释,注释是间隔符的一种，在程序中的作用相当于一个空格。注释的存在不影响程序的意义，但是它有助于人们阅读和理解程序, 使原来模糊的、意义不清的部分变得清晰明了。 在程序中适当加入注释是一个好的程序设计习惯。但是也不要在不需要加注释、意义十分明显的地方加注释。通常:,所有程序都应该从注释开始，该注释至少应该包含如下一些信息： 程序的名称 编写和调试人员的姓名 版本编号 完成时间或最后一次修改时间 程序所做工作描述 使用注意事项 要求的输入数据及其数据格式 产生的输出数据及其格式 . .,所有函数都从注释开始，该注释至少应该包含如下一些信息： 函数的名称 每个形式参数的名称、作用、特性、及其对实在参数的要求 编写和调试人员的姓名 版本编号 完成时间或最后一次修改时间 该函数功能，用到的主要算法 该函数产生的结果、及该结果对主程序的影响 使用注意事项 . .,可以对一个程序段、一个语句、一个声明等加注释，以注明某程序段的功能、一个语句的作用、一个常量或变量的意义等。 当修改有注释的程序时，若程序内容被修改，则相应的注释也必须作修改。错误的注释往往比没有注释效果更坏。,对程序说明的建议,程序中使用的全部常量都要引进一个常量标识符，在程序中不应该出现除了0、1等极其简单的常量以外的其它字面常量。并且常量应该是全程的。在程序一开始用宏定义把本程序中用的全部常量定义，并加注释标明每个常量的意义、使用位置等。而在每个函数中一般不应该再包含常量定义。,大多数情况下，类型名也应该是全程的。但是，对类型的要求要比对常量宽，也可以把类型说明成局部的。 应该按照作用和用途来选择变量的说明位置，并且应该尽量把变量说明成局部的。 函数一般应该只访问它的形式参数和局部量。如果必须访问全局量，应该加必要的注释。,程序的正确性,编程序的目的是把需要计算机解决的问题描述出来，交给计算机，使计算机能按要求解决问题或完成运算。这就要求程序能正确的表达问题程序正确。但人不是神，免不了经常犯错误。一个程序不能产生正确的结果，原因是多方面的，比如： 问题说明的不正确； 所选的算法不是问题的真正解； 程序没有精确的实现算法； 用了错误的数据去执行。,错误种类,一个程序没有产生正确的结果，可能存在有各式各样的原因。这些错误可大致分成如下三类: 语法错误 写出的程序不符合C语言的语法，称有语法错误。比如标识符未说明、语句结构不对、标识符重复说明、. 等等。 避免这类错误的一个根本办法是精确掌握C语言的严格语法定义（BNF表示式），严格的按语法写程序,语义错误 解释程序语义时发现的错误称语义错误。比如：以零作除数、运算分量类型不匹配、死循环、形式参数与实在参数不匹配、变量没赋值之前就使用其值. 等等。 这类错误中的一部分可由编译程序查出来，有一部分错误编译程序检查不出来。 逻辑错误 逻辑错误是程序没有真实反映算法、或算法本身就有错误没有反映所求的问题。例如：错误的运用全局量、错写运算符、. 等等。 这类错误是最大量出现也是最难对服的。程序的调试和查错主要是查这,程序测试和验证,语义错误的一部分以及逻辑错误都要靠本节介绍的方法来排除。计算机程序在投入使用之前，一定要保证它正确。看程序是否正确有两条途径： 证明 若能证明一个程序正确，是最理想的。目前在软件领域内有一个研究分支“程序正确性证明”，专门研究程序正确性证明的理论和方法。不过这已超出本课的范围，我们不涉及它。 测试 给定一切可能的数据运行程序，看结果是否正确，若结果正确，则说明相应程序是正确的,给出一切可能的数据运行程序，事实上是不可能的。有效并实用的方法是：选取若干组有代表性的数据进行测试。这些数据的组合，能代表整个数据的全貌。 所谓有代表性的若干组数据，大致应考虑如下情况: 正确的数据，应能得到正确的结果； 错误的数据，应能报告数据出错，或得到错误结果； 边界上的数据，也能按数据特性，取得合理的结果。 若从程序逻辑上看，选取的数据组应能遍历程序的一切分支和循环。应能达到PAD图最右端的一切可执行框。 不论验证还是测试，只能发现错误，不能证明或说明程序正确没有错误。,测试方法,测试是为了找出程序中的语义、逻辑错误并修改之，有两种途径： 自顶向下 自底向上 自底向上的方法是先从程序的最底层的基本模块开始调试，给出适当数据进行测试，得到正确的模块（保证达到对本模块的要求）；然后向上，调试高一层次的模块；正确后，再向上，如此等等. ；直到最顶层。,自顶向下的方法是从程序的最顶层开始，先假设底层模块正确，调试顶层的整体逻辑，使之正确；然后下到低一层次的各模块，再假设更低层次中的模块正确，调试本层各模块，每一模块保证达到其上层的要求；然再调试更底一层的模块；. 如此等等。直到最底层的每个模块都调试正确为止。 自顶向下方法可以有效的定位错误，不致因为底层错误而影响整个程序逻辑，比较合理。而且这种方法与算法分析及程序设计时采用的自顶向下、逐步求精技术有紧密的对应关系。所以应该使用这种方法来调试程序。 当然这不是绝对的，事实上经常使用的也比较有效的手段是两种方法互相结合。,可移植性,如果一个程序在任何计算机上以及在任何编译系统中都能运行，则说这个程序是可移植的。 如果有可能应该尽量使用不依赖于具体计算机和具体编译系统的方式写程序。 不幸的是标准C中有若干处“由实现定义的” 和“依赖于实现的” 地方； 各个编译系统也在不同程度上对C进行了扩充； 有些编译系统又在不同程度上对标准C进行了一些限制。,为了使程序具有可移植性，建议编程序时注意以下诸点（但它们并不能完全保证可移植性）: 尽量避免“依赖于实现的”和“由实现定义的”部分造成的影响; 不要依赖字符集合的各种性质, 可靠的特性只有 ab z 和 01 9 ; 不论何时输出整数和浮点类型值时, 一定包括宽度和精度参数； 不要为浮点类型计算假设不现实的精度; 尽量不使用具体编译系统对标准C进行的扩充部分； 同样尽量不使用那些可能被某编译系统限制的部分; 用文件仔细说明程序中可能依赖于机器的部分。,文档,程序文档详细记录程序的一切资料。安照我国国家标准，软件产品文档应包括： 可行性报告：一般应该在项目开始前，进行可行性论证时提出。 开发计划：一般应该在项目开始实施前，做工作计划时提出。 需求说明书：一般应该在项目刚开始进行，做需求分析后提出。,数据要求说明书：给出本系统对数据的要求。 概要设计说明书：给出本系统的总体设计。 详细设计说明书：给出本系统的详细设计说明，包括每个程序的功能、输入输出、算法、流程逻辑（流程图、 PAD 图等）、. 等。 数据设计说明：给出本系统使用的数据结构。 用户手册：包括本系统的功能、支掌环境、支持软件、安装及初始化、使用方法步骤、输入输出数据说明、操作说明、出错处理、. 等。 操作手册：包括本系统的运行说明、操作说明、操作步骤等。,模块开发卷宗：每个模块的标题、功能说明、设计说明、测试说明等。 测试计划：包括测试内容、测试条件、测试数据、应得结果等。 测试分析报告：包括测试概要、测试结果、测试结论等。 总结报告。 文档是操作人员的“指南”，维护人员的“参考手册”，必须严格正确，当修改程序时，必须随着修改相应文档。一个与程序不匹配的文档比没有文档更坏。,编程序并不难，只要有算法，会程序设计语言，任何人都可以编出程序，但是不同人编出的程序却大不相同。针对同一个问题: 有人编的程序风格好、易读、易维护、易重用、可靠性高、运行得既快又节省存储空间； 有人编的程序风格差、晦涩难懂、难于维护、冗长、正确性和可靠性极低、运行起来既慢又占用空间。 编程序易，编好程序难 要想编出一个风格优美、正确可靠、各方面均优秀的好程序，必须按照现代软件工程的规范进行 同时也必须遵循好的程序设计原则和使用好的程序设计方法。 本章介绍程序开发、结构化程序设计。,自顶向下逐步求精的程序设计技术,自顶向下、逐步求精 若想让计算机解题必须用清晰而无两义性的方式给它提供算法。要求： 找出一个算法，它能提供所解问题的从输入到输出所需的映象。 选择一种程序语言写出程序，用计算机能接受的方式表述算法。 关键是如何找出算法。因为写出程序，只是表述算法，应该没有困难。,“自顶向下、逐步求精”的程序设计技术是目前较为时髦的、合理的找出算法的一种思维方法。它的核心思想是 对于某一个要解决的问题，在寻求它的解法过程中: 首先从问题的整体（最顶层）出发，将它分解成独立而互不交叉的若干个子问题。每个子问题解决整体问题的一部分或一种情况。这几个子问题若能正确解决，则它们的总和就是整体问题的解。,向下再一个个的具体考虑下一层的各个子问题，针对每个子问题，仍采用对待整体问题解的思路，继续对其进行分解（求精），得到该子问题解法的分解步骤，即更低一层次的子问题。 如此下去，直到最低层的每个子问题都能用计算机语言的一个语句表示出来或都能明显写出解法为止。便找到解决整体问题的解题算法了。,上述的求精过程中的每一步，主要用到如下四种求精技术： 顺序连接的求精 分支、选择的求精 循环的求精 递归的求精,当问题的子解具有前后关系时，采用第一种顺序连接的求精技术，将问题分解成互不相交的几个子问题的顺序执行。 当问题是分别不同情况而应该进行不同处理时，采用第二种分支、选择的求精技术，构造分支。这时要注意分支的条件一定要正确,当问题的子解具有特性：如果有向解的方向前进一步的方法，且不断重复该步骤，即能解决问题，最终达到完全解。则应该采用循环的求精技术。这时要弄清循环的初始条件、结束条件和有限进展的一步都是什么。 当问题的某步解法与前边高层次的某步解法具有相同性质，只是某些参数不同时，可采用递归的求精技术。这时应注意递归的参数变化规律以及递归出口。 所谓自顶向下，逐步求精的分析技术实质上是下图所示过程的反复。,采用自顶向下、逐步求精方法构造程序有如下优点: 程序的层次分明、结构清晰。 便于集体开发程序。对于大型程序来讲，可以每组负责一个模块（一个子部分），在一个组内又可以每个人负责一个子模块（更小的子部分）等等。而各个模块之间以及各个子模块之间相对独立，互相之间没有制约，各个模块的负责人员可以独立的进行程序设计。 便于调试。若程序有错误，可以很容易的将错误局部于某一子部分，找出错误，同时每一部分的错误是独立的，也不至于影响其它的部分。,，,求精过程的表示,有各种方法表示上述求精过程，比较常见的是 传统的流程图方法：把每步求精过程用流程图表示。优点是直观，以两维图表示程序的流程；缺点是不能体现结构化程序设计思想。 函数方法：在求精过程中，每个子问题都以一个函数调用表示，然后再具体求精相应的函数本身。不画框图，而直接书写程序。优点是：直接写出程序，程序的层次分明，能体现结构化程序设计思想。缺点是：以一维方式表示逻辑结构，逻辑结构和算法不直观。,PAD 方法：用二维树形结构图描述程序的逻辑，直观、清楚。具有上述两种方法的共同优点，同时又摈弃了上述两种方法的缺点。 处理的概括性：与一条纵线相连的处理可以作为一个概括。在流程图和程序中，没有特别的表示处理概括的记法。 执行顺序的表示：从上至下用纵线连接处理顺序。在流程图中用箭头表示处理流向；在程序中则没有表示处理顺序的方法。 嵌套层次的表示： PAD的树结构可以清楚地表示嵌套层次。流程图没有表示嵌套的记号；程序则靠的是语句嵌套；都没有PAD清晰、明了。,求精实例,测定字母偶的出现频率 三个齿轮啮合问题 验证三角形外心定理,编程序，测定字母偶的出现频率,测定小写字符串中相邻字母偶出现频率。 例如，针对 the cat 对 th 、he 、ca 、at 计数。设有说明： int conmat2626 ; 字母偶 he 的出现次数存入下标变量 conmath-ae-a,首先把该问题分解成如下几步： 1）初始化计数器数组conmat ； 2）统计每个字母偶的出现频率； 3）输出统计结果。,求精上述PAD中的每一个步骤： 初始化数组conmat ,显然应该一行一行的初始化； 对于每行又应该一个元素一个元素的初始化。,初始化 第c1行,考虑统计部分： 假设被统计的字符串是从终端输入的，则显然我们应该把该字符串全部读入，并在读入的过程中边读边统计。用下图表示。,再考虑具体统计算法，为统计字母偶的出现频率，显然在读入字符串的过程中应该始终保存两个字符 prevchar 、thischar ，并且当该两个字符都是字母时，相应计数单元加1；最后在读入下一个字符之前还应该把保存的两个字符向前串。,最后考虑输出部分, 我们把结果输出成两个 2613 的表，每个表元素是相应字母偶的出现次数： * a b c d e . m a b . z * n o p q r . z a b . 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 问题,八皇后问题,这是一个古老而有趣的游戏。高斯(C.F.Gauss)最早在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 ，取B中下一个符号继续试探, 即作 i=i+1 。 i=k ，说明在当前位置上所有符号都已经被试探过； 应该回溯到上一个位置, 作 m=m-1 ；然后再继续试探 3. 直到找到解；或 m=0 ，全部情况都已经被试探过为止。,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,以八皇后问题为例，考察试探过程：,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,经过863步试探，得到一组解如下：,上述试探法思想描述成如下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(); ,从上例可以看出, 穷举法与试探法的着眼点及主要区别在于: 穷举法是举出全部可能的格局，对每种格局进行检验, 使合格者入选，不合格者淘汰。 试探法是从初始满足条件的格局开始，逐步前进。每前进一步都判断子格局是否合适。 若当前子格局合适则进入下一级; 若当前子格局不合适则选同一级的下一个子格局; 但是若同级子格局已全部试探完毕, 则回溯到上一级 直到当前子格局够长为止。,显然穷举法的运算量比试探法要大的多。因为它要考虑一切情况的排列，而试探法可以在中间丢掉大量的不合格排列。 事实上许多问题的穷举法是不适用的, 八皇后问题穷举法有 种排列，把每一种情况都排出来，并检验其是否合格显然是不可能的。 在上述算法中, 不论是穷举法还是试探法，都是用循环选代的方式给出的解法。循环程序可以用递归来表示。 不论穷举法还是试探法都可以写成递归形式:,八皇后 穷举法的递归实现,用穷举法实现八皇后问题, 可以抽象的描述为：在数组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=0 时检验输出并退出递归。 由此得递归实现八皇后问题的穷举算法及递归程序,int A 9 ; bool check(); /* 检查某格局是否合格的函数, 分程序略 */ void out() ; /* 输出函数, 分程序略 */ void queen( int r ) int i ; for ( i=1; i0 ) 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 的循环上； “回溯” 则体现在递归出口的返回上。,/* PROGRAM eightqueen4 */ int A 9 ; bool check( int m ); /*检查某格局是否合格的函数 */ void out(void) ; /* 输出函数 */ void queen( int r ) /* 试探法 */ int i; for ( i=1; i0 ) 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; ,Debruijn 问题,如图由 个二进制数字0、1组成一个环。使 个3位的二进制数: 000 0 001 1 010 2 011 3 100 4 101 5 110 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 ; / 记录环的长度 int A 256 ; /* 保存环,限制输入 n 最大为 8 */ bool check( int u ) ; /* 检查A0Au的个n位整数是否不同，略 */ void out() ; /* 输出A数组，略 */ int power(int w ) ； /* 求 nn ，略 */ void next ( int m