第讲程序设计基础.ppt

《第讲程序设计基础.ppt》由会员分享，可在线阅读，更多相关《第讲程序设计基础.ppt（32页珍藏版）》请在三一文库上搜索。

1、第九章 程序设计基础,计算机基础知识,1,9.1 算法与程序设计概述,2019/4/13,9.1.1 程序的概念 9.1.2 算法的概念及特征 1)算法的特征 2)算法的评价 9.1.3 算法的表示方法 1) 用自然语言表示 2) 用传统流程图表示 3) N-S流程图 4) 用伪代码表示 9.1.4 简单的程序设计实例 (下一讲),9.1 算法与程序设计,计算机基础知识,2,2019/4/13,1、程序 (先看生活中的程序) 现实生活中，程序的直观特征是按事先安排的步骤，一步步完成一系列动作，这种对活动过程的步骤描述就是一个“程序”。 在计算机领域，程序是指为让计算机完成特定的任务而设计的指令

2、序列。它是程序设计人员编写的、计算机能够理解并执行的一些命令的集合，是解决问题的具体步骤在计算机中的实现。,9.1.1 程序的概念,计算机基础知识,3,2019/4/13,计算机中的问题事例： 例1：求解一元二次方程 4.346 51.24X+8=0 例2：求解一元二次方程 a bXc=0 例3：设a0，b0，c0，若以正数a,b,c为三角的三条边，求三角形abc的面积？可利用海伦公式： 例4：求10以上200以下的整数中，能被3整除但不能被5整除的所有数据之和?,9.1.1 程序的概念,计算机基础知识,4,2019/4/13,计算机中的程序与日常生活中的程序的概念是类似的，只不过执行日常生活

3、程序的主体是人，而执行计算机程序的主体是计算机。计算机程序就是要由计算机进行解释和执行的程序。它表示的是计算机处理事务的时间顺序和处理问题的步骤。 程序只能由计算机可以解释和执行的基本操作组成，组成计算机程序的基本单位一般称为指令，因此简单的说，程序就是事先编制好的具有特定功能的指令序列。,9.1.1 程序的概念,计算机基础知识,5,2019/4/13,2、程序设计 既然程序是按一定次序编排的指令序列，那么编写指令序列的过程就是程序设计。用什么来编写指令序列？由于指令序列是给计算机执行的，因此这些指令应该是以计算机能够理解的语言表示的，这种语言就是程序设计语言。现在能够充当人和计算机之间的交流

