C语言程序设计第二章算法

《C语言程序设计第二章算法》由会员分享，可在线阅读，更多相关《C语言程序设计第二章算法（38页珍藏版）》请在金锄头文库上搜索。

1、 C程序设计程序设计主讲人：袁丽主讲人：袁丽燕大里仁基础教学部任踊娶廉难贝钱签币佬狠蔓巍艺捅翁絮乙术鲤翻向侠哪烟魏主泣摈嫩遏揽C语言程序设计第二章 算法C语言程序设计第二章 算法第二章：算法第二章：算法程序的灵魂程序的灵魂1 什么是算法什么是算法2 算法的特性算法的特性3 算法的表示算法的表示4 结构化程序设计方法结构化程序设计方法沃酷户镰粗棘邑度孟秃老孽锦面侩思烫吹诸磋陛杜仁瓷为颠懂怨参侥漆卫C语言程序设计第二章 算法C语言程序设计第二章 算法一个程序主要包括两方面的信息：一个程序主要包括两方面的信息：u 对数据的描述：在程序中要指定用到哪些数据以及这些数据对数据的描述：在程序中要指定用到哪

2、些数据以及这些数据的类型和数据的组织形式。即数据结构（的类型和数据的组织形式。即数据结构（data structure)data structure)u 对操作的描述：即要求计算机进行操作的步骤，也就是算法对操作的描述：即要求计算机进行操作的步骤，也就是算法(algorithm)(algorithm)著名计算机科学家沃思提出的一个公式：算法+数据结构=程序 算法就是解决问题的思路。有好的算法，才会有好的程序。算法是程序的精髓。算法就是解决问题的思路。有好的算法，才会有好的程序。算法是程序的精髓。类比于我们平常用的汉语，我们都能看懂普通的文字，但不是每个会说普通话的人类比于我们平常用的汉语，我们

3、都能看懂普通的文字，但不是每个会说普通话的人都能写出漂亮的文章。都能写出漂亮的文章。 数据是操作的对象数据是操作的对象; ;操作的目的是对数据进行加工处理，操作的目的是对数据进行加工处理，以得到期望的结果以得到期望的结果遥科铭罗葵硅浆减夕坠胜底篷短娩妨宇淖便朱任撼园赠匪茄掏损禹役稀多C语言程序设计第二章 算法C语言程序设计第二章 算法 一个程序除了算法和数据结构这主要要素外，还应当采用一个程序除了算法和数据结构这主要要素外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言结构化程序设计方法进行程序设计，并且用某一种计算机语言表示表示 算法算法、数据结构数据结构、程序设计方法程序

4、设计方法和和语言工具语言工具是一个程序设是一个程序设计人员应具备的知识计人员应具备的知识u算法是解决算法是解决“做什么做什么”和和“怎么做怎么做”的问题的问题u程序中的操作语句，是算法的体现程序中的操作语句，是算法的体现u不了解算法就谈不上程序设计不了解算法就谈不上程序设计硝乙儒学床拾矽四盏唬脆扇颠硕铱摆假馈慌教纫姥醒锄滴俗彤弄核岿壁戈C语言程序设计第二章 算法C语言程序设计第二章 算法一、什么是算法一、什么是算法 广义地讲：为解决一个问题而采取的方法和步骤，就称为算法。广义地讲：为解决一个问题而采取的方法和步骤，就称为算法。例如：描述太极拳动作的图解，就是太极拳的算法。一首歌曲的例如：描述太

5、极拳动作的图解，就是太极拳的算法。一首歌曲的乐谱，也可以称为该歌曲的算法。乐谱，也可以称为该歌曲的算法。 计算机能执行的算法，为计算机算法。其可分为两大类别：计算机能执行的算法，为计算机算法。其可分为两大类别：数值运算数值运算算法和算法和非数值运算非数值运算算法。算法。对同一个问题，可以有不同的解题方法和步骤对同一个问题，可以有不同的解题方法和步骤为了有效地进行解题，不仅需要保证算法正确，还要考虑算法为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法的质量，选择合适的算法数值运算数值运算的目的是求数值解的目的是求数值解非数值运算非数值运算包括的面十分广泛，最常见的是用

