算法与计算机程序基础.ppt

第2章 算法与程序设计基础,大学计算机基础 I,2.1 程序设计概述,程序（program）是计算机可以执行的指令或语句序列。它是用计算机解决现实生活中的一个实际问题而编制的。设计、编制、调试程序的过程称为程序设计。编写程序所用的语言即为程序设计语言，它为程序设计提供了一定的语法和语义，所编写出的程序必须严格遵守它的语法规则，这样编写出来的程序才能被计算机所接受、运行，并产生预期的结果。,1. 机器语言,机器语言是早期的计算机语言，也是计算机唯一能够识别的计算机语言。机器语言是由“0”和“1”组成的二进制代码所表示的一组指令的集合。指令格式如下：,2.1.1 程序设计语言,从计算机问世至今的60多年中，程序设计语言与计算机共同诞生、共同发展，经历了从机器语言、汇编语言到高级语言的发展历程。,操作码指出应该进行什么样的操作，操作数指出参与操作数本身或它所在的地址。 例如：,此条指令的功能是：把15放入累加器A中。,由此可见，由于机器指令的功能很弱，而且记忆困难。因此用机器语言编写的程序十分繁琐，编程工作量大，可读性差，容易出错。而且通用性也很差。由于每台计算机的指令系统各不相同，在一台计算机上执行的程序，不能在另一台计算机上执行，必须另编程序，造成了重复工作。,2. 汇编语言 为了解决使用机器语言编写应用程序所带来的难以理解和记忆等一系列问题，人们首先想到了使用易于理解和记忆的名称和符号来表示机器指令，从而形成了汇编语言。例如：,ADD a， b 此条语句的功能是：将a中的内容加上b中的内容。,汇编语言和机器语言都属于低级语言，其特点是与特定的机器有关，工作效率高，但与人们思考问题和描述问题的方法相距甚远，使用繁琐、费时，易出差错。,高级语言是为克服低级语言的缺点和不足而设计的计算机语言，其优点是接近于人类熟悉的自然语言和数学语言，更接近于要解决的问题的表示方法，而且用高级语言编写的程序具有易懂、易用、易维护、通用性好的特点。 高级语言是目前非常普及的计算机语言，目前较为流行的高级语言有C语言、C+语言、Visual C (简称VC) 、Visual Basic（简称VB）和Java语言等。,3. 高级语言,程序设计即编程，是让计算机为解题而执行某一种程序设计语言编写的程序代码的过程。 为了使计算机能够理解人的意图，人类就必须为计算机设计出计算机能够识别的解决某一问题的具体步骤，送入计算机，命令计算机按照我们编写的解题步骤一步一步去执行，为我们去解题。这种人和计算机之间交流的过程就是程序设计，即编程，而所谓的程序代码就是让计算机为我们解题而执行的操作步骤，即计算机程序。,2.1.2 程序设计的基本步骤,程序设计的四个基本步骤,（1）分析问题 首先根据问题的具体要求进行需求分析、对现有的信息加以整理，然后在分析的基础上，将实际问题抽象化，建立相应的数学模型并确定解决方案。 （2）设计算法 算法是研究如何写出符合计算机特点、能让计算机执行并能为我们产生正确计算结果的解题步骤。每一个计算机程序都是由相应的算法转化过来的。 根据建立数学模型和确定的方案，详细规划解决问题的步骤。若是简单问题，绘制流程图既可，如是比较复杂的问题则采用伪代码或其他算法描述。(见2.2.2 算法的表示 ),例2.1,（3）编写程序 根据确定的算法，选用合适的程序设计语言，将算法按所选语言的规则描述出来，即形成源程序。 （4）调试运行与维护程序 对编写好的程序需进行验证、测试、调试与维护。若发现问题即对程序进行修改，然后再运行和检验，直到得出正确结果。,下面通过一个例子来说明程序设计的四个基本步骤,例2.1,【例2.1】编写一个程序，任意输入一个圆半径，求出相应的圆面积。,用自然语言写出的求圆面积的算法： 第一步：从键盘输入圆面积R； 第二步：计算圆面积，算式为 3.14159 R2 第三步：输出圆面积计算结果。,一、首先分析问题确定解题方法与相应的公式 二、 确定算法,四步骤,#include void main() int R; /*整变量定义*/ float S; /*整变量定义*/ scanf(“%d”, /*在屏幕上输出圆面积值*/ ,【例2.1】算法的 c语言表示。,注：变量是程序中数据存放场所，对应着一个内存单元。在程序中的变量都要被赋予一个值，这个值是变化的。,三、编写程序,四、运行程序 先从键盘输入一个圆半经并赋予变量R，再计算圆面积的值并赋予变量S，最后在屏幕上显示圆面积的计算结果。,2.2 算法基础,计算机解决一个实际问题而采取的方法和步骤，称之为“算法”。对于同一个问题，可能有不同的方法和步骤，即有不同的算法。,2.2.1 算法的表示,算法的表示方法很多，常见的有自然语言、传统流程图、N-S图，伪代码等。 1用自然语言表示算法 自然语言就是人们日常使用的语言。自然语言表示的算法通俗易懂，但篇幅较长。所以除了很简单的问题，一般不用自然语言表示算法，而使用流程图表示算法。,流程图基本形状图,2用流程图表示算法,3用N-S流程图表示算法（一般了解） 针对传统流程图存在的问题，1973年美国学者提出了一种新型流程图：N-S流程图。其主要特点是完全取消了流程线，不允许随意出现控制流，全部算法写作矩形框内，该矩形框以3种基本结构（顺序、选择、循环）描述符号为基础复合而成。,顺序结构 选择结构 循环机构,4伪代码描述算法（一般了解） 伪代码是一种介于自然语言和程序设计语言之间的文字和符号，用来描述算法。伪代码的表现形式比较灵活，没有严格的语法格式。,【例2.2】计算x和y两个整数的平均值。用自然语言表示法写出此例的算法。,2.2.2 算法设计初步,写算法的目的是为了最终形成正确的计算机程序。按照算法的步骤写出相应的计算机程序,对于初学程序设计者是一个必要的过渡过程。,简单算法设计 下面通过一个例子进一步介绍算法设计的方法,以下是针对【例2.2】的算法（计算机解题的步骤）： 第一步：从键盘输入一个整数给x； 从键盘输入一个整数给y； 第二步：将x和y两个数相加再除以2，即(x+y)/2； 第三步：打印输出计算结果，即算式(x+y)/2的计算值。,说明：“/”为除法运算符，x和y是变量名，变量代表计算机的一个内存单元，从键盘输入的数据和运算的结果都是临时保存在内存中单元中。,#include void main() int x,y; /*变量定义*/ float ave； scanf(“%d”, /*在屏幕上输出平均值*/ ,【例2.2】算法的 c语言表示。,【例2.2】运行结果,在C语言开发环境中进行编程、调试和运行，显示运行结果,通过【例2.1】 和【例2.2】两个简单的解题算法，可以从中对计算机程序得出几点认识： （1） 每个程序实际上是按解题要求从其开发环境（如C语言开发环境）下所能进行的所有操作中选择合适的操作，然后再组成相应的被称作指令的命令序列。 通常，计算机可以执行的基本操作是以指令的形式描述的，对C语言等高级语言来说就是以语句的形式描述的。一个用高级语言编写的计算机程序就是按解题算法从所采用的高级语言（ 如C语言）的语句集合中选择适合的语句所组成的命令序列。,2. 对计算机程序得出几点认识,（2）程序的控制结构 一个要求计算机执行的程序的功能不仅取决于所选的操作，而且与各操作之间的执行的先后顺序有关。程序中各操作之间的顺序称为程序的控制结构。 程序的控制结构给出了程序的基本框架，它不仅决定了程序中各操作的执行顺序，而且也直接反映了程序的设计是否符合结构化原则。一个程序一般都可以用顺序、选择（分支）和循环三种基本控制结构组合而成。,结构化程序设计中，程序有三种基本控制结构，即顺序结构、选择结构和循环结构，其中顺序结构是最基本的结构。C语言中也相应的三种基本控制结构。 顺序结构 所谓顺序结构指的是按照程序中语句出现的先后次序依次执行各条语语句，其流程图见图4-1，“语句1”执行后才执行“语句2”,最后再执行“语句n”。 例如【例2.1】【例2.2 】,以下是针对【例2.2】的算法（计算机解题的步骤）： 第一步：从键盘输入一个整数给x； 从键盘输入一个整数给y； 第二步：将x和y两个数相加再除以2，即(x+y)/2； 第三步：打印输出计算结果，即算式(x+y)/2的计算值。, 选择结构(分支结构) 在下图分支结构中，根据条件P是否成立，来选择执行A或B，条件P常由逻辑表达式或关系表达式、条件表达式等构成。, 循环结构 循环结构是结构化程序设计的3种基本结构之一，在循环结构中，程序的运行将根据条件表达式是否成立(为真或非零)来决定是否重复执行某一语句或多条语句构成的复合语句（这些语句又被称为循环体）。,条件表达式,这也是一个数值计算的问题。用自然语言表示算法是： 第一步：从键盘依次输入三个整数赋给三个变量a,b,x； 第二步：判断x是否大于a,如果条件成立就执行第三步，否则执 行第四步; 第三步：计算算式ax+b的值,赋给变量f,即f= ax+b, 转到第五步； 第四步：计算算式bx+a的值,赋给变量f,即f= ax+b, 转到第五步； 第五步：输出（显示）计算结果，即变量f的值。,在例【例2.3】中算法描述的程序除了顺序结构还有选择结构。,用传统流程图表示,main() int a,b,y,f; /*变量定义*/ scanf(“%d”, /*输出（显示）函数f(x)的值*/ ,【例2.3】算法的 c语言表示,设t代表各项的累计；i代表单项。 用流程图表示计算各项累计的算法为：,在【例2.4】中算法描述的程序包括了顺序结构和循环结构。,循环结构,判断框,思考： 如果将算式增加到50项即加到1/50,应该怎样修改此算法,累加,计数,赋初值,第一步： 将0赋给变量t, 将1赋给变量i,即 t=0 ,i=1 第二步：将t与1/i相加后再重新赋给t，即t=t+1/i 第三步：将i的值加1后再重新赋给i，即i=i+1 第四步：如果i5，返回第二步重新执行。否则终止退出循环 ，执行第五步，此时t中的值就是所求的值。 第五步：打印输出变量t的值。,设t代表各项的累计；i代表单项 用自然语言表示计算各项累计的算法为：,累加算法,计数算法,#include main() int i; float t; t=0; for(i=1;i=5;i+) t=t+1.0/i; /* 采用计数型循环结构来实现 */ printf(“The t is %fn”,t); /*输出各项之和计算结果*/ ,第一步： 将0赋给变量t,将-1赋给变量sign,将1赋给变量i,即 t=0, sign=-1 ,i=1 第二步：将(-1)sign后再赋给变量sign，即sign=(