《C语言程序设计 教学课件 ppt 作者 孟庆昌 陈海鹏 马鸣远 刘振英 第4章 程序设计知识》由会员分享，可在线阅读，更多相关《C语言程序设计 教学课件 ppt 作者 孟庆昌 陈海鹏 马鸣远 刘振英 第4章 程序设计知识（73页珍藏版）》请在金锄头文库上搜索。
1、第4章 程序设计知识,4.1 程序的概念,程序是可以被计算机处理的指令序列。通常，程序是为完成一项任务、由汇编语言或高级语言编写的代码的集合。程序设计是根据所提出的任务，用某种程序设计语言编制一个能正确完成该任务的计算机程序。,4.1.1 程序的特性,著名的计算机科学家沃思（Nikiklaus Wirth）提出一个公式：程序=数据结构+算法。 现在又有很多专家对这个公式加以扩充：程序=算法+数据结构+程序设计方法+语言工具和环境。,所有程序（包括计算机程序）都有一些共同的性质，这些性质主要包括： （1）指令是顺序执行的。 （2）程序的执行都有一个结果。 （3）程序总是要对某些对象进行操作。,（
2、4）有的程序要加入对操作对象的说明。 （5）有时指令要求执行者做出判断。 （6）一条或一组指令可能需要执行多次。,4.1.2 程序设计语言,多数专家认为，计算机语言大致可以分为以下五代。 1第一代语言机器语言 2第二代语言汇编语言 3第三代语言高级语言 4第四代语言 5第五代语言,程序设计离不开算法，算法指导程序设计，算法是程序的灵魂。因此程序设计的大致步骤如下。 （1）问题定义 （2）算法设计 （3）算法表示 （4）程序编制 （5）程序调试、测试及资料编制,4.2 算 法,精确地讲，算法是被精确定义的一系列规则，这些规则规定了解决特定问题的一系列操作顺序，以便在有限步骤内产生出所求问题的解答
3、。,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
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)
5、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 结构化程序设计概念 结构化程序设计的基本方法是：在设计程序时，本着从上到下、逐步求精的原则，将一个大的原始问题分解为多个可独立进行编程的小问题（即小模块），如果某个模块还未精细到能直接进行编程的程度，则继续对它进行分解，直至能直接编程为止。每个模块只有一个入口和一个出口。,结构化程序设计方法有三种基本的控制结构，即：顺序结构、选择结构和循环结构。
6、这三种基本结构可以用图表示法加以描述。,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结构
7、的流程图表示,图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)
8、。 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 穷举法
9、穷举法又称枚举法、试探法。如果问题解的值域是有限的、确定的和有序的，则可以把其中每一个值都拿来试一下，看是否符合所给条件。,例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
10、-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
11、, 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为止。,本例中，
12、设第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
13、的阶乘问题可以转化为求n1的阶乘问题；而求n1的阶乘问题又可转化为求n2的阶乘问题。这样一步步化简，最后当n=1时就可由第一式直接给出结果。,4.5 程 序 调 试,程序中的错误按性质分为以下三种。 （1）编译错误，即语法错误。 （2）运行错误。 （3）逻辑错误。 查找程序中的错误，诊断其准确位置并予以改正，这就是程序调试。程序调试分为人工查错与机器调试。,人工查错一般有两种方式：静态查错与动态模拟查错。 1静态查错 直接对源代码进行仔细检查。主要检查程序中的语法规则和逻辑结构是否正确，以及可能存在的拼写错误。,4.5.1 人工查错,静态查错可以采用“先局部、后整体”的方式。 （1）查接口约定
14、，主要检查模块间的信息交换约定是否合理，是否全面，有无矛盾、疏漏，是否按约定办事。,（2）查框图，主要是检查模块的逻辑结构，即框图的逻辑是否符合算法的要求，如分支转移条件是否完备，循环终止条件是否恰当等。 （3）查程序的语法，包括两个方面：语句正确性检查和语法正确性检查。, 语句正确性检查 语法正确性检查 2动态模拟查错 动态模拟查错是采用人工模拟机器执行程序的方法来查错。,要借助于调试工具。 1程序调试环境和调试用例 很多操作系统中都提供了程序调试系统，如DOS/Windows系统中的Debug程序、UNIX/Linux系统中的sdb程序等。,4.5.2 程序调试,调试用例是针对程序系统的功能、专门设计的一组数据。利用这组数据来检查被调试程序的功能错误、逻辑错误等出现在何处。,2常用的程序调试技术,（1）在被调试的程序中增加调试语句 常用的增加调试语句的方法如下。 回声打印 选择打印 跟踪打印 统计活动次数,（2）使用调试系统的功能 打印现场 设置断点 跟踪现场路径 综合应用以上技巧,
