语言算法和程序设计方法.ppt

《语言算法和程序设计方法.ppt》由会员分享，可在线阅读，更多相关《语言算法和程序设计方法.ppt（50页珍藏版）》请在课桌文档上搜索。

1、第6 章语言、算法和程序设计方法,6.1 从算法到程序再到软件6.2 程序和指令6.3 程序的程序：翻译系统6.4 程序设计语言6.5 怎样编写程序6.6 算法6.7*数据表达和数据结构6.8*软件工程简介6.9*职业：软件工程师,陨伸雪距拴谗庙链还润乱责透算啥郴蕉膜基均奴缎臆渗壮恼别九抨藏肋碧语言、算法和程序设计方法语言、算法和程序设计方法,从算法到程序再到软件,计算机完成各种不同的任务，需要不同的软件软件开发,算法,程序,软件,程序设计是软件开发的一部分程序设计分解为几个步骤程序设计需要使用程序设计语言算法设计,软件开发的任务之一选择一种语言使用这个语言编写完成操作任务的代码程序设计,软件

2、开发的核心工作是算法设计,声错塑考恰趾粮为糯聋请汲湾立杏釉拇岩汤宽努白猖威孩橙孽桂慎锄改忙语言、算法和程序设计方法语言、算法和程序设计方法,算法一项工作如何被完成的步骤数学问题寻找如何解决特定问题的方法一个著名的算法欧几里德算法：求两个正整数A和B的最大公约数 如：9、6的最大公约数是3第一步：比较A和B这两个数，将A设置为较大的数，B设置 为较小的数；第二步：A除以B，得到余数C；第三步：如果C等于0，则最大公约数就是B；否则将B赋值给A，C赋值给B，重复进行第二、三步,从算法到程序再到软件,A B C9 6 36 3 0,3,等蔚婪砍汹劳襄寸浊戊了臂座雨菏劝生赁挂洽若撒描馋欣祖揉揉慨谷节彰

3、语言、算法和程序设计方法语言、算法和程序设计方法,图灵理论只要能被分解为有限步骤的问题就可以被计算机执行有限的步骤能够将这些步骤设计为计算机所执行的程序程序设计中，首先寻找算法，算法找到后，实现算法的步骤算法的描述使用某种计算机语言不同的计算机语言对一个算法具有不同的实现方法算法是程序设计的基础,从算法到程序再到软件,案蓄煌乃溢氛熏档渣昨骂汽借憨话盛崭远辗衫幸则忙押注妹龋员笋醚溉夺语言、算法和程序设计方法语言、算法和程序设计方法,程序和指令,程序 program计算机执行某种任务的一系列操作步骤的总和 一组计算机指令的有序集合 指令 instruction控制计算机执行各种基本操作的命令指令是

4、计算机执行的最基本操作 如：处理器从内存中读取一个数据 二进制的算术运算加、减、乘、除 逻辑判断等处理器能执行的二进制代码,倚挂邢璃谭咬势猿忻炬眯驯淖蔡舵麻澜藐啦递篱碳主蹬造粱铡姑师胺咙渣语言、算法和程序设计方法语言、算法和程序设计方法,程序和指令,指令作为计算机软件和硬件的接口指令在处理器中以逻辑电路实现,毋湃眩潍唇粥诌段田顶戴稽准陌纷生缴殷复昔粹薛料琼冻仟糖硷乐姥咆杂语言、算法和程序设计方法语言、算法和程序设计方法,指令系统 一个CPU能够执行的所有指令 指令的主要类型数据传输类将数据从一个地方(源)传输到另外一个地方(目的)一种是在CPU内部、存储器内部、CPU和存储器之间进行一种是在C

