c语言第3章算法

《c语言第3章算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章算法第九讲本章主要内容¢熟悉算法的定义和算法的表示方法¢掌握结构化程序设计方法¢数据结构+算法=程序——NikiklausWirth数据的类型对数据和数据的组的操作织形式步骤2.1算法的概念¢做事情要有步骤决定成功与否¢1、算法：为解决一个问题而采取的方法和步骤。¢2、两大类别算法：数值运算算法和非数值运算算法。求数值解，算用于事务管理，法比较成熟。应用广泛。¢3、算法特征：有穷性、确定性、有效性等。¢4、算法的表示方法：可以归纳为两种——文字和图形。2.2算法的表示方法¢方法1：使用有序号的自然语言描述。¢方法2：

2、使用流程图描述。¢方法3：使用NS图描述。¢方法4：使用伪码来描述。方法1：使用有序号的自然语言描述。¢通俗易懂，但容易出现“歧义性，表示的含义不严格。（参例2.1－2.5）方法2：使用流程图描述。方法3：使用NS图描述。¢N-S图表示算法的优点：¾比文字描述直观、形象、易于理解；¾比传统流程图紧凑易画，废除了流程线，整个算法结构是由各个基本结构按顺序组成的。¢用N-S图表示的算法都是结构化的算法(它不可能出现流程无规律的跳转，而只能自上而下地顺序执行)。¢N-S图如同一个多层的盒子，又称盒图(boxdiagram)。方法

3、4：使用伪码来描述¢伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。¢优点：书写方便、格式紧凑，也比较好懂，便于向计算机语言算法(即程序)过渡。2.2结构化程序设计方法¢1966年，Bohra和Jacopini提出了以下三种基本结构，作为表示一个良好算法的基本单元。¢程序设计的三种基本结构：¾(1)顺序结构¾(2)选择结构¾(3)循环结构，有两类循环结构：•①当型(While型)循环结构•②直到型(Until型)循环顺序结构如：inta,b,c;a=1;b=2;c=a+b;流程图NS图选择结构流程图NS图先判

4、断，先执行，思考：两循环结构再判断种循环的再执行区别流程图当型(While直到型型)循环(Until型)结构循环结构NS图intnSum,i;思考：如果i的intnSum,i;初始值为100，nSum=0;两个程序的结果nSum=0;分别是多少？i=0;i=0;while(i<100)do{{nSum+=i;nSum+=i;i++;++I;}}while(i<100)当型(While型)循环结构直到型(Until型)循环¢以上三种基本结构的共同特点：¾(1)只有一个入口。¾(2)只有一个出口。¾(3)结构内的每一部分都有机

5、会被执行到。¾(4)结构内不存在“死循环”(无终止的循环)。¢由以上三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。¢每一个结构化的算法都是由一些基本结构顺序组成的；每个基本结构又可以包含其他的基本结构；基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转)。¢如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。¢例1、求1-1/2+1/3-1

6、/4+…+1/99-1/100。¾使用自然语言描述，算法可以表示如下：S1：1=>signS2：1=>sumS3：2=>denoS4：(-1)×sign=>signS5：sign×(1/deno)=>termS6：sum+term=>sumS7：deno+1=>denoS8：若deno≤100返回S4；否则算法结束。¾使用流程图描述，算法可以表示如下：¾使用NS图描述，算法可以表示如下：¾用伪代码表示的算法如下：BEGIN(算法开始)1=>sum2=>deno1=>signwhiledeno<=100{(-1)×sign=

7、>signsign×1/deno=>termsum+term=>sumdeno+1=>deno}printsumEND(算法结束)¢用三种基本结构组成的程序必然是结构化的程序。¢结构化程序设计的优点：易编、易读、易修改和易维护。¢减少了程序出错的机会，提高了程序的可靠性。¢结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。¢结构化程序设计方法的基本思路是，把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。¢结构化的程序的设计方法：¾自顶向下；¾逐步细化；¾模块化设计；

8、¾结构化编码。¢模块化设计的思想——“分而治之”。即把一个大任务分为若干个相对简单的子任务。2.3结构化程序的设计过程¢设计过程：¾1、确定算法。分析问题，建立相应的数学模型、选择公式，写出算法描述。¾2、写出源程序。¾3、上机调试。¢练习：100匹马，100块瓦，大马驮三，中马驮两，小马两个驮一块。问