c程序设计第二章

C程序设计主讲人：袁丽燕大里仁基础教学部第二章：算法—程序的灵魂1什么是算法2算法的特性3算法的表示4结构化程序设计方法一个程序主要包括两方面的信息：对数据的描述：在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式。即数据结构（datastructure)对操作的描述：即要求计算机进行操作的步骤，也就是算法(algorithm)著名计算机科学家沃思提出的一个公式：算法+数据结构=程序算法就是解决问题的思路。有好的算法，才会有好的程序。算法是程序的精髓。类比于我们平常用的汉语，我们都能看懂普通的文字，但不是每个会说普通话的人都能写出漂亮的文章。数据是操作的对象;操作的目的是对数据进行加工处理，以得到期望的结果一个程序除了算法和数据结构这主要要素外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示算法、数据结构、程序设计方法和语言工具是一个程序设计人员应具备的知识算法是解决“做什么”和“怎么做”的问题程序中的操作语句，是算法的体现不了解算法就谈不上程序设计一、什么是算法广义地讲：为解决一个问题而采取的方法和步骤，就称为算法。例如：描述太极拳动作的图解，就是太极拳的算法。一首歌曲的乐谱，也可以称为该歌曲的算法。计算机能执行的算法，为计算机算法。其可分为两大类别：数值运算算法和非数值运算算法。对同一个问题，可以有不同的解题方法和步骤为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法数值运算的目的是求数值解非数值运算包括的面十分广泛，最常见的是用于事务管理领域例1、求1*2*3*4*5。例2、有50个学生，要求输出成绩在80分以上的学生的学号和成绩。例3、给出一个大于或等于3的正整数，判断它是不是一个素数。二、算法的特性有穷性：一个算法应包含有限的操作步骤，而不能是无限的。有穷性往往指“在合理的范围之内”。“合理限度”由人们的常识和需要判定。确定性：算法的每一个步骤都应当是确定的，不应当含糊和模棱两可。也就是说算法的含义应当是唯一的，而不可以产生“歧义性”有零个或多个输入：所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法可以有两个或多个输入，也可以没有输入。有一个或多个输出：算法的目的是为了求解，“解”就是输出。但算法的输出并不一定就是计算机的打印输出或屏幕输出，一个算法得到的结果就是算法的输出，没有输出的算法是没有意义的。有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果。三、算法的表示用自然语言表示算法用流程图表示算法三种基本结构和改进的流程图用N-S流程图表示算法用伪代码表示算法用计算机语言表示算法（1）用自然语言表示算法用自然语言表示通俗易懂，但文字冗长，容易出现歧义性用自然语言描述包含分支和循环的算法，不很方便除了很简单的问题外，一般不用自然语言（2）用流程图表示算法流程图是用一些图框表示各种操作。x≧0Y……N……一个入口两个出口菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立决定如何执行其后的操作。连接点（小圆圈）是用于将画在不同地方的流程线连接起来。位置不够防止交叉例、求1*2*3*4*5。将该算法用流程图表示。开始1t2it*iti+1ii5Y结束N如果需要将最后结果输出:开始1t2it*iti+1ii5YN输出t结束如果需要将最后结果输出:例、求1*2*3*4*5。将该算法用流程图表示。例、判定2000—2500年中的每一年是否闰年，将结果输出。将该算法用流程图表示。开始year不能被4整除2000yearNyear不能被100整除Yyear是闰年Yyear不是闰年Nyear不能被400整除Yyear不是闰年Nyear是闰年year+1yearyear2500NY结束1.通过以上几个例子可以看出流程图是表示算法的较好的工具。2.一个流程图包括以下几部分：(1)表示相应操作的框(2)带箭头的流程线(3)框内外必要的文字说明3.流程线不要忘记画箭头，否则难以判定各框的执行次序。（3）三种基本结构和改进的流程图1.传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制使用者可以毫不受限制地使流程随意地转来转去，使人难以理解算法的逻辑2.三种基本结构(1)顺序结构AB（2）选择结构pYANBpYAN（3）循环结构①当型循环结构p1YAN0xx5Y输出x的值x+1xN输出1,2,3,4,5②直到型循环结构Ap2NY0xx+1x输出x的值x≧5NY输出1,2,3,4,5以上三种基本结构，有以下共同特点：(1)只有一个入口(2)只有一个出口一个判断框有两个出口一个选择结构只有一个出口(3)结构内的每一部分都有机会被执行到。也就是说，对每一个框来说，都应当有一条从入口到出口的路径通过它(4)结构内不存在“死循环”由以上3种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。由三种基本结构派生出来的结构：Ap2YBN根据表达式p的值进行选择AB…MN（4）用N-S流程图表示算法AB顺序结构ABYNp选择结构A当p1成立循环结构（当型）A直到p2成立循环结构（直到型）例：求5!算法用N-S图表示。1t2it*iti+1i直到i5输出t例:将50名学生中成绩高于80分者的学号和成绩输出。将该算法用N-S图表示。1i输入ni、gii+1i直到i501igi≧80是输出ni,gi否i+1i直到i50例:将判定闰年的算法用N-S图表示一个结构化的算法是由一些基本结构顺序组成的在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法（5）用伪代码表示算法伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用例:求5!。begin(算法开始)1t2iwhilei≤5{t*iti+1i}printtend(算法结束)例:求10019914131211begin1sum2deno1signwhiledeno≤100{(-1)*signsignsign*1/denotermsum+termsumdeno+1deno}printsumend（6）用计算机语言表示算法要完成一项工作，包括设计算法和实现算法两个部分。设计算法的目的是为了实现算法。不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。例:将算法（求5!）用C语言表示。#includestdio.hintmain(){inti,t;t=1;i=2;while(i=5){t=t*i;i=i+1;}printf(%d\n,t);return0;}例:将算法（求多项式的值）用C语言表示。10019914131211#includestdio.hintmain(){intsign=1;doubledeno=2.0,sum=1.0,term;while(deno=100){sign=-sign;term=sign/deno;sum=sum+term;deno=deno+1;}printf(%f\n,sum);return0;}四、结构化程序设计方法结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。结构化程序设计方法的基本思路是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。采取以下方法保证得到结构化的程序：（1）自顶向下；（2）逐步细化；（3）模块化设计；（4）结构化编码。用三种基本结构组成的程序是结构化程序自顶向上，逐步细化：将问题求解由抽象逐步具体化的设计过程。比如设计房屋，先进行整体规划，然后确定建筑物方案，再进行各个部分的设计，最后进行细节的设计（门窗，楼道等），而绝不会在没有整体方案之前先设计楼道和厕所。而在完成设计，有了图纸之后，在施工阶段则是自下而上实施的，用一砖一瓦实现一个局部，最后由各个部分组成一个建筑物。模块化设计：“分而治之”的思想，把大任务分为若干子任务。程序中的子模块在C语言中通常是用函数来实现。结构化编码：将已设计好的算法用计算机语言来表示，即根据已经细化的算法正确写出计算机程序。结构化程序设计步骤一、确定算法：分析问题（建立数学模型，利用公式),写出算法描述（比如流程图）二、编写程序：用计算机语言写出实现算法的程序三、上机调试：输入（编辑）程序---编译、连接、执行程序---输出结果举例：《算经》中提出“百鸡问题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？（体会编程步骤）(1)分析：cocks+hens+chicks=1005*cocks+3*hens+chicks/3=100其中，0≤cocks≤19,0≤hens≤33,0≤chicks≤100累试法（枚举法）求解算法描述：cocks=0当cocks≤19时｛找满足题意的hens,chicks数cocks加1｝细化cocks=0当cocks≤19时｛hens=0当hens≤33时{找满足题意的chicks数hens加1}hens加1｝细化cocks=0当cocks≤19时｛hens=0当hens≤33时｛chicks=100-cocks-hens如果（5*cocks+3*hens+chicks/3=100）则输出hens加1}cocks加1}(2)计算机语言写出程序intmain(){intcocks=0.hens,chicks;while(cocks=19){hens=0;while(hens=33){chicks=100-cocks-hens;if(5*cocks+3*hens+chicks/3==100)printf(“%d%d%d\n”,cocks,hens,chicks);hens++;}cocks++;}return0;}#includestdio.h