大学计算机基础07算法与程序设计基础课件.pptx
第7章 算法与程序设计基础,主编：齐晖,第7章 算法与程序设计基础主编：齐晖,中原工学院计算机基础教学部,本章知识点结构,中原工学院计算机基础教学部本章知识点结构程序和程序设计语言算,中原工学院计算机基础教学部,7.1 程序和程序设计语言,程序的一般概念程序（Program）是计算机可以执行的指令或语句序列。程序是用计算机解决现实生活中的一个实际问题而编制的。,中原工学院计算机基础教学部7.1 程序和程序设计语言程序的一,7.1 程序和程序设计语言,设计、编制、调试程序的过程称为程序设计。编写程序所用的语言即为程序设计语言，它为程序设计提供了一定的语法和语义，所编写出的程序必须严格遵守它的语法规则，这样编写出来的程序才能被计算机所接受、运行，并产生预期的结果。,中原工学院计算机基础教学部,7.1 程序和程序设计语言设计、编制、调试程序的过程称为程序,程序设计语言概述,中原工学院计算机基础教学部,程序设计语言是生成和开发程序的工具。计算机程序设计语言的发展，经历了从机器语言、汇编语言到高级语言的历程。,程序设计语言概述中原工学院计算机基础教学部程序设计语言是生成,程序设计语言概述,1机器语言阶段计算机内部采用二进制表示信息。机器语言（Machine Language）是用二进制代码表示的、计算机能直接识别和执行的一种机器指令的集合。它是面向机器的语言，是计算机唯一可直接识别的语言。用机器语言编写的程序称为机器语言程序（又称目标程序）。,中原工学院计算机基础教学部,程序设计语言概述1机器语言阶段中原工学院计算机基础教学部,程序设计语言概述,例如， 某种计算机的指令为：10110110 00000000 表示进行一次加法操作10110101 00000000 表示进行一次减法操作机器语言的优点是不需要翻译而能够直接被计算机接收和识别，由于计算机能够直接执行机器语言程序，所以其运行速度最快；缺点是机器语言通用性极差，用机器指令编制出来的程序可读性差，程序难以修改、交流和维护。,中原工学院计算机基础教学部,程序设计语言概述例如， 某种计算机的指令为：中原工学院计算机,程序设计语言概述,2汇编语言阶段人们采用能反映指令功能的助记符来表达计算机语言，称为汇编语言（Assembly Language）。例如，用汇编语言编写的程序如下： MOV AL 10D /* 将十进制数10送往累加器*/ SUB AL 12D /* 从累加器中减去十进制数12*/,中原工学院计算机基础教学部,程序设计语言概述2汇编语言阶段中原工学院计算机基础教学部,程序设计语言概述,用汇编语言编写程序比用机器语言要容易得多，但计算机不能直接执行汇编语言程序。必须把它翻译成相应的机器语言程序才能运行。将汇编语言程序翻译成机器语言程序的过程叫作汇编，汇编过程是由计算机运行汇编程序自动完成的。,中原工学院计算机基础教学部,程序设计语言概述用汇编语言编写程序比用机器语言要容易得多，但,程序设计语言概述,3高级语言阶段机器语言和汇编语言都是面向机器（计算机硬件）的语言（低级语言），受机器硬件的限制，通用性差，也不容易学习，一般只适用于专业人员。人们意识到，应该设计一种语言：它接近于数学语言或自然语言，同时又不依赖于计算机的硬件，编出的程序能在所有的计算机上通用。,中原工学院计算机基础教学部,程序设计语言概述3高级语言阶段中原工学院计算机基础教学部,程序设计语言概述,用高级语言编写的程序即源程序必须翻译成计算机能识别和执行的二进制机器指令，才能被计算机执行。由源程序翻译成的机器语言程序称为目标程序。高级语言源程序转换成目标程序有两种方式：解释方式和编译方式。高级语言是第三代计算机语言。目前广泛应用的高级语言有多种，如Visual Basic.NET、FORTRAN、C、C+、JAVA及C#等。,中原工学院计算机基础教学部,程序设计语言概述用高级语言编写的程序即源程序必须翻译成计算机,程序设计的基本步骤,中原工学院计算机基础教学部,程序设计的基本步骤中原工学院计算机基础教学部,常用程序设计语言,1FORTRAN语言2BASIC和VB语言3Java语言4C语言和C+语言除了以上介绍的几种常用程序语言外，具有影响的程序语言还有LISP语言（适用于符号操作和表处理，主要用于人工智能领域）、PROLOG语言（一种逻辑式编程语言，主要用于人工智能领域）、Ada语言（一种模块化语言，且易于控制并行任务和处理异常情况，在飞行器控制之类的软件中使用）、MATLAB（一种面向向量和矩阵运算的提供数据可视化等功能的数值计算语言，在工业界和学术界很流行）等，在此不再一一介绍。,中原工学院计算机基础教学部,常用程序设计语言1FORTRAN语言中原工学院计算机基础教,7.2 算法的概念与描述,在程序设计中，程序设计者必须指定计算机执行的具体步骤、怎样设计这些步骤、怎样保证它的正确性和具有较高的效率，这就是算法需要解决的问题。,中原工学院计算机基础教学部,7.2 算法的概念与描述中原工学院计算机基础教学部,算法的概念及特征,1算法的概念 算法，是指为了解决一个问题而采取的方法和步骤。当利用计算机来解决一个具体问题时，也要首先确定算法。,中原工学院计算机基础教学部,算法的概念及特征1算法的概念中原工学院计算机基础教学部,算法的概念及特征,2算法的特征 （1）有穷性（Finiteness）算法的有穷性是指算法必须能在执行有限个步骤之后终止。（2）确定性（Definiteness）算法的每一步骤必须有确切的定义。（3）输入项（Input）一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。（4）输出项（Output）一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。（5）可行性（Effectiveness）算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称为有效性）。,中原工学院计算机基础教学部,算法的概念及特征2算法的特征中原工学院计算机基础教学部,算法的概念及特征,3算法的评价算法分析的目的在于选择合适的算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。（1）时间复杂度（2）空间复杂度,中原工学院计算机基础教学部,算法的概念及特征3算法的评价中原工学院计算机基础教学部,算法的描述,1自然语言2流程图3N-S图 4伪代码,中原工学院计算机基础教学部,算法的描述1自然语言中原工学院计算机基础教学部,算法举例,1枚举法枚举法又称为穷举法。2查找算法查找也可称检索，是在数据集（大量的元素）中找到某个特定的元素的过程。查找算法（Search Algorithms）是在程序设计中常用到的算法之一。3排序算法（1）冒泡排序（2）插入排序（3）选择排序,中原工学院计算机基础教学部,算法举例1枚举法中原工学院计算机基础教学部,7.3 结构化程序设计方法,结构化程序设计的原则结构化程序设计基本思想是采用“自顶向下，逐步求精”的程序设计方法和“单入口、单出口”的控制结构。结构化程序的基本结构和特点解决任何一个复杂的问题，都可以由3种基本结构来完成：顺序结构、选择结构、循环结构。,中原工学院计算机基础教学部,7.3 结构化程序设计方法结构化程序设计的原则中原工学院计,7.47.4 面向对象的程序设计方法,面向对象程序设计（Object Oriented Programming，OOP）是软件系统设计与实现的方法，这种新方法既吸取了结构化程序设计的绝大部分优点，又考虑了现实世界与面向对象空间的映射关系而提出的一种新思想，所追求的目标是将现实世界的问题求解尽可能的简单化。,中原工学院计算机基础教学部,7.47.4 面向对象的程序设计方法面向对象程序设计（Ob,基本概念,1. 对象2. 类3消息4 面向对象程序设计面向对象程序设计的优点表现在：可以解决软件工程的两个主要问题软件复杂性控制和软件生产效率的提高，另外它还符合人类的思维方式，能自然地表现出现实世界的实体和问题。,中原工学院计算机基础教学部,基本概念1. 对象中原工学院计算机基础教学部,面向对象程序设计的特点,面向对象程序设计具有封装、继承、多态三大特性。1封装性封装是一种数据隐藏技术，在面向对象程序设计中可以把数据和与数据有关的操作集中在一起形成类，将类的一部分属性和操作隐藏起来，不让用户访问；另一部分作为类的外部接口，用户可以访问。,中原工学院计算机基础教学部,面向对象程序设计的特点面向对象程序设计具有封装、继承、多态三,面向对象程序设计的特点,2继承性在面向对象程序设计中，继承是指新建的类从已有的类那里获得已有的属性和操作。3. 多态性面向对象的通信机制是消息，面向对象技术是通过向未知对象发送消息来进行程序设计的，当一个对象发出消息时，对于相同的消息，不同的对象具有不同的反应能力。这样，一个消息可以产生不同的响应效果，这种现象称为多态性。,中原工学院计算机基础教学部,面向对象程序设计的特点2继承性中原工学院计算机基础教学部,可视化程序设计,可视化程序设计利用可视化程序设计语言本身所提供的各种工具构造应用程序的各种界面，使得整个界面设计是在“所见即所得”的可视化状态下完成。相对于编写代码方式的程序设计而言，可视化程序设计具有直观形象、方便高效等优点。,中原工学院计算机基础教学部,可视化程序设计中原工学院计算机基础教学部,习题,一、选择题1编写程序时，不需要了解计算机内部结构的语言是（ ）A机器语言B汇编语言C高级语言D指令系统2能够把由高级语言编写的源程序翻译成目标程序的系统软件叫（ ）。A解释程序 B汇编程序C操作系统D编译程序3结构化程序设计主要强调的是（ ）。A程序的规模 B程序的可读性C程序的执行效率 D程序的可移植性4下面描述中，符合结构化程序设计风格的是（ ）。A使用顺序、选择和循环三种基本控制结构表示程序的控制逻辑 B模块只有一个入口，可以有多个出口 C注重提高程序的执行效率D结构化程序设计的结构简单 5在下列选项中，哪个不是一个算法一般应该具有的基本特征（ ）。 A确定性B可行性C无穷性D输出项,中原工学院计算机基础教学部,6结构化程序设计方法的主要原则有下列4项，不正确的是（ ）。A自下向上B逐步求精C模块化D单入口、单出口7在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送（ ）。A调用语句 B命令C口令 D消息8下列程序段的时间复杂度是（ ）。t=i;i=j;j=t;AO(1) BO(3) CO(n) DO(3n)9下列程序段的时间复杂度是（ ）。intbubbleSort(arraya) for (j=1; jai+1) ai=ai+1 AO(n2) BO(2n) CO(n) DO(n(n-1)/2)10一位同学用C语言编写了一个程序，编译和连接都通过了，但就是得不到正确结果，那么下列说法正确的是（ ）A程序正确，机器有问题 B程序有语法错误C程序有逻辑错误 D编译程序有错误,习题一、选择题中原工学院计算机基础教学部6结构化程序设计方,习题,二、填空题1程序设计的基本步骤是分析问题、确定数学模型、。2用高级语言编写的程序称为，把翻译后的机器语言程序叫作。3结构化程序设计的3种基本逻辑结构为顺序、选择和。4面向对象程序设计以作为程序的主体。5在面向对象方法中，信息隐蔽是通过对象的性来实现的。6在最坏情况下，冒泡排序的比较次数为。,中原工学院计算机基础教学部,习题二、填空题中原工学院计算机基础教学部,习题,三、问答题1什么是程序？什么是程序设计？2什么是算法？它有何特征？如何描述算法？3简述冒泡排序、插入拍讯、折半查询的基本思想。4在一档电视节目中，有一个猜商品价格的游戏，竟猜者如在规定的时间内大体猜出某种商品的价格，就可获得该件商品。现有一件商品，其价格在08 000元之间，采取怎样的策略才能在较短的时间内说出正确（大体上）的答案呢？请设计算法并画出相应的N-S流程图。5什么是可视化程序设计？它与面向对象程序设计有何区别和联系是什么？,中原工学院计算机基础教学部,习题三、问答题中原工学院计算机基础教学部,