4、工具的，就是计算机语言，包括各种命令语言和程序设计语言，主要是程序设计语言。,9.1.1 程序的概念,计算机基础知识,6,2019/4/13,*例1的 FoxPro 程序 A=4.346 B=-51.24 C=8 X1=(-B+SQRT(B*B-4*A*C)/(2*A) X2=(-B-SQRT(B*B-4*A*C)/(2*A) ? “X1=“,X1 ? “X2=“,X2,9.1.1 程序的概念,计算机基础知识,7,2019/4/13,*例2的 FoxPro 程序 INPUT “输入数据到A“ TO A INPUT “输入数据到B“ TO B INPUT “输入数据到C“ TO C IF B*B

5、-4*A*C=0 X1=(-B+SQRT(B*B-4*A*C)/(2*A) X2=(-B-SQRT(B*B-4*A*C)/(2*A) ? “X1=“,X1 ? “X2=“,X2 ELSE ? “无实数解!“ ENDIF,9.1.1 程序的概念,计算机基础知识,8,2019/4/13,*例3的 C语言程序 #include main() float a,b,c,p,area; scanf(“%f,%f,%f“, ,9.1.1 程序的概念,计算机基础知识,9,2019/4/13,*例4的 FoxPro程序 sum=0 n=10 do while nn/5 s=s+n endif stor n+1

6、to n enddo 5,10 say “10200内被3整除但不能被5整除的所有数据之和为:“ +str(s,5),9.1.1 程序的概念,计算机基础知识,10,2019/4/13,1、算法的概念 所谓算法是指解题方案的准确而完整的描述。算法是程序的灵魂，计算机程序设计的实质是算法的设计。自从计算机广泛用于解决现实问题以来，人们积累了大量的算法，这些算法是前人思想的结晶，也是新算法产生的基础。学习和研究这些算法，对解决实际问题，以及研究新的算法都是极为必要的。 每个算法实际上是按解题要求从所有的指令系统操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指

7、令序列。,9.1.2 算法的概念及特征,计算机基础知识,11,2019/4/13,一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作间的执行顺序称为算法的控制结构 2、算法的基本要素 一个算法通常由两种基本要素组成，一是对数据对象的运算和操作，二是算法的控制结构。 一个算法的运算操作或控制结构无论是简单还是复杂，一般必须满足以下五个重要特性： 有穷性、确定性、可行性、输入、输出,9.1.2 算法的概念及特征,计算机基础知识,12,2019/4/13,1）有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。 2

8、）确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。 3）可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。 4）输入 一个算法有零个或多个输入。 5）输出 一个算法有一个或多个有效信息的输出。,9.1.2 算法的概念及特征,计算机基础知识,13,2019/4/13,3、算法的评价（算法复杂度） 解决同一个问题的算法可以有多种，不同人员的设计不尽相同，其效率也存在差别，一个不好算法可能导致程序要运行几天、几个月甚至几年，一个好的算法可能只要几分种、几秒钟就可

9、以完成。 在设计算法时，应当遵循以下原则: 首先是保证算法的正确性 其次要具有良好的可读性 第三，算法应具有健壮性 第四，算法执行时间的高效性 第五，降低对存储空间的需求,9.1.2 算法的概念及特征,计算机基础知识,14,2019/4/13,一般而言，方法有优劣之分，算法的优劣可以有多种不同的评价标准。例如，可以从时间上来评价，也可以从空间上来评价，或者从其他的角度来评价。人们当然愿意选择较优的算法。因此，为了有效解题，不仅需要保证算法的正确性，还要考虑算法的质量，选择合适的算法。 从时间上来评价算法的优劣，即执行时间短的算法效率高,用算法的时间复杂度来度量。所谓算法的时间复杂度是指执行算法

10、所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。,9.1.2 算法的概念及特征,计算机基础知识,15,2019/4/13,例如，求1+2+100的结果，有人是先求1+2，再把和加上3，再加4，一直加到100；而高斯采取的办法是，先将这100个数分为若干个组：(100)、(1, 99)、(2, 98)、(49, 51)、(50)，前面50个组每个组的和都是100，因此结果为50*100+50。当然还有其他的方法。 从空间上来评价即为算法所需辅助空间越少越好,用算法的空间复杂度来度量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存

11、储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。,9.1.2 算法的概念及特征,计算机基础知识,16,2019/4/13,1) 用自然语言表示（教材中有例） 2) 用传统流程图表示 3) N-S流程图 4) 用伪代码表示 【例】求1+2+100的和，算法描述如下。 将1赋值给x。 将2赋值给y。 将x与y相加，结果存放在x中。 将y加1，结果存放在y中。 若y大于100，则输出结果x，算法结束，否则转步骤，算法继续执行。,9.1.3 算法的表示方法,计算机基础知识,17,2019/4/13,【例】求1+2+100的和，算法描述二： i1，sum0（

12、即将1赋值给i，0赋值给sum）。 sumsum + i（即将sum + i的结果保存到sum中）。 ii+1。 判断是否i100，如果是，转到步骤，否则，转到步骤。 输出sum的值，算法结束。,9.1.3 算法的表示方法,计算机基础知识,18,2019/4/13,2) 用传统流程图表示 传统流程图是用规定的一组图形符号、流程线和文字说明来表示各种操作的算法表示方法。,9.1.3 算法的表示方法,计算机基础知识,19,2019/4/13,2) 用传统流程图表示 在算法设计中常用到三种基本流程控制结构，即顺序、分支和循环结构。 顺序结构。每一个基本的处理单位顺序地被执行，,9.1.3 算法的表示

