第5章-程序设计基础课件

5.1程序设计概述5.2算法概述5.3软件工程概述第5章程序设计基础5.1程序设计概述第5章程序设计基础5.1.1

程序设计的基本过程5.1.2

程序设计的方法5.1.3

程序设计语言5.1程序设计概述5.1.1程序设计的基本过程5.1程序设计概述5.1.1程序设计的基本过程程序设计：编写程序的过程程序设计过程包括分析、设计、编码、测试、编写文档等不同阶段5.1.1程序设计的基本过程程序设计：编写程序的过程5.1.2程序设计的方法结构化程序设计方法面向对象程序设计方法5.1.2程序设计的方法结构化程序设计方法结构化程序设计结构化程序设计的原则自顶向下逐步细化模块化限制使用goto语句结构化程序设计结构化程序设计的原则结构化程序设计结构化程序设计的基本结构顺序结构选择结构循环结构结构化程序设计结构化程序设计的基本结构结构化程序设计顺序结构按照程序语句的书写顺序一条一条的执行最基本、最常用的结构结构化程序设计顺序结构结构化程序设计选择结构（分支结构）根据设定的条件，判断应该执行哪一条语句包括单分支结构、双分支结构和多分支结构结构化程序设计选择结构（分支结构）结构化程序设计循环结构（重复结构）根据给定的条件，判断是否需要重复执行相同的程序段分为当型循环结构和直到型循环结构

结构化程序设计循环结构（重复结构）面向对象程序设计结构化程序设计又称为面向过程的程序设计面向对象程序设计方法模拟人们理解和处理客观世界的方式来分析问题，把系统视为一系列对象的集合，分析者、设计者和编程者都可以使用相同的概念，从而使面向对象的程序设计方法能比较自然地模拟客观世界的活动，使问题描述空间与解空间在结构上尽可能一致。面向对象程序设计结构化程序设计又称为面向过程的程序设计面向对象的基本概念对象：客观世界中的任何实体，既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界和意义的东西。对象的特点：标识唯一性分类型多态性封装性模块独立性面向对象的基本概念对象：客观世界中的任何实体，既可以是具体的面向对象程序设计类：类是对象的抽象，它描述了该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例消息面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制来协助完成，这种机制称为“消息”面向对象程序设计类：面向对象程序设计继承使用已有的类定义作为基础建立新类的定义技术已有的类可当做基类来引用，新类可当做派生类来引用继承具有传递性面向对象程序设计继承面向对象程序设计封装性所谓封装，指的就是类中定义的数据只能被类中定义的方法所访问，除此之外别无它法封装的结果实际上隐蔽了复杂性，并提供了代码重用性，从而降低了软件开发的难度。多态性对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时，可导致完全不同的行动，该现象称为多态性面向对象程序设计封装性面向对象程序设计面向对象方法的优点：与人类习惯的思维方法一致稳定性好可重用性好易于开发大型软件产品可维护性好面向对象程序设计面向对象方法的优点：5.1.3程序设计语言程序设计语言就是用于书写计算机程序的一组记号和一组规则。分类：机器语言汇编语言高级语言5.1.3程序设计语言程序设计语言就是用于书写计算机程序的(1)机器语言

由0、1代码组成，能被计算机硬件系统直接识别和执行的计算机语言，不需要翻译。特点：占用空间小、执行速度快不易学习和修改不同类型机器的机器语言不同，通用性差程序设计语言(1)机器语言由0、1代码组成，能被计算机硬件系统直机器语言程序注释1011000000001000把8存放到累加器A中0010110000001010将10与累加器中的8相加，结果存在A中11110100程序结束机器语言实例机器语言程序注释1011000000001000把8存放到(2)汇编语言（符号语言）程序设计语言

用助记符代替机器语言中的指令和数据特点：易修改，保持速度快，占用空间小不同类型机器的汇编语言不同，通用性差实例：8+10加法题MOVAX,8HMOVBX,0AHADDBX,AX(2)汇编语言（符号语言）程序设计语言用助记符代替机器语(3)高级语言程序设计语言

由贴近自然语言的“词”和“数学公式”组成

特点：

易学、易读，易修改通用性好，不依赖于机器具有很强的通用性和可移植性

