37330-00王移芝-大学计算机4版第7章

第7章程序设计基础,学习内容,什么是算法算法的基本特征及评价算法的描述工具,学习内容,1.认识算法,算法（Algorithm）是一组明确的、可以执行的步骤的有序集合。“有序集合”说明算法中的步骤是有顺序关系的。,1.认识算法什么是算法,算法的概念要求步骤集是有序的，这就要求算法中的各个步骤必须拥有定义完好的、顺序执行的结构。,算法概念,方法一：步骤1：先求1与2的和，得到结果3；步骤2：将步骤1得到的和与3相加，得到结果6；步骤3：将步骤2得到的和与4相加，得到结果10；步骤9：将步骤8得到的和与10相加，得到结果55。方法二：步骤1：分别求1与9的和，2与8的和，3与7的和，4与6的和；步骤2：求5个10的和；步骤3：将步骤2得到的和与5相加，得到结果55。,1.认识算法什么是算法,【示例7-1】求1+2+3+10，即,设变量sum为被加数，变量i为加数，用循环算法来求结果。可以将方法一改写如下：步骤1：使sum为1，写成1=sum；步骤2：使i为1，写成2=n；步骤3：将sum与i相加，结果仍放到变量sum中，写成sum+n=sum；步骤4：使i的值加1，即i+1=n；步骤5：如果i的值不大于11（i10），返回重新执行第3步和其后的步骤4和步骤5；否则，算法结束，sum的值即为所求。,1.认识算法什么是算法,【示例7-1】求1+2+3+10，即,设计算法就是掌握分析问题、解决问题的方法，就是锻炼分析、分解，最终归纳整理出算法的能力。,1.认识算法算法的基本特征及评价,有穷性确切性有0个或多个输入有1个或多个输出有效性,一个算法必须保证执行有限步之后结束,算法的每一步骤必须有确切的定义,描述运算对象的初始情况，所谓0个输入是指算法本身给出了初始条件。,算法特征,1.认识算法算法的基本特征及评价,算法评价,算法的正确性一个算法在计算机上运行所花费的时间在存储器上所占用的存储空间（主要考虑在算法运行过程中临时占用的存储空间的大小）算法的易读性,用自然语言描述算法用流程图描述算法用N-S图描述算法用伪代码表示算法用计算机语言表示算法,1.认识算法算法的描述工具,算法的描述方法,流程图是通过箭头相互连接的几何图形来表达的方法。,ANSI规定的一些常用流程图符号。,1.认识算法算法的描述工具,1.认识算法算法的描述工具,【示例7-1】求1+2+3+10，即,流程图,N-S图,不带有流程线，整个算法完全写在一个大的矩形框中。,1.认识算法算法的描述工具,【示例7-1】求1+2+3+10，即,伪代码,sum=0n=1forn=1to10dosum=sum+nprintsumend,#includeintmain()intsum=0,n=1;for(n=1;n=10;n+)sum=sum+n;printf(sum=%dn,sum);return0;,用C语言描述的算法,程序设计概述计算机语言高级语言程序的构成和执行,学习内容,2.程序设计基础,在计算机领域，程序是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合，是人们求解问题的逻辑思维活动的代码化描述。,2.程序设计基础程序设计概述,程序是程序设计的最终产物。计算机程序设计又称编程（Programming），是一门编写和设计计算机程序的科学和艺术。,计算机语言（ComputerLanguage）是指用于人与计算机之间通信的语言。计算机语言是人与计算机之间传递信息的媒介。人类使用计算机辅助进行一定的逻辑思维所用的思维工具就是计算机语言。,2.程序设计基础计算机语言,计算机语言的功能是人与计算机交换信息、计算机与计算机之间交换信息。,2.程序设计基础计算机语言,高级语言,机器语言,汇编语言,低级语言,计算机语言,面向问题的语言,面向过程的语言,面向对象的语言,C、Pascal、Fortran,VisualFoxPro,C+、Java,机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。机器语言的所有指令都是由0、1组成的二进制。,2.程序设计基础计算机语言,例如，计算A=15+10的机器语言程序如下：,1011000000001111把15放到累加器A中001011000000101010与累加器A的值相加，结果仍放入A中11110100结束，停机,格式,汇编语言用一些简洁的英文字母、符号串来替代一个特定的指令的二进制串，例如，用“ADD”代表加法，“MOV”代表数据传递等等。,2.程序设计基础计算机语言,例如，计算A=15+10的汇编程序如下：,MOVA,15把15放到累加器A中ADDA,1010与累加器A的值相加，结果仍放入A中HLT结束，停机,高级语言由贴近自然语言的“词”和“数学公式”组成。,例如，计算A=15+10的C语言程序如下：,#includeintmain()inta;a=15+10;printf(“%d”,a);return0;,2.程序设计基础计算机语言,#includeintmain()intadd(inta,intb);inta,b,sum;printf(Inputtwointegernumbers:n”);/*输出提示信息*/scanf(“%d,%d”,说明部分,【示例7-2】编写程序，计算两个整数的和。,intadd(intx,inty)intz;z=x+y;returnz;,2.程序设计基础高级语言程序的构成和执行,程序体,主函数,add函数,函数体,2.程序设计基础高级语言程序的构成和执行,C程序有函数构成，有且有一个主函数程序执行时总是从main()函数开始语句必须以“；”结束，书写格式自由“#”开头的为编译预处理命令利用/*/作为注释,C的程序结构,数据描述,常量：在程序中不能改变其值的量变量：其值在程序执行过程中是可以改变的量,程序处理的数据形式,2.程序设计基础高级语言程序的构成和执行,整型(如0,67,-2,123L,123u,022,0 x12)实型(如2.3,1.2e-5)字符型(如z,3,$,n)用开头的字符为转义字符,代表1个字符字符串(如UKM,1,5a),十进制小数,指数形式,无符号整型,长整型,八进制,十六进制,常量,2.程序设计基础高级语言程序的构成和执行,变量的声明,变量必须先声明，后使用,类型说明符变量名，变量名，;,变量,C语言规则,2.程序设计基础高级语言程序的构成和执行,机器语言,高级语言,2.程序设计基础高级语言程序的构成和执行,翻译方式有两种：编译和解释。编译是指事先编好的一个称为编译程序的机器语言程序，通过编译程序把高级语言书写的源程序整个地翻译成用机器语言表示的与之等价的目标程序。解释程序是在源程序进入计算机时，通过解释程序边扫描边解释，逐句输入，逐句翻译，计算机一句句执行，并不产生目标程序。,2.程序设计基础高级语言程序的构成和执行,2.程序设计基础高级语言程序的构成和执行,高级语言执行过程C语言程序,2.程序设计基础高级语言程序的构成和执行,结构化程序设计面向对象的程序设计,学习内容,3.程序设计方法,自顶向下逐步求精模块化限制使用goto语句,3.程序设计方法结构化程序设计,结构化程序设计方法的主要原则,顺序结构选择结构循环结构,基本结构,顺序结构,选择结构,循环结构,程序的三种主要结构,当型循环,直到型循环,3.程序设计方法结构化程序设计,顺序结构,3.程序设计方法结构化程序设计,利用海伦公式可以求得三角形面积为：其中，s=(a+b+c)/2，a、b、c是三条边长,【示例7-3】已知三角形的三条边长，计算三角形的面积。,选择结构,3.程序设计方法结构化程序设计,【示例7-4】输入三角形的三条边长，如果能构成三角形则计算三角形的面积，否则，输出“不能构成三角形”。,循环结构,3.程序设计方法结构化程序设计,【示例7-5】输入5组三角形的三条边长，对每组数据进行判断，如果能构成三角形则计算三角形的面积，否则，输出“不能构成三角形”。,对实际问题进行全局性的分析，确定解决问题的数学模型。确定程序的总体结构。将整个问题分解为若干个相对独立的子问题。确定每一个子问题的具体功能及其相互关系。对每一个子问题进行分析和细化，确定每一个子问题的解决方法。用计算机语言描述，并最终解决问题。,3.程序设计方法结构化程序设计,结构化程序设计方法步骤,3.程序设计方法面向对象的程序设计,对象是一个具有属性、能处理相应事件、具有特定方法程序、以数据为中心的统一体。类是一组具有相同特性的对象抽象。对象是对应类的实例。消息是对象之间进行通信的结构叫做消息。方法是对象的操作属性。,面向对象的基本概念,抽象性：抽取主题中与当前目标相关的细节，忽略与主题中与当前目标无关的那些细节。封装性：把数据和操作这些数据的代码封装在对象类里，对外界是完全不透明的，对象类完全拥有自己的属性。继承性：在已有类的基础上创建一个新类的定义技术。可以直接获得已有的性质和特征，而不必重复定义它们。多态性：相同的消息为不同的对象接收时可导致完全不同的行动，该现象称为多态性。,3.程序设计方法面向对象的程序设计,面向对象特性,排序常见算法查找基本算法,学习内容,4.典型算法及程序设计,4.典型算法及程序设计排序常见算法,所谓排序是把一系列无序的数据按照特定的顺序（如升序或降序）重新排列为有序序列的过程。,排序前,排序后,【示例7-6】利用选择排序算法，实现对n个数进行从小到大的排序。,【算法思想】扫描整个序列，从中选出最小的元素，将它与序列的第一个元素交换；然后再在余下的元素中找出最小数据的元素，与序列的第二个元素相互交换位置，然后对剩下的序列采用同样的方法，直到序列空为止。,4.典型算法及程序设计排序常见算法,【示例7-6】利用选择排序算法，实现对n个数进行从小到大的排序。,4.典型算法及程序设计排序常见算法,【举例说明】,【示例7-7】利用冒泡法排序算法，实现对n个数进行从小到大的排序。,【算法思想】在每一轮的排序过程中从第一个数开始，相邻两数依次比较，当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。这样，较小的数据就会逐个向前移动，好像气泡向上浮起一样。在扫描过程中，不断地将两相邻元素中的大者往后移动，最后将序列中的最大值换到了序列的最后。,4.典型算法及程序设计排序常见算法,4.典型算法及程序设计排序常见算法,【举例说明】,5个数经过5-1=4轮冒泡排序后，数据序列2，3，6，15，18为升序排列，排序结束,【示例7-8】输入一组数据，再输入需要查找的数x，如果找到，输出相应的位置，否则，输出NotFound。,【算法思想】将待查找的数依次顺序地与数列中的每一个数进行比较，如果相等，说明找到，宣布查找成功，算法结束；如果不相等，说明没有找到，此时应判断是否还有剩余的数据，如果还有剩余的数据则继续和剩余的数据比较，如果没有剩余的数据，则宣布查找失败，算法结束。,4.典型算法及程序设计查找基本算法,顺序查找,输入：298106查找：9输出：2,输入：298106查找：7输出：NotFound,【示例7-10】输入一组已排好序的数据，再输入需要查找的数x，使用折半查找法查找x，如果找到，输出相应的位置，否则，输出NotFound。,【算法思想】如果查找表中的数据元素按数值排序（假设递增有序），则在查找时不必逐个顺序比较，而采用跳跃的方式：首先与“中间位置”的元素