6、于事务管理领域包括的面十分广泛，最常见的是用于事务管理领域筏野泥吃禹蕾含芹擎趁缮影簿宛芭例价疥树撂拉琐贴循诣窘酿电夺创斩判C语言程序设计第二章 算法C语言程序设计第二章 算法例例1 1、求、求1*2*3*4*51*2*3*4*5。可晦项粥驾中忘莲泌锥爆滤仑赛卸疟遣募杀荆嗅罪榆安哈叹辜潞逐凡俘舀C语言程序设计第二章 算法C语言程序设计第二章 算法例例2 2、有、有5050个学生，要求输出成绩在个学生，要求输出成绩在8080分以上的学生的学号和成绩。分以上的学生的学号和成绩。措栽怜戮蝴亮簇骑鞘晚拇战谈届庄秧绪惟烫桐徘补椰的毫如亥契掩巡修吉C语言程序设计第二章 算法C语言程序设计第二章 算法例例3

7、3、给出一个大于或等于、给出一个大于或等于3 3的正整数，判断它是不是一个素数。的正整数，判断它是不是一个素数。帝懦形船誊哗多临代泡屁脐倔公稍后锄刀曲齐刮槽瓮捅兜丑颠钮茬样埂茂C语言程序设计第二章 算法C语言程序设计第二章 算法二、算法的特性二、算法的特性u有穷性有穷性：一个算法应包含有限的操作步骤，而不能是无限的。一个算法应包含有限的操作步骤，而不能是无限的。有穷性往往指有穷性往往指“在合理的范围之内在合理的范围之内”。“合理限度合理限度”由人们的常识由人们的常识和需要判定。和需要判定。u确定性确定性：算法的每一个步骤都应当是确定的，不应当含糊和模棱算法的每一个步骤都应当是确定的，不应当含糊

8、和模棱两可。也就是说算法的含义应当是唯一的，而不可以产生两可。也就是说算法的含义应当是唯一的，而不可以产生“歧义性歧义性”u有零个或多个输入有零个或多个输入：所谓输入是指在执行算法时需要从外界取得所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法可以有两个或多个输入，也可以没有输入。必要的信息。一个算法可以有两个或多个输入，也可以没有输入。u有一个或多个输出有一个或多个输出：算法的目的是为了求解，算法的目的是为了求解，“解解”就是输出。就是输出。但算法的输出并不一定就是计算机的打印输出或屏幕输出，一个算法但算法的输出并不一定就是计算机的打印输出或屏幕输出，一个算法得到的结果就是算法的输

9、出，没有输出的算法是没有意义的。得到的结果就是算法的输出，没有输出的算法是没有意义的。u有效性有效性：算法中的每一个步骤都应当能有效地执行，并得到确定算法中的每一个步骤都应当能有效地执行，并得到确定的结果。的结果。酒壮诺鞍挎困冰棒掸涨缕蜕卡讹篡欧遵好乱生各闷和矮望斜钵他手刑脖茶C语言程序设计第二章 算法C语言程序设计第二章 算法三、算法的表示三、算法的表示 用自然语言表示算法用自然语言表示算法 用流程图表示算法用流程图表示算法 三种基本结构和改进的流程图三种基本结构和改进的流程图 用用N-SN-S流程图表示算法流程图表示算法 用伪代码表示算法用伪代码表示算法 用计算机语言表示算法用计算机语言表

10、示算法繁箔塑蕾窿冈月恩播钞忻恩讣条贪婴义辅栗联糯艇耶步吏俊馋诸爱云孕雍C语言程序设计第二章 算法C语言程序设计第二章 算法（1）用自然语言表示算法）用自然语言表示算法n用自然语言表示通俗易懂，但文字冗长，容易出现歧义性用自然语言表示通俗易懂，但文字冗长，容易出现歧义性n用自然语言描述包含分支和循环的算法，不很方便用自然语言描述包含分支和循环的算法，不很方便n除了很简单的问题外，一般不用自然语言除了很简单的问题外，一般不用自然语言 （2）用流程图表示算法）用流程图表示算法流程图是用一些图框表示各种操作。流程图是用一些图框表示各种操作。嘲吮旦陌叁勤瑟钵谷念熙助文彻祝伐纪走麦毒慷卡剂孵绸断哀贸稿篱肮

11、坟C语言程序设计第二章 算法C语言程序设计第二章 算法x 0YN一个入口一个入口两个出口两个出口 菱形框的作用是对一个给定的条件进行判断，根据给定的条件菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立决定如何执行其后的操作。是否成立决定如何执行其后的操作。性化德攘翰劣捏扇繁冬裔备祖缅屡滑彪鸿播五侯鬼塞丝除秋厂态磨堵因音C语言程序设计第二章 算法C语言程序设计第二章 算法 连接点（小圆圈）是用于将画在不同地方的流程线连接起连接点（小圆圈）是用于将画在不同地方的流程线连接起来。来。位置不够位置不够防止交叉防止交叉涌娩闰经郎窑碌桑嘲晌咸秉帛埂尤夷樟占蔓痰人擂丰式喇恒古橙佳侍陕哈C语言程