实例：c=8+10(3)高级语言程序设计语言由贴近自然语言的“词”和“常用的程序设计语言面向过程语言Fortran、Pascal、C等面向对象语言C++、java常用的程序设计语言面向过程语言语言处理系统的作用就是把程序语言编写的程序变换成计算机上执行的程序分类汇编程序编译程序解释程序程序设计语言处理系统语言处理系统的作用就是把程序语言编写的程序变换成计算机上执行汇编语言源程序机器语言程序汇编程序

汇编程序程序设计语言处理系统汇编程序汇编程序程序设计语言处理系统高级语言源程序高级语言目标源程序程序编译程序连接程序可执行程序计算结果数据解释程序计算结果数据编译程序：执行速度快，但占用内存多，可脱离编译程序和源程序独立存在并反复使用.如：C/C++、Pascal、FORTRAN等解释程序：边解释边执行，便于查错，占用内存少，执行效率低、速度慢。如：BASIC语言程序设计语言处理系统编译程序连接程序可执行计算数据解释程序计算数据编译程序：执行编译程序与解释程序的区别编译程序与解释程序的区别5.2.1

算法的概念5.2.2

算法的表示5.2.3

常用算法介绍5.2算法概述5.2.1算法的概念5.2算法概述算法算法(Algorithm)：算法就是一个有穷规则的集合，其中的规则确定了一个解决某一特定类型问题的运算序列。5.2.1算法的概念算法5.2.1算法的概念算法的特性①有限性②确定性③可行性④输入⑤输出算法的特性①有限性算法的表示方法算法的表示方法：自然语言；程序流程图；N-S流程图；伪代码；算法的表示方法算法的表示方法：自然语言使用自然语言描述求解sum=1+2+3+4+5……+（n-1）+n的方法。①确定一个n的值；②设等号右边的算式项中的初始值i为1；③设sum的初始值为0；④如果i≤n时，执行⑤，否则转出执行⑧；⑤计算sum加上i的值后，重新赋值给sum；⑥计算i加1，然后将值重新赋值给i；⑦转去执行④；⑧输出sum的值，算法结束。自然语言使用自然语言描述求解sum=1+2+3+4+5……+自然语言自然语言描述方法的缺点：自言语言的歧异性容易导致算法执行的不确定性。自然语言的语句一般太长，从而导致了用自然语言描述的算法太长。由于自然语言表示的串行性，因此，当一个算法中循环和分支较多时就很难清晰地表示出来。自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。自然语言自然语言描述方法的缺点：程序流程图程序流程图符号程序流程图程序流程图符号程序流程图以求解sum=1+2+3+4+5……+（n-1）+n为例来介绍算法的流程图描述方法程序流程图以求解sum=1+2+3+4+5……+（n-1）+N-S流程图N-S流程图简称N-S图，也被称为盒图。N-S图是在1973年，由美国学者I.Nassi和B.Shneiderman提出来的，并分别取两人名字的首字母来进行命名。N-S图是在程序流程图的基础上去掉流程线，将全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框的一种算法表示方法。即由一些基本的框组成的一个大框。N-S流程图N-S流程图简称N-S图，也被称为盒图。N-S图N-S流程图N-S流程图的三大结构顺序结构选择结构循环结构N-S流程图N-S流程图的三大结构N-S流程图写出求sum=1+2+3+4+5……+（n-1）+n的N-S图的描述方法N-S流程图写出求sum=1+2+3+4+5……+（n-1）伪代码用流程图或N-S图来描述算法虽然形象直观，但在算法设计过程中使用起来并不十分方便，特别是当算法稍微复杂一点时，不易修改。在实际的算法设计中，常常使用自然语言或计算机语言或类计算机语言来描述。这里的类计算机语言是一种非计算机语言，借用了一些高级语言的某些成分，没有加入严格的规则，而且不能够被计算机所接受，称其为“伪代码”。伪代码用流程图或N-S图来描述算法虽然形象直观，但在算法设计伪代码写出求sum=1+2+3+4+5……+（n-1）+n的伪代码的描述方法(1)算法开始；(2)输入n的值；(3)i←1；(4)sum←0；(5)dowhilei<=n(6){sum←sum+i；(7)

i←i+1；}(8)输出sum的值；(9)算法结束；伪代码写出求sum=1+2+3+4+5……+（n-1）+n的5.2.3常用算法介绍1.枚举法2.递推法3.求最大值、最小值问题4.交换两个变量的值5.排序算法6.查找算法5.2.3常用算法介绍1.枚举法枚举法又称为穷举法基本思想：根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况均通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。特点：算法简单，容易理解，运算量大1.枚举法枚举法又称为穷举法1.枚举法1.枚举法应用：百钱买百鸡问题假定公鸡每只5元，母鸡每只3元，小鸡3只1元。现有100元钱要求买100只鸡，问共有几种购鸡方案？问题分析：根据题目，设公鸡、母鸡、小鸡各为x，y，z只，列出方程为： x+y+z=100 5x+3y+z/3=1001.枚举法应用：百钱买百鸡问题巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是一种重要的算法设计策略：①穷举法几乎可以通用于任何领域的问题求解，可能是唯一一种解决所有问题的一般性方法②即使效率低下，仍可用穷举法求解一些小规模的问题实例；③如果解决的问题实例不多，而穷举法可用一种可接受的速度对问题求解，那么花时间去设计一个更高效地算法是得不偿失的。