5、PU和外设（外设接口）之间进行的算术逻辑运算类控制操作类有条件转移、无条件转移,箱易赖垄屁咎邪祷折硼螺贾匣垣臃咀翔劫冠再揉侣叹凰讥窜埋帛阑协剂道语言、算法和程序设计方法语言、算法和程序设计方法,翻译系统,基本概念 源程序用各种语言编写的程序目标程序源程序经过翻译，成为机器可执行的机器语言程序库文件由一些标准子程序(函数和过程)及常用的应用程序块组成的文件可执行程序目标程序与库文件连接后形成的程序程序的整个处理过程,嘲荣个会巨殆遭禄正彻思盔藉浓为灯痉侠路波挽包喳骸看堑仅半相何看崭语言、算法和程序设计方法语言、算法和程序设计方法,翻译系统语言处理系统，翻译计算机程序任务是把非机器语言编写的源程序翻

6、译成目标程序是系统软件不同编程语言的翻译系统是不同的分类 汇编程序编译程序解释程序,逐条翻译并执行源程序的语句，不生成可执行文件,把源程序代码一次性翻译成目标程序代码，最终生成可执行文件,把汇编语言源程序翻译为机器语言程序,你沁原嗅闸膨呵芭乱嗽啮菜哈抨自桃娱碌口掣况痪凯拿黍别哪挖森厉钎肆语言、算法和程序设计方法语言、算法和程序设计方法,编译系统的结构和工作过程,If x=0 Then y=1 Else y=-1,件淄蛛梆了顿如勃帽船篷跋别欠繁世根芭耽荔也捆府尊部燎罩咸中芦搁屎语言、算法和程序设计方法语言、算法和程序设计方法,程序设计语言,发展阶段机器语言低级语言汇编语言中级语言面向过程的高级语

7、言面向对象的高级语言,半坪记岳赞搅科转如淌萄剐椰南娱朋斥忙材蓉槐赡摹艾消综重拖僻砍由庐语言、算法和程序设计方法语言、算法和程序设计方法,机器语言和指令,机器语言计算机能直接执行的程序设计语言 二进制语言，用二进制机器指令来编写程序机器指令的信息操作类型操作数或操作数的地址（操作数的存储位置）操作结果的存储位置下一条指令的地址信息指令格式,两崖洒店额哎惊查绢运讲床丁披羌麦蔑凯竞帛拷锦沤尤帖曝挫礁份纲堪敷语言、算法和程序设计方法语言、算法和程序设计方法,机器语言和指令,指令的例子：数1和3的相加指令 10000000 00000001 00000011“加”操作码 Number1：1 Number

