算法和基本程序设计

《算法和基本程序设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章算法和基本程序设计3.1算法的概念3.2结构化程序设计方法3.3程序的基本结构3.4顺序结构程序设计3.5数据的输入输出3.6C程序的上机步骤3.1算法的概念1.定义:做任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤，就称为算法。2.计算机算法可分为两大类：数值运算算法：求解数值；非数值运算算法：事务管理领域。一个著名的公式数据结构+算法=程序数据：计算机所能识别、存储和处理的对象。数据的动态性。数据结构：确定数据对象及其存储方式，并定义在这些数据对象上的运算集合。算法：为解决一个问题而采取的方法和步骤。算法的特性1有穷性操作步骤是有限的，不是无限的。2确

2、定性每个步骤是确定的，无歧义性。3有零个或多个输入4有一个或多个输出5有效性每一步骤能有效执行，并得到确定结果。3.1.2算法的评价标准1.正确性对任何合法的输入，算法都会得出正确的结果。2.可读性可读性指算法被理解的难易程度。3.健壮性（鲁棒性）健壮性即对非法输入的抵抗能力。4.高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。二者往往是一对矛盾，常常可以用空间换时间，也可以用时间换空间。怎样表示一个算法用自然语言表示算法用流程图表示算法用N-S流程图表示算法用伪代码表示算法用计算机语言表示算法歧义性

3、，描述分支、循环算法不方便起止框输入输出框处理框判断框流程线连接点【例3.1】求三个整数的和。求三个整数和的算法流程图如图所示。开始x+y+z=>sum输出sum的值结束输入x,y,z图3.2求三个整数和的算法【例3.2】求最大公约数。m,n为正整数开始结束输入m,n求m/n的余数rr=0?n=>m,r=>n输出n是否最大公因数的算法求最大公因数的最普遍的算法是欧几里得算法，它最初是公元前由欧几里得提出来的，有时也称它为辗转相除法．表述如下：设给定m，n(m＞n)，令r0=m，r1=n，有则得rk=gcd(rk-1，rk)=gcd(rk-2，rk-1)=…=gcd(r2，

4、r3)=gcd(r1，r2)=gcd(r0，r1)=gcd(m，n)．b

5、a表示b整除a或者a整除以b则a是b的倍数，b是a的约数rk-2=qk-1qkrk+rk=(qk-1qk+1)rkS1:求1×2=2S2:求2×3=6S3:求6×4=24••••••天啊！共需999个步骤，太可怕了。案例求1×2×3×4×······×1000S1:1p(p:被乘数)S2:2i(i:乘数)S3:p×ipS4:i+1iS5:若i≤1000,返回S3；否则，结束。只需5个步骤，简单。3.2结构化程序设计的方法结构化程序设计思想采用了模块分解与功能抽象和自顶向下、分而治之的方法，从而有效地

6、将一个较复杂的程序系统设计任务分解成许多易于控制和处理的子程序，便于开发和维护，减少程序的出错概率和提高软件的开发效率。采用结构化程序设计方法应遵循以下原则。1.自顶向下即在程序设计时，先考虑总体，做出全局设计，然后再考虑细节进行局部设计，逐步实现精细化。这种方法称为“自顶向下，逐步细化”的方法。2.模块化就是将一个大任务分成若干个较小的部分，每一部分承担一定的功能，称为“功能模块”。每个模块可以分别编程和调试，然后组成一个完整的程序。模块的划分应遵循一些基本原则，如模块内部联系要紧密，关联程度要高；模块间的接口要尽可能简单，以减少模块间的数据传递。3.限制使用GOTO语

7、句结构化的程序设计方法基本思路:把一个复杂问题的求解过程分阶段进行,每个阶段处理的问题都控制在人们容易理解和处理的范围内.采用的方法:1自顶而下2逐步细化3模块化设计4结构化编码三种基本结构1顺序结构2选择结构3循环结构3.3程序的基本结构三种基本结构的特点1只有一个入口2只有一个出口pA3结构内的每一部分都有机会被执行到AB4结构内没有死循环顺序结构的流程图符号ABabAB传统流程图N-S流程图选择结构的流程图符号Ap成立不成立BAp成立不成立传统流程图选择结构的流程图符号（续）成立不成立ApBN-S流程图循环结构的流程图符号Ap1成立不成立ab不成立Ap2成立ab传统

8、流程图While型Until型循环结构的流程图符号（续）直到p1成立A当p1成立AWhile型Until型N-S流程图一个有用的结论已经证明：三种基本结构的顺序组成可以表示任何复杂的算法结构。由基本结构构成的算法，属于“结构化”算法。有关结构化算法的总结一个结构化的算法是由一些基本结构顺序组成的；基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构的范围之内（如循环中的流程跳转）；一个非结构化算法可以用一个等价的结构化算法代替，其功能不变。如果一个算法不能分解为若干个节本结构，则它必然不是一个结构化算法。3.4顺