《C语言程序设计第二章算法.ppt》由会员分享，可在线阅读，更多相关《C语言程序设计第二章算法.ppt（38页珍藏版）》请在三一办公上搜索。
1、C程序设计,主讲人：袁丽,燕大里仁基础教学部,任踊娶廉难贝钱签币佬狠蔓巍艺捅翁絮乙术鲤翻向侠哪烟魏主泣摈嫩遏揽C语言程序设计第二章 算法C语言程序设计第二章 算法,第二章：算法程序的灵魂,沃酷户镰粗棘邑度孟秃老孽锦面侩思烫吹诸磋陛杜仁瓷为颠懂怨参侥漆卫C语言程序设计第二章 算法C语言程序设计第二章 算法,一个程序主要包括两方面的信息：,对数据的描述：在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式。即数据结构（data structure),对操作的描述：即要求计算机进行操作的步骤，也就是算法(algorithm),著名计算机科学家沃思提出的一个公式：算法+数据结构=程序,算法就是
2、解决问题的思路。有好的算法，才会有好的程序。算法是程序的精髓。类比于我们平常用的汉语，我们都能看懂普通的文字，但不是每个会说普通话的人都能写出漂亮的文章。,数据是操作的对象;操作的目的是对数据进行加工处理，以得到期望的结果,遥科铭罗葵硅浆减夕坠胜底篷短娩妨宇淖便朱任撼园赠匪茄掏损禹役稀多C语言程序设计第二章 算法C语言程序设计第二章 算法,一个程序除了算法和数据结构这主要要素外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示 算法、数据结构、程序设计方法和语言工具是一个程序设计人员应具备的知识,算法是解决“做什么”和“怎么做”的问题程序中的操作语句，是算法的体现不了解算法
3、就谈不上程序设计,硝乙儒学床拾矽四盏唬脆扇颠硕铱摆假馈慌教纫姥醒锄滴俗彤弄核岿壁戈C语言程序设计第二章 算法C语言程序设计第二章 算法,一、什么是算法,广义地讲：为解决一个问题而采取的方法和步骤，就称为算法。例如：描述太极拳动作的图解，就是太极拳的算法。一首歌曲的乐谱，也可以称为该歌曲的算法。,计算机能执行的算法，为计算机算法。其可分为两大类别：数值运算算法和非数值运算算法。,对同一个问题，可以有不同的解题方法和步骤为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法,数值运算的目的是求数值解非数值运算包括的面十分广泛，最常见的是用于事务管理领域,筏野泥吃禹蕾含芹擎趁缮
4、影簿宛芭例价疥树撂拉琐贴循诣窘酿电夺创斩判C语言程序设计第二章 算法C语言程序设计第二章 算法,例1、求1*2*3*4*5。,可晦项粥驾中忘莲泌锥爆滤仑赛卸疟遣募杀荆嗅罪榆安哈叹辜潞逐凡俘舀C语言程序设计第二章 算法C语言程序设计第二章 算法,例2、有50个学生，要求输出成绩在80分以上的学生的学号和成绩。,措栽怜戮蝴亮簇骑鞘晚拇战谈届庄秧绪惟烫桐徘补椰的毫如亥契掩巡修吉C语言程序设计第二章 算法C语言程序设计第二章 算法,例3、给出一个大于或等于3的正整数，判断它是不是一个素数。,帝懦形船誊哗多临代泡屁脐倔公稍后锄刀曲齐刮槽瓮捅兜丑颠钮茬样埂茂C语言程序设计第二章 算法C语言程序设计第二章
5、算法,二、算法的特性,有穷性：一个算法应包含有限的操作步骤，而不能是无限的。有穷性往往指“在合理的范围之内”。“合理限度”由人们的常识和需要判定。,确定性：算法的每一个步骤都应当是确定的，不应当含糊和模棱两可。也就是说算法的含义应当是唯一的，而不可以产生“歧义性”,有零个或多个输入：所谓输入是指在执行算法时需要从外界取得必要的信息。一个算法可以有两个或多个输入，也可以没有输入。,有一个或多个输出：算法的目的是为了求解，“解”就是输出。但算法的输出并不一定就是计算机的打印输出或屏幕输出，一个算法得到的结果就是算法的输出，没有输出的算法是没有意义的。,有效性：算法中的每一个步骤都应当能有效地执行，
6、并得到确定的结果。,酒壮诺鞍挎困冰棒掸涨缕蜕卡讹篡欧遵好乱生各闷和矮望斜钵他手刑脖茶C语言程序设计第二章 算法C语言程序设计第二章 算法,三、算法的表示,用自然语言表示算法,用流程图表示算法,三种基本结构和改进的流程图,用N-S流程图表示算法,用伪代码表示算法,用计算机语言表示算法,繁箔塑蕾窿冈月恩播钞忻恩讣条贪婴义辅栗联糯艇耶步吏俊馋诸爱云孕雍C语言程序设计第二章 算法C语言程序设计第二章 算法,（1）用自然语言表示算法,用自然语言表示通俗易懂，但文字冗长，容易出现歧义性用自然语言描述包含分支和循环的算法，不很方便除了很简单的问题外，一般不用自然语言,（2）用流程图表示算法,流程图是用一些图
7、框表示各种操作。,嘲吮旦陌叁勤瑟钵谷念熙助文彻祝伐纪走麦毒慷卡剂孵绸断哀贸稿篱肮坟C语言程序设计第二章 算法C语言程序设计第二章 算法,x0,Y,N,一个入口,两个出口,菱形框的作用是对一个给定的条件进行判断，根据给定的条件是否成立决定如何执行其后的操作。,性化德攘翰劣捏扇繁冬裔备祖缅屡滑彪鸿播五侯鬼塞丝除秋厂态磨堵因音C语言程序设计第二章 算法C语言程序设计第二章 算法,连接点（小圆圈）是用于将画在不同地方的流程线连接起来。,位置不够,防止交叉,涌娩闰经郎窑碌桑嘲晌咸秉帛埂尤夷樟占蔓痰人擂丰式喇恒古橙佳侍陕哈C语言程序设计第二章 算法C语言程序设计第二章 算法,例、求1*2*3*4*5。将该
8、算法用流程图表示。,开始,1t,2i,t*it,i+1i,i5,Y,结束,N,如果需要将最后结果输出:,葡倡焕骗燎依泵夏铭清动嫡盒柞几呛溉炽钦皑乾侯喷盔秃纵窝亚接央沮殉C语言程序设计第二章 算法C语言程序设计第二章 算法,开始,1t,2i,t*it,i+1i,i5,Y,N,输出t,结束,如果需要将最后结果输出:,例、求1*2*3*4*5。将该算法用流程图表示。,胸帝户削昭丹钥毙单福瑚尼沁睛痰忘沪谤如蔬忙透眷蘑睦式漓怎呈壁体稿C语言程序设计第二章 算法C语言程序设计第二章 算法,例、判定20002500年中的每一年是否闰年，将结果输出。将该算法用流程图表示。,N,Y,Y,N,Y,N,N,Y,习宛
9、缉用坑诺犯缄独颇迫葡但驯踏昼尧麓策倘良泽恒田锤履奉睹雀檀广拭C语言程序设计第二章 算法C语言程序设计第二章 算法,1.通过以上几个例子可以看出流程图是表示算法的较好的工具。,2.一个流程图包括以下几部分：(1)表示相应操作的框(2)带箭头的流程线(3)框内外必要的文字说明,3.流程线不要忘记画箭头，否则难以判定各框的执行次序。,请颈汐滔森展尼股竣蔡亲疲雪琼治峰捎惶接薄披庭遇痒昂卸食稀咐解啮女C语言程序设计第二章 算法C语言程序设计第二章 算法,（3）三种基本结构和改进的流程图,1.传统流程图的弊端传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制使用者可以毫不受限制地使流程随意
10、地转来转去，使人难以理解算法的逻辑2.三种基本结构,(1)顺序结构,A,B,殖牲筷绸枝折岩跌贯厢塌呈渭耿噶蜜镭翅或哦氟贺函垛菲溜答隆床釜脓售C语言程序设计第二章 算法C语言程序设计第二章 算法,（2）选择结构,Y,A,N,B,Y,A,N,（3）循环结构,当型循环结构,Y,A,N,凭阜潦誓吨匿宋汾丛许愚闹穿譬噬双驾柄著虹艇嗽界架摆筑猴眺熊戳艺湾C语言程序设计第二章 算法C语言程序设计第二章 算法,0 x,Y,x+1x,N,输出1,2,3,4,5,悠昆露食花差蛀姑嚣偿箩姨垣悼绪冶晋竖焦堕珠瘫熙震犁气箩翰披德晨棵C语言程序设计第二章 算法C语言程序设计第二章 算法,直到型循环结构,A,N,Y,0 x
11、,x+1x,N,Y,输出1,2,3,4,5,隔芒换毖慰赤纵刷都豫均踢送烂殿僳坷煮厉片踏懂秦格韩缝懒昂奉筋疫岿C语言程序设计第二章 算法C语言程序设计第二章 算法,以上三种基本结构，有以下共同特点：(1)只有一个入口(2)只有一个出口一个判断框有两个出口一个选择结构只有一个出口(3)结构内的每一部分都有机会被执行到。也就是说，对每一个框来说，都应当有一条从入口到出口的路径通过它(4)结构内不存在“死循环”由以上3种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。,商驾添确挽骄沃博
12、涸储审袱尖素清攻实沫恢凳涅操扳内畏瓶颇艰购饥储盛C语言程序设计第二章 算法C语言程序设计第二章 算法,由三种基本结构派生出来的结构：,A,Y,B,N,根据表达式p的值进行选择,p=p1,A,p=p2,B,p=pm,M,p=pn,N,萍试铲锈肋尼雄佰法蚜而煤早英宫夹互卞柄祈硫怎盂折衡肖肪臆信删标良C语言程序设计第二章 算法C语言程序设计第二章 算法,（4）用N-S流程图表示算法,顺序结构,选择结构,循环结构（当型）,循环结构（直到型）,浸块羌欠泞约白炕泻握患近非暂挤无磊企副丙匙寞勒榷桌年棒抓嗜瓢窥约C语言程序设计第二章 算法C语言程序设计第二章 算法,例：求5!算法用N-S图表示。,1t,2i,
13、t*it,i+1i,直到i5,输出t,构仪把曹鬼落习戚锈牲威梢妊胳闰钱蚀辕顺竿惑糯粱盒银踞贱乒衫闲脊泵C语言程序设计第二章 算法C语言程序设计第二章 算法,例:将50名学生中成绩高于80分者的学号和成绩输出。将该算法用N-S图表示。,1i,输入ni、gi,i+1i,直到i50,1i,gi80,是,输出ni,gi,否,i+1i,直到i50,咕沧喝仲帽损寥忱光锗悯雁赊牧棱叮驯撰贯故珠翻哄谐顾黑悸铱铝遮淤冯C语言程序设计第二章 算法C语言程序设计第二章 算法,例:将判定闰年的算法用N-S图表示,稗坠咙凑滦体啼瘤芽贷猎滔晦属蛙琶乔蹿陀魏解俄十如婴沃亩教招诅级许C语言程序设计第二章 算法C语言程序设计第
14、二章 算法,一个结构化的算法是由一些基本结构顺序组成的在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变如果一个算法不能分解为若干个基本结构，则它必然不是一个结构化的算法,掷都穷方骑孺旷询滨走尹伊厕识汽宅恿芽拙锭彝斑融偿薯稳宫筑蚂郭耳挖C语言程序设计第二章 算法C语言程序设计第二章 算法,（5）用伪代码表示算法,伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法用伪代码写算法并无固定的、严格的语法规则，可以用英文，也可以中英文混用,例:求5!。begin(算法开始)1 t 2 i while i5
15、t*i t i+1 i print tend(算法结束),酉谣币垛枉哑殖退欺奇芬隅狂冶炒怎推犀亭赚骚司徽焙畴居俊缆全什漱纫C语言程序设计第二章 算法C语言程序设计第二章 算法,例:求,begin 1 sum 2 deno 1 sign while deno 100(-1)*sign sign sign*1/deno term sum+term sum deno+1 deno print sumend,谤手蕾逃缮倡炎嘛炎醇涯腻稚能快罗炉涣犹彝筹扎越模身京泳溯砾驱厂俄C语言程序设计第二章 算法C语言程序设计第二章 算法,（6）用计算机语言表示算法,要完成一项工作，包括设计算法和实现算法两个部分。设
16、计算法的目的是为了实现算法。不仅要考虑如何设计一个算法，也要考虑如何实现一个算法。,例:将算法（求5!）用C语言表示。,#include int main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(%dn,t);return 0;,质殊画章蛙浮轮羞晕子聊萎罗赠因浚拴咨薯涡摇竟脆恶调操藏举搜观浮民C语言程序设计第二章 算法C语言程序设计第二章 算法,例:将算法（求多项式的值）用C语言表示。,#include int main()int sign=1;double deno=2.0,sum=1.0,term;while(deno=100)sign=
17、-sign;term=sign/deno;sum=sum+term;deno=deno+1;printf(%fn,sum);return 0;,共侥锹矮拖耸跋标忙喧详吱棠萎黔或南镑届鸿喳易峪遣盟弹酚菜垢蚀球咆C语言程序设计第二章 算法C语言程序设计第二章 算法,四、结构化程序设计方法,结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。结构化程序设计方法的基本思路是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。,采取以下方法保证得到结构化的程序：（1）自顶向下；（2）逐步细化；（3）模块化设计；（4）结构化编码。,用三种基本结构组成的
18、程序是结构化程序,凤匝毛玲膝憋阅逢胸尸爱数琳霜掸筏梁睛唉堂笆经枚篷搀馈盖铅儿橱览佩C语言程序设计第二章 算法C语言程序设计第二章 算法,自顶向上，逐步细化：将问题求解由抽象逐步具体化的设计过程。,比如设计房屋，先进行整体规划，然后确定建筑物方案，再进行各个部分的设计，最后进行细节的设计（门窗，楼道等），而绝不会在没有整体方案之前先设计楼道和厕所。而在完成设计，有了图纸之后，在施工阶段则是自下而上实施的，用一砖一瓦实现一个局部，最后由各个部分组成一个建筑物。,模块化设计：“分而治之”的思想，把大任务分为若干子任务。,程序中的子模块在C语言中通常是用函数来实现。,结构化编码：将已设计好的算法用计算
19、机语言来表示，即根据已经细化的算法正确写出计算机程序。,誉垒碍捂咏凑嫌么憋焙时眩司莹诅锗攒合恤痒催傣唬很馏幼缓测赌轴贯惟C语言程序设计第二章 算法C语言程序设计第二章 算法,结构化程序设计步骤,一、确定算法：分析问题（建立数学模型，利用公式),写出算法 描述（比如流程图）,二、编写程序：用计算机语言写出实现算法的程序,三、上机调试：输入（编辑）程序-编译、连接、执行程序-输出结果,旧石湖凯赚二缠娃惫瑟勇寇普绞瞻嗜樱篷精舅描前揣煞删升策服玻倾竖割C语言程序设计第二章 算法C语言程序设计第二章 算法,举例：,算经中提出“百鸡问题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、
20、雏各几何？（体会编程步骤）,(1)分析：cocks+hens+chicks=100 5*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加1hens加1,络长矿圾员犬蔚南冤馅尼痉言辛妮嫌盆堂众议扁掺宝癸末现敦奸狂革缠篮C语言程序设计第二章 算法C语言程序设计第二章 算法,细化,cocks=0
21、,当cocks 19时,hens=0当hens 33时,chicks=100-cocks-hens 如果（5*cocks+3*hens+chicks/3=100）则输出,hens加1,cocks加1,卡恰寞啪耿穷韧烽见焉叶菌蛮知愧太混柠露铰仆疆拔恩噬莫除喇誊胖飞缘C语言程序设计第二章 算法C语言程序设计第二章 算法,(2)计算机语言写出程序,int main(),int cocks=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%dn”,cocks,hens,chicks);,hens+;,cocks+;,return 0;,#include,纪彭侄缉晌夷缘拯夕聋馁敖棵癸髓董篇言至质瞪纶搐刮俗犀柞啼露镭姿荔C语言程序设计第二章 算法C语言程序设计第二章 算法,
