第一章 计算机程序设计与算法

北京理工大学计算机学院2020/1/281第一章计算机程序设计与算法李书涛[e-mail]北京理工大学计算机学院2020/1/282目录§1程序与程序设计§2程序设计算法§3计算机算法的表示§4用程序设计语言实现算法§5算法举例§6本章小结第一章计算机程序设计与算法北京理工大学计算机学院2020/1/283§1程序与程序设计§1程序与程序设计一、什么是程序程序是用计算机能够理解的语言描述的解决问题的方法和步骤。从编写程序的角度来看，程序是对所要解决问题的各个对象和处理规则的描述。其中：对象用数据结构表示；处理规则用算法设计描述。北京理工大学计算机学院2020/1/284什么是程序main(){说明语句数据结构语句执行语句算法设计}对所要解决问题的各个对象和处理规则的描述。程序＝数据结构＋算法北京理工大学计算机学院2020/1/285二、什么是程序设计其中:方法指程序设计的方法与风格。工具包含1.算法描述工具有：流程图、NS图、PDL（过程设计）语言等。2.程序设计语言。把需要解决的问题用计算机能完全理解的方式描述给计算机。程序设计＝数据结构＋算法＋方法＋工具北京理工大学计算机学院2020/1/286三、什么是数据结构数据的特性被抽象为数据类型和值。数据及其联系，即数据元素的组织形式又被抽象为数据结构。计算机的别名：数据处理机。数据元素：数据的最小单位。数据结构包括数据的逻辑结构与物理结构，它关系到软件与程序的复杂程度。北京理工大学计算机学院2020/1/287四、程序设计语言的分类1.科学计算语言：用于科学计算，基础是数学模型，过程描述的是数值计算，如FORTRAN语言；2.系统开发语言：用于编写编译程序、操作系统、数据库管理系统DBMS等，如C语言；3.实时处理语言：及时响应环境信息，可以根据外部信号对不同的程序段进行并发控制执行；如汇编语言；4.商用语言：主要用于商业处理、经济管理,基础为自然语言模型；如COBOL语言；5.人工智能描述语言：模拟人的思维推理过程，实现智能化控制等；6.模拟建模语言：用于模拟实现客观事物的发展与变化过程，以提前预测未来发展的结果；7.网络编程语言：在网络技术基础上进入深层次的应用研究与开发的语言,如Dephi适于网络化环境的编程，而JAVA是一种新型跨平台分布式程序设计语言，语义规范与C语言相同等等，不再列举。北京理工大学计算机学院2020/1/288五、程序设计过程1.程序实现过程程序设计是指我们使用一种计算机语言为实现解决实际问题的算法去设计编写计算机程序的过程。计算机语言是人与计算机进行交流的媒介，通过语言编写的程序，计算机就会准确地按程序步骤执行操作，计算机解决实际问题的一般过程如图1.1所示：北京理工大学计算机学院2020/1/289：包含以下几个步骤(1)分析问题：程序设计首先要进行对问题的分析，明白我们要作什么，确定要使用的数学模型。(2)确定算法：确定算法即确定解决问题时要执行的一系列步骤。(3)算法描述：算法描述就是使用计算机语言对算法予以描述。(4)确定程序设计语言：由于不同的计算机程序设计语言有不同的特点，根据实际情况与需要选定好程序设计语言后，就可以用该语言编程实现以算法。(5)调试和运行程序。2.程序设计的过程北京理工大学计算机学院2020/1/2810§2程序设计算法§2程序设计算法一、什么是算法一般而言，对解题过程准确而完整的描述称为解此问题的算法，因此不知道解题的算法也就不可能编写程序来解题。例如，要求一个圆的周长和面积就必须知道“周长＝2πR”及“面积＝πR2”两个公式，根据这两个公式就可以列出计算圆的周长和面积的算法。【例】算法：1)从键盘输入两个数N1和N22)计算两数之和S＝N1+N23)计算两数平均值V＝S/24)打印S和V它涉及4个操作，其控制方式是1)～4)顺序执行。北京理工大学计算机学院2020/1/2811如何交换两个数据的值？如何求两个数的最大公约数？如何求一个整数的阶乘？如何将十个数从大到小排序？如何表示算法？常用算法有：枚举法、迭代法、递推法、递归法、分治法二、算法举例北京理工大学计算机学院2020/1/2812§3计算机算法的表示§3计算机算法的表示算法的表示算法的表示通常有程序流程图、N-S图、PAD图等方式，但目前应用最广泛的是程序流程图和N-S图。下图表示程序流程图的基本符号，可用它来表示方程ax２+bx+c＝0程序流程图基本符号一、流程图人们普遍采用程序流程图是因为它简单、直观。把执行的流程表达得一清二楚，易于理解。然而，它也有不少缺陷，程序流程图中的箭头十分灵活，使用不当会影响到程序结构的清晰。X1=(-b+)/2aX2=(-b-)/2aS开始输入a,b,cS=b*b-4*a*cS=0y打印X1，X2打印“无实根解”n结束S方程ax２+bx+c＝0的求解算法开始s=0,a=0输入na=a+1s=s+aanYN输出s结束用规定的一系列图形、流程线和文字说明算法中的基本操作和控制流程。scanf(“%d”,&n);printf(“%d”,s);While(an)算法的表示--流程图例如计算:s=Σa;a=1~n北京理工大学计算机学院2020/1/2815二、N-S图N-S图的基本形式S1S2S3条件FTS1S3S2While条件SSUntil条件顺序分支循环1循环2N-S图图4N-S图输入系数a,b,cS=b*b-4*a*cS=0打印“无实根解”X1=(-b+)/2aX2=(-b–)/2a打印X1,X2SSFT方程ax２+bx+c＝0的求解三、PAD图PAD图的基本符号S1S2S3While条件SUntil条件S顺序分支循环S1S2条件TPAD图图0-3方程ax２+bx+c＝0的求解输入系数a,b,cS=b*b-4*a*cS=0打印X1,X2打印“无实根解”X2=(-b–)/2aSX1=(-b+)/2aS北京理工大学计算机学院2020/1/2819§4用程序设计语言实现算法§4用程序设计语言实现算法一.机器语言(Machinelanguage)例如，计算表达式m÷n-z的值，并把结果值存到10010000号内存单元。假设已知某计算机的取数操作码为1000，除法操作码为1010，减法操作码为1001，传送操作码为0100，另外也知m、n、z中的三个数已分别存放在11110110、10101101、01010110号内存单元。用机器语言可描述编写如下程序：100011110110取出m放在11110110内存单元的值101010101101除法操作放在10101101内存单元的值100101010110把结果值减去z放在10101101内存单元的值010010010000把最后结果值存到10010000号内存单元北京理工大学计算机学院2020/1/2820二.汇编语言(Assemblerlanguage)例如计算表达式m÷n-z值的程序可以写成：LDAM取出mDIVN除法操作SUBZ减法操作MOVY传送结果值使用这种语言计算机CPU不能直接识别，必须用事先存放在存储器中的“翻译程序”，把汇编语言翻译成机器语言,计算机指令系统才能识别和执行，这个翻译程序称为编译汇编程序,翻译成机器语言描述的程序叫目标程序。北京理工大学计算机学院2020/1/2821三.高级语言(High-levellanguage)不管使用机器语言还是使用汇编语言描述算法和编写程序，都没有摆脱计算机指令系统的束缚。到了1954年，出现了一种与具体计算机指令系统无关的语言，即高级语言。它与人们习惯使用的自然语言与数学语言非常接近，例如：y=2x2-x+1这样一个数学式子用高级语言来写，就写成y=2*x*x-x+1基本上是原样表达，这样描述程序算法显然就得心应手的多。北京理工大学计算机学院2020/1/2822高级语言特点∶面向过程。编程要解决两个问题∶做什么？怎样做？随着计算机的发展，急需要解决的是计算机硬件的高速度和程序编制的低效率之间的矛盾，在50年代末期出现了“高级程序设计语言”，它较为接近自然语言，具有易学易懂的特点。更重要的是，它是面向用户的语言，当学会了一种高级语言后，在各种类型的计算机上都能使用(但也略有差异)。用近似自然语言的语句编写程序高级语言自从高级语言问世以来，出现过上千种程序设计语言，通常可以分为通用型和专用型两大类。具体划分为：通用型语言：适合于数值计算的语言(例如ALGOL-60语言、FORTRAN语言)；结构化程序设计语言(例如Pascal语言、C语言)；适合商用和管理领域的语言(例如COBOL、FoxBASE、FOXPRO语言)，还有一些交互式的通用语言(例如BASIC语言)。专用型语言：种类多、功能各异。如适合数控机床工作的数控语言APL，适用于计算机辅助设计的AHPL和DDL语言，适合符号处理的LISP语言，适合于人工智能的LISP、PROLOG语言，适合于系统分析的PSL/PSA语言等。汇集性语言：它综合各类语言特点、功能强大，适用范围较广，如ADA和PL/I语言。用高级语言写的程序称为高级语言源程序目标程序源程序翻译高级语言机器语言高级语言常用的高级语言有：BASIC、FORTRAN（公式翻译）、ALGOL（算法语言）、COBOL、Pascal、C、PL/Ⅰ、LISP、PROLOG、Ada、APL等等。BASIC（初学者通用符号指令代码）面对这么多的高级语言，要全面掌握它是不可能的。事实上在实际计算机应用中常用的语言才十几种，初学者应以一种语言为模板，深入学习和应用，掌握该语言的基础、结构及编程等技术，这样才能为学习其他高级语言打下基础。北京理工大学计算机学院2020/1/2825四.第四代语言特点∶非过程化。编程只要解决一个问题∶做什么？常用的第四代语言有：DBMS（数据库管理系统）。如：FoxPro、Oracle、INFORMIX、SYBASE等等。五.第五代语言特点∶人工智能语言。可自动编写程序。例如：LIST正在研制发展中。面向问题的语言北京理工大学计算机学院2020/1/2826§5算法举例§5算法举例程序设计的关键是算法设计，有了算法，再用计算机语言去实现算法，就容易了。例1：计算1+2+3+…+100之和。算法步骤分析：S1:累加器变量sum赋初值0，即sum=0S2:计数器变量i赋初值1，即i=1S3:使累加器变量值sum加计数器变量值i,结果仍放在sum中,即sum=sum+i,此时sum值为sum=sum+i=0+1=1S4:使计数器变量i加1,结果仍放在i中,即i=i+1,此时i值为i=i+1=1+1=2依此类推……北京理工大学计算机学院2020/1/2827计算机组织结构运算器存储器控制器输出设备输入设备1.控制流2.数据流中央处理器(CPU)外部设备主机数据数据数据地址数据指令程序控制信息命令数据程序指令地址CentralProcessingUnit北京理工大学计算机学院2020/1/2828程序流程图和N-S图如下图所示图累加运算程序流程图开始sum=0i=0sum=sum+ii=i+1i=100打印NY图累加运算N-S图北京理工大学计算机学院2020/1/2829C语言程序算法如下main(){inti=1,sum=0;/*定义变量及其数据类型*/while(i=100)/*循环控制结构*/{sum+=i;i=i+1;}/*循环体结束*/printf(“sum=%d\n”,sum);/*输出累加结果*/}程序算法不是唯一的，这个问题还有其它的算法。北京理工大学计算机学院2020/1/2830以此类推可以很容易表示出其它问题的算法例2：计算下式之和的算法，当分母大于100时程序结束，输出计算结果。程序算法如下。北京理工大学计算机学院2020/1/2831例2算法的N-S图如下所示北京理工大学计算机学院2020/1/2832§6本章小结§6本章小结本章是计算机程序设计的基础，介绍了计算机程序设计语言的应用特点和发展演变，特别介绍了程序设计过程以及程序设