1.枚举法[思考题]举例说明生活中的穷举法应用。巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是递推法又称为迭代法基本思想：利用问题本身所具有的某种递推关系求解问题。从初值出发，归纳出新值与旧值间存在的关系，从而把一个复杂的计算过程转换为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。2.递推法递推法又称为迭代法2.递推法2.递推法

2.递推法

基本思想：采用如同打擂台的方法。在n个数中，先假设第一个数为最大值，称为擂主，依次同第2，3，……，n个数据逐一比较，一旦某个数大，马上替换擂主；所有值比较完，最大值也就获得。求最小值问题则先假设第一个数为最小值。3.求最大值、最小值问题基本思想：采用如同打擂台的方法。在n个数中，先假设第一个数为3.求最大值、最小值问题应用：对输入的若干个学生成绩，求出最高分和最低分。max=min=a[0]；用max依次与后续的成绩进行对比，若比max大则将相应值赋值给max；用min依次与后续的成绩进行对比，若比min小则将相应值赋值给min；最后输出max和min的值。3.求最大值、最小值问题应用：对输入的若干个学生成绩，求出最基本思想：由于计算机内存的特点，因此，计算机中交换两个变量的值只能采取间接交换的方法。4.交换两个变量的值基本思想：由于计算机内存的特点，因此，计算机中交换两个变量的4.交换两个变量的值有黑和蓝两个墨水瓶，但却把黑墨水装在了蓝墨水的瓶子里，而把蓝墨水错装在了黑墨水瓶子里，要求将其互换。4.交换两个变量的值有黑和蓝两个墨水瓶，但却把黑墨水装在了蓝4.交换两个变量的值应用：a=5,b=10，交换a，b的值并输出引入一个新的变量c；将a的值赋值给c；将b的值赋值给a；将c的值赋值给b；4.交换两个变量的值应用：a=5,b=10，交换a，b的值选择排序的基本思想：每一轮从待排序列中选取一个关键码最小的记录与第i个位置的记录进行交换，也即第一轮从n个记录中选取关键码最小的记录与第1个位置的记录交换，第二轮从剩下的n-1个记录中选取关键码最小的记录与第2个位置的记录进行交换，直到整个序列的记录选完5.排序算法选择排序的基本思想：每一轮从待排序列中选取一个关键码最小的记5.排序算法【例5.6】给出一组关键字(28，6，72，85，39，41，13，20)，排序后得到(6，13，20，28，39，41，72，85)，其选择排序过程如下5.排序算法【例5.6】给出一组关键字(28，6，72，85查找是指从给定的数据结构中查找某个给定的值。常用的查找算法有顺序查找、二分查找等等。顺序查找是直接从头到尾搜索集合中满足条件的值。二分查找是必须首先将集合按照降序或升序排序，然后利用折半技术搜索集合中满足条件的值。6.查找算法查找是指从给定的数据结构中查找某个给定的值。6.查找算法6.查找算法二分查找的方法如下：将x与线性表的中间项进行比较；若中间项的值等于x，则说明查找到，查找结束；若x小于中间项的值，则在线性表的前半部分以相同的方法进行查找。若x大于中间项的值，则在线性表的后半部分以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0为止。6.查找算法二分查找的方法如下：【例5.7】有序表中关键字序列为3，10，13，17，40，43，50，70，要查找关键字值为43的数据元素6.查找算法【例5.7】有序表中关键字序列为3，10，13，17，40，5.3.1

软件危机5.3.2

软件工程5.3.3

软件生存周期5.3软件工程概述5.3.1软件危机5.3软件工程概述5.3.1软件危机软件危机是指在计算机软件的开发和维护过程中所遇到的一系列严重问题，主要有以下一些表现形式。①软件开发费用和进度失控。②软件的可靠性差。③生产出来的软件难以维护。④用户对“已完成”的系统不满意现象经常发生。5.3.1软件危机软件危机是指在计算机软件的开发和维护过程5.3.2软件工程IEEE给出的软件工程的定义是：软件工程是将系统化的、规范的、可度量的方法应用于软件的开发、运行、维护过程，即将工程化应用于软件中的方法的研究。人们给出的一般定义是：软件工程是一门旨在生产无故障的、积极交付的、在预算之内的和满足用户需求的软件的学科。实质上，软件工程就是采用工程的概念、原理、技术和方法来开发与维护软件，把经过实践考验而证明正确的管理方法和最先进的软件开发技术结合起来，应用到软件开发和维护过程中，来解决软件危机问题。5.3.2软件工程IEEE给出的软件工程的定义是：软件工程5.3.2软件工程软件工程包括三要素：方法、工具和过程。软件工程的目标是：在给定成本、进度的前提下，开发出具有可修改性、有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性并且满足用户需求的软件产品。追求这些目标有助于提高软件产品的质量和开发效率，减少维护的困难软件工程的原则：抽象、信息隐藏、模块化、局部化、一致性、确定性、完备性和可验证性5.3.2软件工程软件工程包括三要素：方法、工具和过程。5.3.3软件生存周期软件定义期——“做什么”，确定工程的总目标和可行性，导出实现工程目标应使用的策略及系统必须完成的功能，估计完成工程需要的资源和成本，制定进度表。软件开发期——“如何做”，具体设计和实现在前一个使其定义的软件软件维护期——“如何长久的做”，使软件持久地满足用户的需求。5.3.3软件生存周期软件定义期——“做什么”，确定工程的软件过程模型定义：从软件项目需求定义直至软件运行维护为止，跨越整个生存期的系统开发、运作和维护所实施的全部过程、活动和任务的结构框架。常见的软件过程模型：瀑布模型原型模型增量模型螺旋模型软件过程模型定义：从软件项目需求定义直至软件运行维护为止，跨瀑布模型（WaterfallModel）1970年提出，又称线性模型，是历史上第一个正式使用并得到业界广泛认可的软件开发模型具体划分：制定计划、需求分析、软件设计、程序编写、软件测试、运行维护规定了自上而下、相互衔接的固定次序瀑布模型（WaterfallModel）1970年提出，又原型模型原型模型的基本思想是：原型模型从需求采集开始，如图所示，然后是“快速设计”，集中于软件中那些对用户可见的部分的表示，并最终导致原型的创建。

原型模型原型模型的基本思想是：原型模型从需求采集开始，如图所螺旋模型1988年由TRW公司的B.Boehm提出，将瀑布模型和演化模型结合，并强调了其他模型都忽略了的风险分析。螺旋模型1988年由TRW公司的B.Boehm提出，将瀑布模并发模型并发模型也称并发工程，它表达了在软件项目任一阶段的活动之间存在的并发性。并发模型并发模型也称并发工程，它表达了在软件项目任一阶段的活基于构件的开发模型基于构件的开发（CBD）模型（如图5.18所示）融合了螺旋模型的许多特征，本质上是演化型的，要求软件创建迭代过程，但是基于构件的开发模型是利用预先封装好的软件构件来构造应用的。基于构件的开发模型基于构件的开发（CBD）模型（如图5.18小结程序设计的基本方法程序设计语言算法的表示方法常用的算法软件工程软件生存周期小结程序设计的基本方法5.1程序设计概述5.2算法概述5.3软件工程概述第5章程序设计基础5.1程序设计概述第5章程序设计基础5.1.1

程序设计的基本过程5.1.2

程序设计的方法5.1.3

程序设计语言5.1程序设计概述5.1.1程序设计的基本过程5.1程序设计概述5.1.1程序设计的基本过程程序设计：编写程序的过程程序设计过程包括分析、设计、编码、测试、编写文档等不同阶段5.1.1程序设计的基本过程程序设计：编写程序的过程5.1.2程序设计的方法结构化程序设计方法面向对象程序设计方法5.1.2程序设计的方法结构化程序设计方法结构化程序设计结构化程序设计的原则自顶向下逐步细化模块化限制使用goto语句结构化程序设计结构化程序设计的原则结构化程序设计结构化程序设计的基本结构顺序结构选择结构循环结构结构化程序设计结构化程序设计的基本结构结构化程序设计顺序结构按照程序语句的书写顺序一条一条的执行最基本、最常用的结构结构化程序设计顺序结构结构化程序设计选择结构（分支结构）根据设定的条件，判断应该执行哪一条语句包括单分支结构、双分支结构和多分支结构结构化程序设计选择结构（分支结构）结构化程序设计循环结构（重复结构）根据给定的条件，判断是否需要重复执行相同的程序段分为当型循环结构和直到型循环结构

结构化程序设计循环结构（重复结构）面向对象程序设计结构化程序设计又称为面向过程的程序设计面向对象程序设计方法模拟人们理解和处理客观世界的方式来分析问题，把系统视为一系列对象的集合，分析者、设计者和编程者都可以使用相同的概念，从而使面向对象的程序设计方法能比较自然地模拟客观世界的活动，使问题描述空间与解空间在结构上尽可能一致。面向对象程序设计结构化程序设计又称为面向过程的程序设计面向对象的基本概念对象：客观世界中的任何实体，既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界和意义的东西。对象的特点：标识唯一性分类型多态性封装性模块独立性面向对象的基本概念对象：客观世界中的任何实体，既可以是具体的面向对象程序设计类：类是对象的抽象，它描述了该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例消息面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制来协助完成，这种机制称为“消息”面向对象程序设计类：面向对象程序设计继承使用已有的类定义作为基础建立新类的定义技术已有的类可当做基类来引用，新类可当做派生类来引用继承具有传递性面向对象程序设计继承面向对象程序设计封装性所谓封装，指的就是类中定义的数据只能被类中定义的方法所访问，除此之外别无它法封装的结果实际上隐蔽了复杂性，并提供了代码重用性，从而降低了软件开发的难度。多态性对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时，可导致完全不同的行动，该现象称为多态性面向对象程序设计封装性面向对象程序设计面向对象方法的优点：与人类习惯的思维方法一致稳定性好可重用性好易于开发大型软件产品可维护性好面向对象程序设计面向对象方法的优点：5.1.3程序设计语言程序设计语言就是用于书写计算机程序的一组记号和一组规则。分类：机器语言汇编语言高级语言5.1.3程序设计语言程序设计语言就是用于书写计算机程序的(1)机器语言

由0、1代码组成，能被计算机硬件系统直接识别和执行的计算机语言，不需要翻译。特点：占用空间小、执行速度快不易学习和修改不同类型机器的机器语言不同，通用性差程序设计语言(1)机器语言由0、1代码组成，能被计算机硬件系统直机器语言程序注释1011000000001000把8存放到累加器A中0010110000001010将10与累加器中的8相加，结果存在A中11110100程序结束机器语言实例机器语言程序注释1011000000001000把8存放到(2)汇编语言（符号语言）程序设计语言

用助记符代替机器语言中的指令和数据特点：易修改，保持速度快，占用空间小不同类型机器的汇编语言不同，通用性差实例：8+10加法题MOVAX,8HMOVBX,0AHADDBX,AX(2)汇编语言（符号语言）程序设计语言用助记符代替机器语(3)高级语言程序设计语言

由贴近自然语言的“词”和“数学公式”组成

特点：

易学、易读，易修改通用性好，不依赖于机器具有很强的通用性和可移植性

实例：c=8+10(3)高级语言程序设计语言由贴近自然语言的“词”和“常用的程序设计语言面向过程语言Fortran、Pascal、C等面向对象语言C++、java常用的程序设计语言面向过程语言语言处理系统的作用就是把程序语言编写的程序变换成计算机上执行的程序分类汇编程序编译程序解释程序程序设计语言处理系统语言处理系统的作用就是把程序语言编写的程序变换成计算机上执行汇编语言源程序机器语言程序汇编程序

汇编程序程序设计语言处理系统汇编程序汇编程序程序设计语言处理系统高级语言源程序高级语言目标源程序程序编译程序连接程序可执行程序计算结果数据解释程序计算结果数据编译程序：执行速度快，但占用内存多，可脱离编译程序和源程序独立存在并反复使用.如：C/C++、Pascal、FORTRAN等解释程序：边解释边执行，便于查错，占用内存少，执行效率低、速度慢。如：BASIC语言程序设计语言处理系统编译程序连接程序可执行计算数据解释程序计算数据编译程序：执行编译程序与解释程序的区别编译程序与解释程序的区别5.2.1

算法的概念5.2.2

算法的表示5.2.3

常用算法介绍5.2算法概述5.2.1算法的概念5.2算法概述算法算法(Algorithm)：算法就是一个有穷规则的集合，其中的规则确定了一个解决某一特定类型问题的运算序列。5.2.1算法的概念算法5.2.1算法的概念算法的特性①有限性②确定性③可行性④输入⑤输出算法的特性①有限性算法的表示方法算法的表示方法：自然语言；程序流程图；N-S流程图；伪代码；算法的表示方法算法的表示方法：自然语言使用自然语言描述求解sum=1+2+3+4+5……+（n-1）+n的方法。①确定一个n的值；②设等号右边的算式项中的初始值i为1；③设sum的初始值为0；④如果i≤n时，执行⑤，否则转出执行⑧；⑤计算sum加上i的值后，重新赋值给sum；⑥计算i加1，然后将值重新赋值给i；⑦转去执行④；⑧输出sum的值，算法结束。自然语言使用自然语言描述求解sum=1+2+3+4+5……+自然语言自然语言描述方法的缺点：自言语言的歧异性容易导致算法执行的不确定性。自然语言的语句一般太长，从而导致了用自然语言描述的算法太长。由于自然语言表示的串行性，因此，当一个算法中循环和分支较多时就很难清晰地表示出来。自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。自然语言自然语言描述方法的缺点：程序流程图程序流程图符号程序流程图程序流程图符号程序流程图以求解sum=1+2+3+4+5……+（n-1）+n为例来介绍算法的流程图描述方法程序流程图以求解sum=1+2+3+4+5……+（n-1）+N-S流程图N-S流程图简称N-S图，也被称为盒图。N-S图是在1973年，由美国学者I.Nassi和B.Shneiderman提出来的，并分别取两人名字的首字母来进行命名。N-S图是在程序流程图的基础上去掉流程线，将全部算法写在一个矩形框内，在该框内还可以包含其他的从属于它的框的一种算法表示方法。即由一些基本的框组成的一个大框。N-S流程图N-S流程图简称N-S图，也被称为盒图。N-S图N-S流程图N-S流程图的三大结构顺序结构选择结构循环结构N-S流程图N-S流程图的三大结构N-S流程图写出求sum=1+2+3+4+5……+（n-1）+n的N-S图的描述方法N-S流程图写出求sum=1+2+3+4+5……+（n-1）伪代码用流程图或N-S图来描述算法虽然形象直观，但在算法设计过程中使用起来并不十分方便，特别是当算法稍微复杂一点时，不易修改。在实际的算法设计中，常常使用自然语言或计算机语言或类计算机语言来描述。这里的类计算机语言是一种非计算机语言，借用了一些高级语言的某些成分，没有加入严格的规则，而且不能够被计算机所接受，称其为“伪代码”。伪代码用流程图或N-S图来描述算法虽然形象直观，但在算法设计伪代码写出求sum=1+2+3+4+5……+（n-1）+n的伪代码的描述方法(1)算法开始；(2)输入n的值；(3)i←1；(4)sum←0；(5)dowhilei<=n(6){sum←sum+i；(7)

i←i+1；}(8)输出sum的值；(9)算法结束；伪代码写出求sum=1+2+3+4+5……+（n-1）+n的5.2.3常用算法介绍1.枚举法2.递推法3.求最大值、最小值问题4.交换两个变量的值5.排序算法6.查找算法5.2.3常用算法介绍1.枚举法枚举法又称为穷举法基本思想：根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况均通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。特点：算法简单，容易理解，运算量大1.枚举法枚举法又称为穷举法1.枚举法1.枚举法应用：百钱买百鸡问题假定公鸡每只5元，母鸡每只3元，小鸡3只1元。现有100元钱要求买100只鸡，问共有几种购鸡方案？问题分析：根据题目，设公鸡、母鸡、小鸡各为x，y，z只，列出方程为： x+y+z=100 5x+3y+z/3=1001.枚举法应用：百钱买百鸡问题巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是一种重要的算法设计策略：①穷举法几乎可以通用于任何领域的问题求解，可能是唯一一种解决所有问题的一般性方法②即使效率低下，仍可用穷举法求解一些小规模的问题实例；③如果解决的问题实例不多，而穷举法可用一种可接受的速度对问题求解，那么花时间去设计一个更高效地算法是得不偿失的。

1.枚举法[思考题]举例说明生活中的穷举法应用。巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是递推法又称为迭代法基本思想：利用问题本身所具有的某种递推关系求解问题。从初值出发，归纳出新值与旧值间存在的关系，从而把一个复杂的计算过程转换为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。2.递推法递推法又称为迭代法2.递推法2.递推法

2.递推法

基本思想：采用如同打擂台的方法。在n个数中，先假设第一个数为最大值，称为擂主，依次同第2，3，……，n个数据逐一比较，一旦某个数大，马上替换擂主；所有值比较完，最大值也就获得。求最小值问题则先假设第一个数为最小值。3.求最大值、最小值问题基本思想：采用如同打擂台的方法。在n个数中，先假设第一个数为3.求最大值、最小值问题应用：对输入的若干个学生成绩，求出最高分和最低分。max=min=a[0]；用max依次与后续的成绩进行对比，若比max大则将相应值赋值给max；用min依次与后续的成绩进行对比，若比min小则将相应值赋值给min；最后输出max和min的值。3.求最大值、最小值问题应用：对输入的若干个学生成绩，求出最基本思想：由于计算机内存的特点，因此，计算机中交换两个变量的值只能采取间接交换的方法。4.交换两个变量的值基本思想：由于计算机内存的特点，因此，计算机中交换两个变量的4.交换两个变量的值有黑和蓝两个墨水瓶，但却把黑墨水装在了蓝墨水的瓶子里，而把蓝墨水错装在了黑墨水瓶子里，要求将其互换。4.交换两个变量的值有黑和蓝两个墨水瓶，但却把黑墨水装在了蓝4.交换两个变量的值应用：a=5,b=10，交换a，b的值并输出引入一个新的变量c；将a的值赋值给c；将b的值赋值给a；将c的值赋值给b；4.交换两个变量的值应用：a=5,b=10，交换a，b的值选择排序的基本思想：每一轮从待排序列中选取一个关键码最小的记录与第i个位置的记录进行交换，也即第一轮从n个记录中选取关键码最小的记录与第1个位置的记录交换，第二轮从剩下的n-1个记录中选取关键码最小的记录与第2个位置的记录进行交换，直到整个序列的记录选完5.排序算法选择排序的基本思想：每一轮从待排序列中选取一个关键码最小的记5.排序算法【例5.6】给出一组关键字(28，6，72，85，39，41，13，20)，排序后得到(6，13，20，28，39，41，72，85)，其选择排序过程如下5.排序算法【例5.6】给出一组关键字(28，6，72，85查找是指从给定的数据结构中查找某个给定的值。常用的查找算法有顺序查找、二分查找等等。顺序查找是直接从头到尾搜索集合中满足条件的值。二分查找是必须首先将集合按照降序或升序排序，然后利用折半技术搜索集合中满足条件的值。6.查找算法查找是指从给定的数据结构中查找某个给定的值。6.查找算法6.查找算法二分查找的方法如下：将x与线性表的中间项进行比较；若中间项的值等于x，则说明查找到，查找结束；若x小于中间项的值，则在线性表的前半部分以相同的方法进行查找。若x大于中间项的值，则在线性表的后半部分以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0为止。6.查找算法二分查找的方法如下：【例5.7】有序表中关键字序列为3，10，13，17，40，43，50，70，要查找关键字值为43的数据元素6.查找算法【例5.7】有序表中关键字序列为3，10，13，17，40，5.3.1

软件危机5.3.2

软件工程5.3.3

软件生存周