12、序设计第二章 算法C语言程序设计第二章 算法例、求例、求1*2*3*4*51*2*3*4*5。将该算法用流程图表示。将该算法用流程图表示。开始开始1t2it*iti+1ii5Y结束结束N如果需要将最后结果输出如果需要将最后结果输出: :葡倡焕骗燎依泵夏铭清动嫡盒柞几呛溉炽钦皑乾侯喷盔秃纵窝亚接央沮殉C语言程序设计第二章 算法C语言程序设计第二章 算法开始开始1t2it*iti+1ii5YN输出输出t结束结束如果需要将最后结果输出如果需要将最后结果输出: :例、求例、求1*2*3*4*51*2*3*4*5。将该算法用流程图表示。将该算法用流程图表示。胸帝户削昭丹钥毙单福瑚尼沁睛痰忘沪谤如蔬忙透眷

13、蘑睦式漓怎呈壁体稿C语言程序设计第二章 算法C语言程序设计第二章 算法例、例、 判定判定2000200025002500年中的每一年是否闰年，将结果输出。年中的每一年是否闰年，将结果输出。 将该算法用流程图表示。将该算法用流程图表示。开始开始year不能不能被被4整除整除2000yearNyear不能不能被被100整除整除Yyear是闰年是闰年Yyear不是闰年不是闰年Nyear不能不能被被400整除整除Yyear不是闰年不是闰年Nyear是闰年是闰年year+1yearyear2500NY结束结束习宛缉用坑诺犯缄独颇迫葡但驯踏昼尧麓策倘良泽恒田锤履奉睹雀檀广拭C语言程序设计第二章 算法C语言

14、程序设计第二章 算法1.1.通过以上几个例子可以看出流程图是表示算法的较好的工通过以上几个例子可以看出流程图是表示算法的较好的工具。具。2.2.一个流程图包括以下几部分：一个流程图包括以下几部分：(1) (1) 表示相应操作的框表示相应操作的框(2) (2) 带箭头的流程线带箭头的流程线(3) (3) 框内外必要的文字说明框内外必要的文字说明3.3.流程线不要忘记画箭头，否则难以判定各框的执行次序。流程线不要忘记画箭头，否则难以判定各框的执行次序。请颈汐滔森展尼股竣蔡亲疲雪琼治峰捎惶接薄披庭遇痒昂卸食稀咐解啮女C语言程序设计第二章 算法C语言程序设计第二章 算法 （3）三种基本结构和改进的流程

15、图）三种基本结构和改进的流程图1.1.传统流程图的弊端传统流程图的弊端n传统的流程图用流程线指出各框的执行顺序，对流程线传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制的使用没有严格限制n使用者可以毫不受限制地使流程随意地转来转去，使人使用者可以毫不受限制地使流程随意地转来转去，使人难以理解算法的逻辑难以理解算法的逻辑2.2.三种基本结构三种基本结构(1)(1)顺序结构顺序结构AB殖牲筷绸枝折岩跌贯厢塌呈渭耿噶蜜镭翅或哦氟贺函垛菲溜答隆床釜脓售C语言程序设计第二章 算法C语言程序设计第二章 算法（2 2）选择结构）选择结构pYANBpYAN（3 3）循环结构）循环结构 当型循

16、环结构当型循环结构p1YAN凭阜潦誓吨匿宋汾丛许愚闹穿譬噬双驾柄著虹艇嗽界架摆筑猴眺熊戳艺湾C语言程序设计第二章 算法C语言程序设计第二章 算法0xx5输出输出t构仪把曹鬼落习戚锈牲威梢妊胳闰钱蚀辕顺竿惑糯粱盒银踞贱乒衫闲脊泵C语言程序设计第二章 算法C语言程序设计第二章 算法例例: :将将5050名学生中成绩高于名学生中成绩高于8080分者的学号和成绩输出。将该算法用分者的学号和成绩输出。将该算法用N-SN-S图表示。图表示。1i输入输入ni、gii+1i直到直到i501igi 80是是输出输出ni,gi否否i+1i直到直到i50咕沧喝仲帽损寥忱光锗悯雁赊牧棱叮驯撰贯故珠翻哄谐顾黑悸铱铝遮淤

17、冯C语言程序设计第二章 算法C语言程序设计第二章 算法例例: :将判定闰年的算法用将判定闰年的算法用N-SN-S图表示图表示稗坠咙凑滦体啼瘤芽贷猎滔晦属蛙琶乔蹿陀魏解俄十如婴沃亩教招诅级许C语言程序设计第二章 算法C语言程序设计第二章 算法n一个结构化的算法是由一些基本结构顺序组成的一个结构化的算法是由一些基本结构顺序组成的n在基本结构之间不存在向前或向后的跳转，流程的转移只在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内存在于一个基本结构范围之内n一个非结构化的算法可以用一个等价的结构化算法代替，一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变其功能不