13、方法,计算机基础知识,20,2019/4/13, 分支结构。又称作选择结构，根据逻辑条件的成立与否，选择执行不同的处理，当逻辑条件成立时，执行处理A，否则执行处理B。,2) 用传统流程图表示 循环结构。当逻辑条件成立时，反复执行处理A，直到逻辑条件不成立时结束（左）。,9.1.3 算法的表示方法,计算机基础知识,21,2019/4/13,2) 用传统流程图表示 求1到100的 自然数的和 流程图,9.1.3 算法的表示方法,计算机基础知识,22,2019/4/13,4) 用伪代码表示 赋值 给一个变量赋值 变量名表达式 例 s12 xs*6.2+8 给多个变量赋相同的值 变量名，变量名，变量名

14、表达式 例 x,y,z3.5 s,tx+y,9.1.3 算法的表示方法,计算机基础知识,23,2019/4/13,4) 用伪代码表示 从键盘上输入数据到一个变量 input “数据类型” to 变量名 例 INPUT “姓名” TO XM INPUT “数值数据” TO S 输出一个或多个结果值 output “结果提示”, 表达式，表达式 例 OUTPUT “二次方程式的根为：”, X,Y output “1100的数据和S=：” ,s OUTPUT S,9.1.3 算法的表示方法,计算机基础知识,24,2019/4/13,4) 用伪代码表示 分支,9.1.3 算法的表示方法,计算机基础知识

15、,25,2019/4/13,单分支 if 语句组 endif,双分支 if 语句组A else 语句组B endif,4) 用伪代码表示 分支,9.1.3 算法的表示方法,计算机基础知识,26,2019/4/13,多分支（可省略） DO CASE CASE 语句组1 CASE 语句组2 CASE 语句组N OTHER 语句组N+1 ENDCASE,【注】逻辑运算符3个： NOT AND OR,4) 用伪代码表示 循环,9.1.3 算法的表示方法,计算机基础知识,27,2019/4/13, DO WHILE/ENDDO结构 (当条件为真时执行循环体) DO WHILE 循环体 ENDDO, FO

16、R/NEXT结构(不超越终值时执行循环体) FOR 循环控制变量=初值(表达式) TO 终值(表达式) STEP 步长值(表达式) 循环体 NEXT,综合举例： 【例1】求数列1,1,2,3,5,8,13,21前30项的数据和。 X，Y1 N，S2 DO WHILE N30 GX+Y XY YG SS+Y NN+1 ENDDO OUTPUT “数列1,1,2,3,5,8,13,21前30项的数据和S=”,S OUTPUT “数列当前项为”,N,9.1.3 算法的表示方法,计算机基础知识,28,2019/4/13,【例2】从键盘上任意输入十个非负数据，求平均值。 sum0 count1 do w

17、hile count10 input “输入数值数据”to x if not x0 sum sum+x countcount+1 endif enddo output “10个数据的平均值：”，sum/10,9.1.3 算法的表示方法,计算机基础知识,29,2019/4/13,【例3】求给定的十个数的平均值(教材例9.1) sum0 for count=1 to 10 step 1 input “输入数值数据”to x sumsum+x next output “10个数据的平均值：”，sum/10,9.1.3 算法的表示方法,计算机基础知识,30,2019/4/13,小 结,程序：程序是指为让计算机完成特定的任务而设计的指令序列。 程序设计：编写指令序列的过程就是程序设计 算法：算法是指解题方案的准确而完整的描述。算法是程序的灵魂，计算机程序设计的实质是算法的设计。 算法的表示方法 1) 用自然语言表示 2) 用传统流程图表示 3) N-S流程图 4) 用伪代码表示,计算机基础知识,31,2019/4/13,32,计算机基础知识,小 结,外部存储器、输入/输出设备,2019/4/13,