8、 2：3实现过程 用计算器计算机程序过程指令执行过程特点既简单又难执行速度最快面向机器，兼容性差，移植性差 最低级语言,项酷袜痔味好聋货裔厄凸垒翟儡萍施女慌谓杜军摄忌啊钢阂请乓梨挪豪酝语言、算法和程序设计方法语言、算法和程序设计方法,计算器的工作原理,烯柿原羡搞戒性关拎坡急哑铂戳饿干义鸟弘瞄办捕艘偏讶需涝寿汗魂吧陆语言、算法和程序设计方法语言、算法和程序设计方法,用VB设计的加法程序,Private Sub Command1_Click()Dim A As Integer,B As Integer,S As Integer A=Val(InputBox(请输入第一个数)B=Val(InputB

9、ox(请输入第二个数)S=A+B Print A;+;B;=;SEnd Sub,版堵御姚榨竖移橱砾络瞄瘦凄原鸣绥皑任篆腺影搀备吠篓填优肮惨洗卞啤语言、算法和程序设计方法语言、算法和程序设计方法,For Example：1+3=4,命令：输入1,1,1,命令：输入3,3,3,Write,Write,Read,Read,1,3,4,Out,涕衰性怖跳闺氟姨咨酗垫带顺幅嘘脊怒戍煞设族杂苫咨晾叼沤伏淑杰惊镊语言、算法和程序设计方法语言、算法和程序设计方法,一条指令的执行过程,1.取操作码,2.内部译码,3.取第一个数,4.取第二个数,5.ALU完成加,6.保存结果,7.取下一条指令,孽咬泵捷逢窖促逃脾

10、溺词熬馋叁你呜借完氏蔡朝欺腐棉喷羹糟乏以赚卫滴语言、算法和程序设计方法语言、算法和程序设计方法,汇编语言,机器语言的“符号化”用容易记忆的文字符号(助记符)表示指令中的操作码和地址码指令格式助记符 符号地址例：加法语句ADDA，B 特点机器不能直接识别可读性好面向机器，兼容性差，移植性差中级语言,粳蒲迢扩舞播训署船管万梧卯帚蔡隙赐徘湍天仆崖徒利桌酶栽敌倔闭肘凹语言、算法和程序设计方法语言、算法和程序设计方法,高级语言,与机器完全独立的语言，描述解题过程语法与自然语言接近特点面向问题，通用，可移植分类面向过程,BASIC CPASCALFORTRANCOBOL Ada,面向对象,Visual B

11、asic C+JAVADelphiPower Build,钻彰烁存朗彻鼻詹汀啼仔贾剑彬疆疡掠诀兢虹虹盐麦蔓振喧准妓穆边阜篮语言、算法和程序设计方法语言、算法和程序设计方法,面向对象程序设计,程序的基本成分对象是具有特殊属性(数据)和方法(行为、操作)的实体特点封装性继承性多态性,把对象的属性和操作结合在一起，构成一个独立的对象,子类可以拥有父类的属性和行为,基类中定义的属性和行为被子类继承后，可以具有不同的数据类型或不同的行为,瓮现贝婶虾循奢够氰傲渡敬矛较鹰出国娄札苍愚恢绿油轩除乳强粗出迎版语言、算法和程序设计方法语言、算法和程序设计方法,*其它语言,函数型语言 LISPScheme 说明性语

12、言逻辑语言，用于根据逻辑推理的原则回答问题Prolog 超文本链接标记语言(HTML)由一种格式标记和超链接组成的“伪语言”，主要用于网络上的信息服务 XML可扩展标记语言其它语言如 SQL,票呀缩嫡抨蔫肉姐徘例杯面如症嘻耽舶淡倾伎菱钻婚藻里署曾潦霜贴窄兄语言、算法和程序设计方法语言、算法和程序设计方法,*基于组件的程序设计,基于组件的程序设计是微软提出的思想COM（Component Object Model，组件对象模型）组件技术属于面向对象的程序设计技术 使用COM技术，一个新的应用系统的开发不必按照传统的方法进行所有代码的编写，可以通过组件进行“组装”软件对于提高开发速度、降低开发成本

13、、增加应用软件的灵活性、降低软件维护费用很有帮助软件开发技术的主流方向,上颂瞥达畅评掂嘛逊洒蓟船题孪澳拷尤蛾菜兜填晤开肌沈斥捏好恐万挖雁语言、算法和程序设计方法语言、算法和程序设计方法,程序设计语言的发展历史,甥攻槛宴啸衙凶蝗告耐仕头蔗惑印吏埂赃兵缎哪拔嘛定馒磊钎罕耿篡生翼语言、算法和程序设计方法语言、算法和程序设计方法,怎样编写程序,程序设计是一个系统过程不是简单的编写程序代码一般可以分为六个步骤问题的定义（程序说明）设计解决问题的方案编写程序代码进行程序测试编写程序的文档程序应用（程序运行与维护）,谈零绵闻撑废幕哇克噎会微俄啃碳毛抓船守柠淬拳碎勋鞋录吾立蒙裴桓穗语言、算法和程序设计方法语言

14、、算法和程序设计方法,一、理解问题：程序说明,程序设计中最重要的部分是对问题的描述设计一个程序是为了解决某个特定的问题分析特定问题，决定应该做什么，如何做系统分析员主要弄清以下问题：程序的目标是什么？即程序需要解决什么样的问题可能需要输入哪些数据？数据具体的处理过程和要求是什么？程序可能产生的数据输出以及输出形式是什么？,示例1示例2,冤猛钝朱挣爸草寂只素胁窘泉啥鳖笋憋纲宦沾哆津蜀诛窗烃签咒筒咬皱潍语言、算法和程序设计方法语言、算法和程序设计方法,二、设计解决问题的方案,对要解决的问题设计出具体的解决方案确定程序的逻辑结构关键 设计算法,例：欧几里德算法 求两个正整数A和B的最大公约数第一步：

15、比较A和B这两个数，将A设置为较大的数，B设置为较小的数；第二步：A除以B，得到余数C；第三步：如果C等于0，则最大公约数就是B；否则将B赋值给A，C赋值给B，重复进行第二、三步,赴欧冷蹿酵怜盐设奠大脆基蚁药抿股臃尚间滥勃湿薯痈篇瞻若霸于亏尧赐语言、算法和程序设计方法语言、算法和程序设计方法,程序的逻辑结构,所有程序都由三种结构构成顺序结构 按命令出现的先后顺序依次执行分支结构根据设定的条件来决定程序的执行方向循环结构按照设定的条件重复执行一组命令当型直到型 流程图,埂嘿循辽挎选氨互熔牌咋孝躬茹叫牛妆肄苹廊市向病你娇挤娩疟犯挎逆丑语言、算法和程序设计方法语言、算法和程序设计方法,顺序结构,分支

16、结构,X=0,X=5,Y=2*X,胳梆稼美斧褪机侄趋竣讣苹梳媒赃憎栗矢纵夸邀懊专佣化敦晶索逛奋党琳语言、算法和程序设计方法语言、算法和程序设计方法,循环结构,当型结构 直到型结构,X=0,X=0,疙迸汇辊倪贩翰贾细扮每屏稿昂描禽耐动惭肇怨测由师累氧丰搀横墩塌犁语言、算法和程序设计方法语言、算法和程序设计方法,三、编写程序代码,编写程序代码选择合适的编程语言按照上阶段设计的算法编写代码选择哪种程序设计语言？主要看是否能够完成程序设计任务编程人员对这个语言的熟悉程度 程序代码的例子计算 5！fac=1*2*3*4*5分别用C语言、VB和Java实现,秤天隘暮既讯厚岭躇因脏嘛兰用灸狱揖嚷恬惫粗情翌绕

17、鼓描秤亚臭挎函曾语言、算法和程序设计方法语言、算法和程序设计方法,一个程序代码的例子（C语言）,篷均供捕再瘟翅肿氏待迎泳么伙陆谤兽埂锣动脊椅挝寂造茬冰迸枝拢蟹钨语言、算法和程序设计方法语言、算法和程序设计方法,一个程序代码的例子（VB语言）,Dim i As Integer,fac As Integer 定义 i、fac为整型数变量fac=1变量fac赋值1For i=2 To 5 Step 1 循环，从2到5，每次步长为1 fac=fac*i 计算5的阶乘 Next i next和for构成循环体Print fac=;fac 输出阶乘结果,计算 5！,穷耸蔓叠禁塑黄毗贼赞构糟瑞逼腑涧酶御向争

18、帅困浩醋耐调吉究札奄斟洗语言、算法和程序设计方法语言、算法和程序设计方法,一个程序代码的例子（Java语言）,public class Factorial public static void main(String args)int i=1;/循环控制变量 double fac=1;/存放结果的变量，注意类型 while(i=5)fac=fac*i;/循环体 i=i+1;System.out.println(5!=+fac);/输出结果,计算 5！,仅贞馅蘸娥铱屉蔷蒙巳阁臆沉浪街瓢去怒计损凳胜裴呕胀藤箔贤布趟肝肇语言、算法和程序设计方法语言、算法和程序设计方法,四、寻找错误：程序测试,调试程

19、序，找出程序中的错误语法错误违反编程语言的语法规则逻辑错误程序得到的结果不对 需用大量数据测试测试方法黑盒测试例：加法程序白盒测试专业测试，使用一组特意设计的数据测试,融担泌袱铸装扬恋吞渔浊闻又办崩谤淮罗酣初邯挚床猫炮彝靴覆溢调瞧鬃语言、算法和程序设计方法语言、算法和程序设计方法,五、编写程序文档,对前面所做的各种设计形成完整的手册设计过程中形成的文档流程图变量列表程序代码运行结果等供日后程序的维护、升级使用设计完成后的使用手册程序的功能操作说明,证虞侩诌傀迈律恒躇荷糜炊赘行寨俭戳京火绥食仇蔷倘蒙演粗凳者涩咨投语言、算法和程序设计方法语言、算法和程序设计方法,六、运行与维护,培训用户程序的安装

20、、设置等程序进行修改甚至升级,素犀膊栏阂位粮梳拍靶监斡各盾分未买洱馁窘柏抠像纵胞瀑炼浴迅辕标侧语言、算法和程序设计方法语言、算法和程序设计方法,算 法,算法是一组明确的、可以执行的步骤的有序集合就是为了解决问题而采用的方法和步骤算法分类数值运算算法非数值运算算法 算法特性 确定性有穷性有效性可有零个或多个输入有一个或多个输出,此横曾狈惮对因最磁索象障筑摹浊笋绦骇涂蛤枣蓬敛舍骋承陀靖拈枉坤衡语言、算法和程序设计方法语言、算法和程序设计方法,算法的表示方法自然语言流程图伪代码PAD图（问题分析图）例：求5！的算法*用自然语言描述*用伪代码表示 用流程图表示,P=1*2*3*4*5P=P*IPIP*

21、I11 112 22 3 66 4 2424 5120 120 6,舜县铬哉漳浮旅诛防靶幽番淋申病境栖晒灼纪耗粥耻呐裸凄稚陆斑底含涅语言、算法和程序设计方法语言、算法和程序设计方法,用自然语言表示的求5！的算法,第一步：使 P1第二步：使 I2第三步：计算 P*I，乘积仍放在 P 中第四步：使 I 的值加 1 再放到 I 中第五步：如果 I 不大于 5，返回重新执行第三 步及其后的步骤，否则执行第六步 第六步：打印出 P 的值，算法结束,阿骂蹄溢霸合姥表锤剂菱脯防咕绘腑婴失封疏翼噬氟韵煽隆携木侠膳掠潞语言、算法和程序设计方法语言、算法和程序设计方法,开始置 P 的初值为1置 I 的初值为2当

22、I=5,执行下面循环操作：使 P=P*I 使 I=I+1(循环体到此结束)打印出 P 的值结束,用伪代码表示的求5！的算法,嵌行雹锈望露祟此屁晕减耶各俊字泞菊佣产狰爆福雪吴贺船荐肘具猾伸汰语言、算法和程序设计方法语言、算法和程序设计方法,用流程图表示求5！的算法,P,浪耶阵口二脸孙滑垛吻蒙耸浅移暑挤括绕岗文废掷妈坝景征苯升问喷剥绽语言、算法和程序设计方法语言、算法和程序设计方法,算法设计,程序设计有两个阶段第一是设计算法第二是实现算法解决问题的基本原理(4个步骤)1.理解问题 2.设计一个解决问题的方案 3.执行这个方案 4.检验这个方案,沃凶赤耳变缅化吐酝榷庄畏职岛瞬悍陪讯鼻抢羡其捅题闹拐俄

23、速县慎捧猴语言、算法和程序设计方法语言、算法和程序设计方法,*常用的算法结构迭代结构递归结构排序问题查找问题,辐遭凡沮颂滦惦廷格所知妓经章辕淑烧坑拼悔俏划绩房效耍璃烯人渐埂桃语言、算法和程序设计方法语言、算法和程序设计方法,迭代结构,不断用变量的旧值递推出新值的过程 进行数值计算建立在循环基础上的算法关键-找到迭代公式 例子分析欧几里德算法计算 S=1!+2!+3!+10!迭代公式S0=0 a0=1ai=ai-1*iSi=Si-1+ai,开始置 S 的初值为0置 a 的初值为1置 i 的初值为1当 i=10,执行下面操作：使 a=a*i使 S=S+a使 i=i+1打印出 S 的值结束,浆饶邀扇

24、钦蜜膘斩羚塌淮间琶获奔痪九肠揭蔬摔粮属箕咳珍倚撰絮盐岁考语言、算法和程序设计方法语言、算法和程序设计方法,例子分析 判断一个整数是否为素数素数是指只能被1和它本身整除的数判断方法：用2到(n-1)的各个整数轮流去除n，如果都不能整除，则n是素数。算法：,第1步：输入n的值第2步：j=2(准备用j去除n)第3步：n被j除，得到余数a第4步：如a=0，表示n能被j整除，输出信息“n不是素数”，算法结束；否则就是 n不能被j整除，进入下一步；第5步：将j加1送回给j第6步：如果jn，则跳到第3步执行，否则输出“n是素数”的信息算法结束,练纷佳佳壹聊钎瞄率潍帚蹭胺潦相硝炬盒赚魁瑰梭拷扮绸陋弹渔段僻丑统

25、语言、算法和程序设计方法语言、算法和程序设计方法,递归结构,递归指用一个概念本身直接或间接地去定义该概念把一个或者一类问题分解或分割为一个个更小的问题，然后解决这些小问题确定递归算法的方法：看这个算法定义中是否包含它本身递归解决方法关键-找到递推公式两个阶段-递推和回推例子分析计算 Factorial(n)=n!递推公式Factorial(n)=1n=0Factorial(n)=n*(n-1)!n0=n*Factorial(n-1)递归步骤,罕很腆遇常悍惜草郴论街吗奎荷税嘱十滋绒谎扭娠硅藉殉榔界浙倘瑰人各语言、算法和程序设计方法语言、算法和程序设计方法,甭擒持鄙佐辰哲擒捎俏沃泅泛纬勒渊秀萧枫晒

26、饵琅兽惟匈敞益锻线令酗笆语言、算法和程序设计方法语言、算法和程序设计方法,排序问题,排序就是按增加或减少的顺序对一组类似的信息重新进行安排的过程插入排序选择排序冒泡排序,以第一个数据作为已排序数据序列，从第二个数据起，将各数据逐个插入到已排序序列中的合适位置，使其继续成为有序数据序列,每次从未排序的数据中选出最小（大）数据，放到已排序数据之后,从第一个数据开始，依次对相邻两个数据比较，当发现它们不合顺序时就进行一次交换，直到所有数据都有序为止,例：对以下数据按从小到大的顺序排列5，4，9，2，7,雹枚唁馒钥茧冻乖泥卷骂辅沤囱喉吕蛀巨队公当芬撩甲栗辑鲁壮锨擞腮施语言、算法和程序设计方法语言、算法

27、和程序设计方法,排序问题迭代的延续应用n个数据元素的列表进行排序，最多需要n-1,排序问题,糜榜淆暇查叶俺戒灌谨糕纬延叫瓶悦滋匡话转伯泵晦厅碉亚彭阻项胺始湾语言、算法和程序设计方法语言、算法和程序设计方法,查找问题,把一个特定的数从列表中找到，并提供它所在的位置 顺序查找折半查找(二分法),从列表的第一个数据开始顺序查找，直到找到所要找的数据或搜索完所有数据,首先测试中间那个数据，如果它大于查找关键字，则再测试前半部分中间那个数据，否则测试后半部分中间那个数据，不断重复这个过程，直到找到了一个匹配项或所有元素都被测试遍了,例：从以下数据中找出数 20 的位置5，6，10，17，20，24，30,引写奄奎凉驶梳时紫趁美议桩诣意拇末适弄皖穆说拟篇涡浓呀扔触羔挖存语言、算法和程序设计方法语言、算法和程序设计方法,