18、变n如果一个算法不能分解为若干个基本结构，则它必然不是如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法一个结构化的算法掷都穷方骑孺旷询滨走尹伊厕识汽宅恿芽拙锭彝斑融偿薯稳宫筑蚂郭耳挖C语言程序设计第二章 算法C语言程序设计第二章 算法 （5）用伪代码表示算法）用伪代码表示算法n伪代码是用介于自然语言和计算机语言之间的文字和符号来描伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法述算法n用伪代码写算法并无固定的、严格的语法规则，可以用英文，用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用也可以中英文混用例例: :求求5!5!。beginbegi

19、n ( (算法开始算法开始) ) 1 1 t t 2 2 i i while i5 while i5 t*i t*i t t i+1 i+1 i i print t print tend end ( (算法结束算法结束) )酉谣币垛枉哑殖退欺奇芬隅狂冶炒怎推犀亭赚骚司徽焙畴居俊缆全什漱纫C语言程序设计第二章 算法C语言程序设计第二章 算法例例: : 求求begin begin 1 1 sumsum 2 2 denodeno 1 1 signsign while deno 100 while deno 100 (-1)*sign (-1)*sign sign sign sign*1/deno s

20、ign*1/deno term term sum+term sum+term sum sum deno+1 deno+1 deno deno print sum print sumendend谤手蕾逃缮倡炎嘛炎醇涯腻稚能快罗炉涣犹彝筹扎越模身京泳溯砾驱厂俄C语言程序设计第二章 算法C语言程序设计第二章 算法（6 6）用计算机语言表示算法）用计算机语言表示算法n要完成一项工作，包括要完成一项工作，包括设计算法设计算法和和实现算法实现算法两个部分。两个部分。n设计算法的目的是为了实现算法。设计算法的目的是为了实现算法。n不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。不仅要考虑如何设计一个算

21、法，也要考虑如何实现一个算法。例例: :将算法（求将算法（求5!5!）用）用C C语言表示。语言表示。#include #include int main( )int main( ) int i,t; int i,t; t=1; i=2;t=1; i=2; while(i=5) while(i=5) t=t*i; t=t*i; i=i+1; i=i+1; printf(%dn,t); printf(%dn,t); return 0; return 0; 质殊画章蛙浮轮羞晕子聊萎罗赠因浚拴咨薯涡摇竟脆恶调操藏举搜观浮民C语言程序设计第二章 算法C语言程序设计第二章 算法例例: :将算法（求多项式

22、的值）用将算法（求多项式的值）用C C语言表示。语言表示。#include #include int main( )int main( ) int sign=1; int sign=1; double deno = 2.0,sum = 1.0, double deno = 2.0,sum = 1.0, term; term; while (deno = 100)while (deno = 100) sign = -sign; sign = -sign; term = sign/deno; term = sign/deno; sum = sum+term; sum = sum+term; den

23、o = deno+1; deno = deno+1; printf (%fn,sum); printf (%fn,sum); return 0; return 0; 共侥锹矮拖耸跋标忙喧详吱棠萎黔或南镑届鸿喳易峪遣盟弹酚菜垢蚀球咆C语言程序设计第二章 算法C语言程序设计第二章 算法四、结构化程序设计方法四、结构化程序设计方法n结构化程序结构化程序设计强调程序设计风格和程序结构的规范化，设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。提倡清晰的结构。n结构化程序设计方法的结构化程序设计方法的基本思路基本思路是：把一个复杂问题的求是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都

24、控制在人们容解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。易理解和处理的范围内。n采取以下方法保证得到结构化的程序：采取以下方法保证得到结构化的程序：（1 1） 自顶向下自顶向下；（2 2） 逐步细化逐步细化；（3 3） 模块化设计模块化设计；（4 4） 结构化编码结构化编码。用三种基本结构组成的程序是结构化程序用三种基本结构组成的程序是结构化程序凤匝毛玲膝憋阅逢胸尸爱数琳霜掸筏梁睛唉堂笆经枚篷搀馈盖铅儿橱览佩C语言程序设计第二章 算法C语言程序设计第二章 算法 自顶向上，逐步细化：自顶向上，逐步细化：将问题求解由抽象逐步具体化的设计过程。将问题求解由抽象逐步具体化的

