大学计算机基础07.算法与程序设计基础课件

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