资源预览内容
第1页 / 共73页
第2页 / 共73页
第3页 / 共73页
第4页 / 共73页
第5页 / 共73页
第6页 / 共73页
第7页 / 共73页
第8页 / 共73页
第9页 / 共73页
第10页 / 共73页
亲,该文档总共73页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第4章 程序设计知识,4.1 程序的概念,程序是可以被计算机处理的指令序列。通常,程序是为完成一项任务、由汇编语言或高级语言编写的代码的集合。程序设计是根据所提出的任务,用某种程序设计语言编制一个能正确完成该任务的计算机程序。,4.1.1 程序的特性,著名的计算机科学家沃思(Nikiklaus Wirth)提出一个公式:程序=数据结构+算法。 现在又有很多专家对这个公式加以扩充:程序=算法+数据结构+程序设计方法+语言工具和环境。,所有程序(包括计算机程序)都有一些共同的性质,这些性质主要包括: (1)指令是顺序执行的。 (2)程序的执行都有一个结果。 (3)程序总是要对某些对象进行操作。,(4)有的程序要加入对操作对象的说明。 (5)有时指令要求执行者做出判断。 (6)一条或一组指令可能需要执行多次。,4.1.2 程序设计语言,多数专家认为,计算机语言大致可以分为以下五代。 1第一代语言机器语言 2第二代语言汇编语言 3第三代语言高级语言 4第四代语言 5第五代语言,程序设计离不开算法,算法指导程序设计,算法是程序的灵魂。因此程序设计的大致步骤如下。 (1)问题定义 (2)算法设计 (3)算法表示 (4)程序编制 (5)程序调试、测试及资料编制,4.2 算 法,精确地讲,算法是被精确定义的一系列规则,这些规则规定了解决特定问题的一系列操作顺序,以便在有限步骤内产生出所求问题的解答。,4.2.1 算法的特点,1确定性 2能行性 3有穷性 4输入 5输出,通常,表示算法的方法有以下四种。 1自然语言描述法 2伪码表示法 伪码是用介于自然语言和计算机语言之间的文字和符号来描述算法,类似一篇短文,它把算法的思想表达清楚。,4.2.2 算法的表示,例如求三个数中最大值问题,用伪码可表示为: IF ab THEN把 a交给 max ELSE 把b交给 max IF maxc THEN输出最大值 max ELSE 输出最大值c,3N-S图表示法,图4-1 求三个数中最大值问题的N-S图表示,4流程图表示法,图4-2 流程图表示法常用图例,常用的图例主要有图4-2中所示的几种。,图4-3 求三个数最大值问题的流程图表示,例4-1 用辗转相除法求两个正整数的最大公约数。 用自然语言描述(其中S1,S2,分别表示步骤1,步骤2,):,S1. 输入两个正整数m和n; S2. 比较m和n,如m小于n,则二者交换值,保证m是最大数。m当作相除时的分子; S3. 求m除以n的余数r; S4. 如余数r=0,转S6; S5. 把除数n作为新的分子m,余数r作为新的分母n,然后转S3; S6. 打印除数n,n即为最大公约数。, 用伪码描述: input m, n if mn then 交换m 和 n r=mod (m,n) while r0 do m=n n=r r=mod (m,n) end do print n,其中,符号mod(m,n)代表m除以n的余数。 用N-S图描述,如图4-4所示。 用流程图描述,如图4-5所示。,图4-4 例4-1的N-S图描述,图4-5 例4-1的流程图描述,4.3 结构化程序设计方法,4.3.1 结构化程序设计概念 结构化程序设计的基本方法是:在设计程序时,本着从上到下、逐步求精的原则,将一个大的原始问题分解为多个可独立进行编程的小问题(即小模块),如果某个模块还未精细到能直接进行编程的程度,则继续对它进行分解,直至能直接编程为止。每个模块只有一个入口和一个出口。,结构化程序设计方法有三种基本的控制结构,即:顺序结构、选择结构和循环结构。 这三种基本结构可以用图表示法加以描述。,4.3.2 结构化程序设计的三种基本结构,(1)顺序结构,1用N-S图表示,(2)选择结构,(3)循环结构 while结构, repeat_until结构,2用流程图表示,(1)顺序结构 (2)选择结构,又有如下三种形式: if结构(单路选择结构) if-else结构(双路选择结构) switch结构 (多路选择结构),图4-6 顺序结构的流程图表示,图4-7 if结构的流程图表示,图4-8 if-else结构的流程图表示,图4-9 switch结构的流程图表示,(3)循环结构 while结构 do-while结构 for结构,图4-10 while结构的流程图表示,图4-11 do-while结构的流程图表示,图4-12 for结构的流程图表示,结构化程序设计的规则有4条: (1)从最简单的流程图开始; (2)任何矩形框都可以被两个按顺序放置的矩形框取代; (3)任何矩形框都可以被任何结构取代; (4)规则(2)和规则(3)可按任何顺序运用多次。,图4-13 从最简结构出发反复使用规则(2)和规则(4),图4-14 对最简结构使用规则(3)和规则(4),例4-2 用二分法求方程的解。,图4-16 二分法求方程的解,可写出其算法如下(S表示Step,即步骤): S1. 读入下界a、上界b。 S2. 执行循环体: S2.1 取中点h=(a+b)。 S2.2 如f (h)和f (a)同号,则以h为新的下界a,否则以h为新的上界b。 S2.3 如满足精度要求 | ab | ,则向下执行S3,否则返回S2.1继续执行。,S3. 取x=(a+b)作为方程的近似根。 S4. 打印输出x。 S5. 结束。 如何判断f (h)和f (a)是否同号呢?可对算法S2.2进一步细化为: S2.2.1 计算f (a)。 S2.2.2 计算f (h)。 S2.2.3 如f (a)*f (h)0,则以h为新的下界a,否则以h为新的上界b。,图4-17 例4-2的流程图,图4-18 例4-2的N-S图表示,4.4 程序设计中的几种常用算法,4.4.1 穷举法 穷举法又称枚举法、试探法。如果问题解的值域是有限的、确定的和有序的,则可以把其中每一个值都拿来试一下,看是否符合所给条件。,例4-3 百鸡问题。用100元钱买100只鸡,已知每只公鸡5元,每只母鸡3元,3只小鸡1元,问能买的公鸡、母鸡和小鸡各是多少只? 设能买公鸡x只,母鸡y只,小鸡z只,按题意可列出下列方程组:,公鸡x的取值范围是0到20 ,同样母鸡y的取值范围是0到33;小鸡z没有取值的主动权,它只能在x和y的值确定之后方可决定自己的值,z=100xy。 当x、y、z各取一值之后,还要验证是否符合总钱数的限制条件: 100=5x+3y+(100xy)/3,图4-19 例4-3的流程图,图4-20 例4-3的N-S图,迭代法主要用于对方程的求解,其基本思想是:首先给定一个近似解,然后根据该方程的迭代公式可以求出下一个近似解,后者比前一个近似解更接近于真实解,这样一步步地逼近真实解。这个过程就称为迭代过程。 迭代算法最重要的工作是确定迭代公式。,4.4.2 迭代法,具体说,迭代法求解过程如下: 首先选取一个x的近似根x0,从x0出发,代入f2,即f2(x0),求出f2(x0)的值,设为c0;再解方程f1(x)=c0,可以得到下一个近似根x1。, 将上次得到的近似根再代入f2(x),得到一个值ci,再解方程f1(x)=ci,又得到一个近似根xi。 重复的计算,可以得到一系列近似根x1, x2, xi, xi+1, xn,。 如果方程有根,则该数列会收敛于方程的根。若对于预先给定的正数,有|xnxn1|时,则可认为xn即为方程的根。,例4-5 用迭代法求方程 把f(x) = 0分成两个函数,使得f1(x) f2(x) = 0。 令:f1(x) = x 本题算法如图4-23和图4-24所示。,的根。,图4-23 例4-5的流程图,图4-24 例4-5的N-S图,递推法是从简单问题开始,一步步地向后推导。在推导的过程中,每一步的解都是确定的,并可用来判断是否达到了所要求的条件。递推法常用于对级数问题的求解。,4.4.3 递推法,例4-7 求,直到第n项小于106为止。,本例中,设第n项为tn,第n+1项为tn+1,则,,而第1项,。,如图4-27和图4-28所示。,和递推法的方向相反,递归法不是由前向后、每一步都给出一个确定的值,而是从总体上把握问题的求解。,4.4.4 递归法,递归算法包含两个过程:第一个过程为递归调用过程,即上面所说的不断简化问题的过程;第二个过程为回退过程,即递归调用达到最简单的、一步可以解决的边界条件时,就要一步步地回退,在回退的过程中进行求解,直至达到原始问题。当回退到原始问题时,问题的解就出来了。,图4-27 例4-7的流程图,图4-28 例4-7的N-S图,例4-8 有些数学问题本身就具有很好的递归性质。如求阶乘问题。 由数学公式,求n的阶乘问题可以转化为求n1的阶乘问题;而求n1的阶乘问题又可转化为求n2的阶乘问题。这样一步步化简,最后当n=1时就可由第一式直接给出结果。,4.5 程 序 调 试,程序中的错误按性质分为以下三种。 (1)编译错误,即语法错误。 (2)运行错误。 (3)逻辑错误。 查找程序中的错误,诊断其准确位置并予以改正,这就是程序调试。程序调试分为人工查错与机器调试。,人工查错一般有两种方式:静态查错与动态模拟查错。 1静态查错 直接对源代码进行仔细检查。主要检查程序中的语法规则和逻辑结构是否正确,以及可能存在的拼写错误。,4.5.1 人工查错,静态查错可以采用“先局部、后整体”的方式。 (1)查接口约定,主要检查模块间的信息交换约定是否合理,是否全面,有无矛盾、疏漏,是否按约定办事。,(2)查框图,主要是检查模块的逻辑结构,即框图的逻辑是否符合算法的要求,如分支转移条件是否完备,循环终止条件是否恰当等。 (3)查程序的语法,包括两个方面:语句正确性检查和语法正确性检查。, 语句正确性检查 语法正确性检查 2动态模拟查错 动态模拟查错是采用人工模拟机器执行程序的方法来查错。,要借助于调试工具。 1程序调试环境和调试用例 很多操作系统中都提供了程序调试系统,如DOS/Windows系统中的Debug程序、UNIX/Linux系统中的sdb程序等。,4.5.2 程序调试,调试用例是针对程序系统的功能、专门设计的一组数据。利用这组数据来检查被调试程序的功能错误、逻辑错误等出现在何处。,2常用的程序调试技术,(1)在被调试的程序中增加调试语句 常用的增加调试语句的方法如下。 回声打印 选择打印 跟踪打印 统计活动次数,(2)使用调试系统的功能 打印现场 设置断点 跟踪现场路径 综合应用以上技巧,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号