25、设计过程。 比如设计房屋，先进行整体规划，然后确定建筑物方案，再进行各个比如设计房屋，先进行整体规划，然后确定建筑物方案，再进行各个部分的设计，最后进行细节的设计（门窗，楼道等），而绝不会在没有整体部分的设计，最后进行细节的设计（门窗，楼道等），而绝不会在没有整体方方案之前先设计楼道和厕所。而在完成设计，有了图纸之后，在施工阶段则案之前先设计楼道和厕所。而在完成设计，有了图纸之后，在施工阶段则是自下而上实施的，用一砖一瓦实现一个局部，最后由各个部分组成一个是自下而上实施的，用一砖一瓦实现一个局部，最后由各个部分组成一个建筑物。建筑物。 模块化设计：模块化设计：“分而治之分而治之”的思想，把大任

26、务分为若干子任务。的思想，把大任务分为若干子任务。 程序中的子模块在程序中的子模块在C C语言中通常是用函数来实现。语言中通常是用函数来实现。 结构化编码：结构化编码：将已设计好的算法用计算机语言来表示，即根据已经细化的将已设计好的算法用计算机语言来表示，即根据已经细化的算法正确写出计算机程序。算法正确写出计算机程序。誉垒碍捂咏凑嫌么憋焙时眩司莹诅锗攒合恤痒催傣唬很馏幼缓测赌轴贯惟C语言程序设计第二章 算法C语言程序设计第二章 算法结构化程序设计步骤结构化程序设计步骤一、确定算法：一、确定算法：分析问题（建立数学模型，利用公式分析问题（建立数学模型，利用公式),),写出算法写出算法 描述（比如

27、流程图描述（比如流程图）二、编写程序：二、编写程序：用计算机语言写出实现算法的程序用计算机语言写出实现算法的程序三、上机调试：三、上机调试：输入（编辑）程序输入（编辑）程序-编译、连接、执行程序编译、连接、执行程序-输出结果输出结果旧石湖凯赚二缠娃惫瑟勇寇普绞瞻嗜樱篷精舅描前揣煞删升策服玻倾竖割C语言程序设计第二章 算法C语言程序设计第二章 算法举例：举例： 算经中提出算经中提出“百鸡问题百鸡问题”：鸡翁一值钱五，鸡母一值钱三，：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？（体会编程步骤）（体会编程步骤）(1)(1

28、)分析：分析：cocks+hens+chicks=100 5*cocks+3*hens+chicks/3=100cocks+hens+chicks=100 5*cocks+3*hens+chicks/3=100其中，其中，0 cocks 19 , 0 hens 33 ,0 chicks 1000 cocks 19 , 0 hens 33 ,0 chicks 100累试法（枚举法）求解累试法（枚举法）求解算法描述：算法描述： cocks=0 cocks=0 当当cocks 19cocks 19时时找满足题意的找满足题意的hens,chickshens,chicks数数 cocks cocks加加

29、1 1 细化细化cocks=0cocks=0 当当cocks 19cocks 19时时hens=0hens=0当当hens 33hens 33时时 找满足题意的找满足题意的chickschicks数数 hens hens加加11henshens加加1 1 络长矿圾员犬蔚南冤馅尼痉言辛妮嫌盆堂众议扁掺宝癸末现敦奸狂革缠篮C语言程序设计第二章 算法C语言程序设计第二章 算法细化细化cocks=0cocks=0当当cocks 19cocks 19时时hens=0hens=0当当hens 33hens 33时时chicks=100-cocks-henschicks=100-cocks-hens 如果（

30、如果（5*cocks+3*hens+chicks/3=1005*cocks+3*hens+chicks/3=100） 则输出则输出henshens加加11cockscocks加加11卡恰寞啪耿穷韧烽见焉叶菌蛮知愧太混柠露铰仆疆拔恩噬莫除喇誊胖飞缘C语言程序设计第二章 算法C语言程序设计第二章 算法(2)(2)计算机语言写出程序计算机语言写出程序int main ( )int main ( ) int cocks=0.hens,chicks; int cocks=0.hens,chicks;while(cocks=19)while(cocks=19) hens=0; hens=0; while

31、(hens=33) while (hens=33) chicks=100-cocks-hens; chicks=100-cocks-hens; if(5*cocks+3*hens+chicks/3=100) if(5*cocks+3*hens+chicks/3=100) printf( printf(“%d%d%dn%d%d%dn”,cocks,hens,chicks);,cocks,hens,chicks);hens+;hens+; cocks+;cocks+; return 0;return 0; #include#include纪彭侄缉晌夷缘拯夕聋馁敖棵癸髓董篇言至质瞪纶搐刮俗犀柞啼露镭姿荔C语言程序设计第二章 算法C语言程序设计第二章 算法