1、第九章第九章 程序设计基础程序设计基础计算机基础知识19.1 9.1 算法与程序设计概述算法与程序设计概述 2022-11-149.1.1 9.1.1 程序的概念程序的概念 9.1.2 9.1.2 算法的概念及特征算法的概念及特征 1)1)算法的特征算法的特征 2)2)算法的评价算法的评价 9.1.3 9.1.3 算法的表示方法算法的表示方法1)1)用自然语言表示用自然语言表示2)2)用传统流程图表示用传统流程图表示3)N-S3)N-S流程图流程图4)4)用伪代码表示用伪代码表示9.1.4 9.1.4 简单的程序设计实例简单的程序设计实例 (下一讲下一讲)9.1 算法与程序设计算法与程序设计计
2、算机基础知识22022-11-141 1、程序、程序 (先看生活中的程序先看生活中的程序)现实生活中，程序的现实生活中，程序的直观特征是按事先安排的步直观特征是按事先安排的步骤，一步步完成一系列动作骤，一步步完成一系列动作，这种对活动过程的步，这种对活动过程的步骤描述就是一个骤描述就是一个“程序程序”。在计算机领域，在计算机领域，程序是指为让计算机完成特定的程序是指为让计算机完成特定的任务而设计的指令序列任务而设计的指令序列。它是程序设计人员编写的、。它是程序设计人员编写的、计算机能够理解并执行的一些命令的集合，是解决计算机能够理解并执行的一些命令的集合，是解决问题的具体步骤在计算机中的实现。
3、问题的具体步骤在计算机中的实现。9.1.1 程序的概念程序的概念计算机基础知识32022-11-14计算机中的问题事例：计算机中的问题事例：例例1 1：求解一元二次方程求解一元二次方程4.3464.34651.24X+8=051.24X+8=0例例2 2：求解一元二次方程求解一元二次方程 a a bXbXc=0c=0例例3 3：设设a0a0，b0b0，c0c0，若以正数，若以正数a,b,ca,b,c为三角的为三角的三条边，求三角形三条边，求三角形abcabc的面积？可的面积？可利用海伦公式利用海伦公式：例例4 4：求求1010以上以上200200以下的整数中，能被以下的整数中，能被3 3整除但
4、不整除但不能被能被5 5整除的所有数据之和整除的所有数据之和?9.1.1 程序的概念程序的概念计算机基础知识42022-11-142x2x2)()()(cbalclblallarea其中计算机中的程序与日常生活中的程序的概念是类计算机中的程序与日常生活中的程序的概念是类似的，只不过似的，只不过执行日常生活程序的主体是人执行日常生活程序的主体是人，而，而执执行计算机程序的主体是计算机行计算机程序的主体是计算机。计算机程序就是要。计算机程序就是要由计算机进行解释和执行的程序。它表示的是计算由计算机进行解释和执行的程序。它表示的是计算机处理事务的时间顺序和处理问题的步骤。机处理事务的时间顺序和处理问
5、题的步骤。程序程序只能只能由由计算机可以解释和执行的计算机可以解释和执行的基本操作组基本操作组成成，组成计算机程序的基本单位一般称为，组成计算机程序的基本单位一般称为指令指令，因，因此简单的说，程序就是事先编制好的具有特定功能此简单的说，程序就是事先编制好的具有特定功能的指令序列。的指令序列。9.1.1 程序的概念程序的概念计算机基础知识52022-11-142 2、程序设计程序设计既然既然程序是程序是按一定次序编排的按一定次序编排的指令序列指令序列，那么编，那么编写指令序列的过程就是程序设计。写指令序列的过程就是程序设计。用什么来编写指用什么来编写指令序列？令序列？由于指令序列是给计算机执行
6、的，因此由于指令序列是给计算机执行的，因此这这些指令应该是以计算机能够理解的语言表示些指令应该是以计算机能够理解的语言表示的，这的，这种语言就是程序设计语言。现在能够充当人和计算种语言就是程序设计语言。现在能够充当人和计算机之间的交流工具的，就是计算机语言，包括各种机之间的交流工具的，就是计算机语言，包括各种命令语言和程序设计语言，主要是程序设计语言。命令语言和程序设计语言，主要是程序设计语言。9.1.1 程序的概念程序的概念计算机基础知识62022-11-14*例例1 1的的 FoxPro FoxPro 程序程序A=4.346A=4.346B=-51.24B=-51.24C=8C=8X1=(
7、-B+SQRT(BX1=(-B+SQRT(B*B-4B-4*A A*C)/(2C)/(2*A)A)X2=(-B-SQRT(BX2=(-B-SQRT(B*B-4B-4*A A*C)/(2C)/(2*A)A)?X1=,X1?X1=,X1?X2=,X2?X2=,X29.1.1 程序的概念程序的概念计算机基础知识72022-11-14*例例2 2的的 FoxPro FoxPro 程序程序INPUT INPUT 输入数据到输入数据到A TO AA TO AINPUT INPUT 输入数据到输入数据到B TO BB TO BINPUT INPUT 输入数据到输入数据到C TO CC TO CIF BIF
8、B*B-4B-4*A A*C=0C=0 X1=(-B+SQRT(B X1=(-B+SQRT(B*B-4B-4*A A*C)/(2C)/(2*A)A)X2=(-B-SQRT(B X2=(-B-SQRT(B*B-4B-4*A A*C)/(2C)/(2*A)A)?X1=,X1?X1=,X1?X2=,X2?X2=,X2ELSEELSE?无实数解无实数解!ENDIFENDIF9.1.1 程序的概念程序的概念计算机基础知识82022-11-14*例例3 3的的 C C语言程序语言程序#include#includemain()main()float a,b,c,p,area;float a,b,c,p,a
9、rea;scanf(%f,%f,%f,&a,&b,&c);scanf(%f,%f,%f,&a,&b,&c);if(a+bc)&(a+cb)&(b+ca)if(a+bc)&(a+cb)&(b+ca)p=(a+b+c)/2.0;p=(a+b+c)/2.0;area=sqrt(p area=sqrt(p*(p-a)(p-a)*(p-b)(p-c);(p-b)(p-c);printf(a=%7.2f,b=%7.2f,c=%7.2f,p=%7.2fn,a,b,c,p);printf(a=%7.2f,b=%7.2f,c=%7.2f,p=%7.2fn,a,b,c,p);printf(area=%7.2fn,
10、area);printf(area=%7.2fn,area);else else printf(abc printf(abc不能构成三角形不能构成三角形!);!);9.1.1 程序的概念程序的概念计算机基础知识92022-11-14*例例4 4的的 FoxProFoxPro程序程序sum=0sum=0n=10n=10do while n200do while n200 if mod(n,3)=0 and int(n/5)n/5 if mod(n,3)=0 and int(n/5)n/5 s=s+n s=s+n endif endif stor n+1 to n stor n+1 to nend
11、doenddo 5,10 say 10200 5,10 say 10200内被内被3 3整除但不能被整除但不能被5 5整除的所有数整除的所有数据之和为据之和为:+str(s,5):+str(s,5)9.1.1 程序的概念程序的概念计算机基础知识102022-11-141 1、算法的概念算法的概念所谓所谓算法是指解题方案的准确而完整的描述算法是指解题方案的准确而完整的描述。算算法是程序的灵魂，计算机程序设计的实质是算法的法是程序的灵魂，计算机程序设计的实质是算法的设计。设计。自从计算机广泛用于解决现实问题以来，人自从计算机广泛用于解决现实问题以来，人们积累了大量的算法，这些算法是前人思想的结晶，
12、们积累了大量的算法，这些算法是前人思想的结晶，也是新算法产生的基础。学习和研究这些算法，对也是新算法产生的基础。学习和研究这些算法，对解决实际问题，以及研究新的算法都是极为必要的。解决实际问题，以及研究新的算法都是极为必要的。每个算法实际上是按解题要求从所有的指令系统每个算法实际上是按解题要求从所有的指令系统操作中选择合适的操作所组成的一组指令序列。因操作中选择合适的操作所组成的一组指令序列。因此，此，计算机算法就是计算机能处理的操作所组成的计算机算法就是计算机能处理的操作所组成的指令序列。指令序列。9.1.2 算法的概念及特征算法的概念及特征计算机基础知识112022-11-14一个算法的功
13、能不仅取决于所选用的操作，而且一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作间还与各操作之间的执行顺序有关。算法中各操作间的执行顺序称为的执行顺序称为算法的控制结构算法的控制结构2 2、算法的基本要素、算法的基本要素一个算法通常由两种一个算法通常由两种基本要素基本要素组成，组成，一是一是对数据对数据对象的对象的运算和操作运算和操作，二是二是算法的算法的控制结构控制结构。一个算法的运算操作或控制结构无论是简单还是一个算法的运算操作或控制结构无论是简单还是复杂，一般必须满足以下复杂，一般必须满足以下五个重要特性五个重要特性：有穷性、确定性、可行性、输入、输出有
14、穷性、确定性、可行性、输入、输出9.1.2 算法的概念及特征算法的概念及特征计算机基础知识122022-11-141 1）有穷性）有穷性对于任意一组合法输入值，在执行对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。都能在有限时间内完成。2 2）确定性）确定性对于每种情况下所应执行的操作，对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，者都能明确其含义及如何执行。并且在任何条件下，算法都只有
15、一条执行路径。算法都只有一条执行路径。3 3）可行性）可行性算法中的所有操作都必须足够基本，算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。都可以通过已经实现的基本操作运算有限次实现之。4 4）输入）输入一个算法有零个或多个输入。一个算法有零个或多个输入。5 5）输出）输出一个算法有一个或多个有效信息的输一个算法有一个或多个有效信息的输出。出。9.1.2 算法的概念及特征算法的概念及特征计算机基础知识132022-11-143 3、算法的评价（算法复杂度）算法的评价（算法复杂度）解决同一个问题的算法可以有多种，不同人员的解决同一个问题的算法可以有多种，不同人员的设
16、计不尽相同，其效率也存在差别，一个不好算法设计不尽相同，其效率也存在差别，一个不好算法可能导致程序要运行几天、几个月甚至几年，一个可能导致程序要运行几天、几个月甚至几年，一个好的算法可能只要几分种、几秒钟就可以完成。好的算法可能只要几分种、几秒钟就可以完成。在在设计算法设计算法时，应当时，应当遵循遵循以下以下原则原则:首先首先是保证算法的是保证算法的正确性正确性其次其次要具有良好的要具有良好的可读性可读性第三第三，算法应具有，算法应具有健壮性健壮性第四，算法执行时间的高效性第四，算法执行时间的高效性第五，降低第五，降低对对存储空间的需求存储空间的需求9.1.2 算法的概念及特征算法的概念及特征
17、计算机基础知识142022-11-14一般而言，方法有优劣之分，算法的优劣可以有一般而言，方法有优劣之分，算法的优劣可以有多种不同的评价标准。例如，可以多种不同的评价标准。例如，可以从时间上来评价从时间上来评价，也可以从空间上来评价也可以从空间上来评价，或者从其他的角度来评价。，或者从其他的角度来评价。人们当然愿意选择较优的算法。因此，为了有效解人们当然愿意选择较优的算法。因此，为了有效解题，不仅需要保证算法的正确性，还要考虑算法的题，不仅需要保证算法的正确性，还要考虑算法的质量，选择合适的算法。质量，选择合适的算法。从时间上来评价算法的优劣从时间上来评价算法的优劣，即执行时间短的算，即执行时
18、间短的算法效率高法效率高,用算法的时间复杂度来度量。所谓算法用算法的时间复杂度来度量。所谓算法的时间复杂度是指执行算法所需要的计算工作量。的时间复杂度是指执行算法所需要的计算工作量。可以用算法在执行过程中所需基本运算的执行次数可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。来度量算法的工作量。9.1.2 算法的概念及特征算法的概念及特征计算机基础知识152022-11-14例如例如，求，求1+2+1001+2+100的结果，有人是先求的结果，有人是先求1+21+2，再把和加上再把和加上3 3，再加，再加4 4，一直加到，一直加到100100；而高；而高斯采取的办法是，先将这斯采
19、取的办法是，先将这100100个数分为若干个组：个数分为若干个组：(100)(100)、(1,99)(1,99)、(2,98)(2,98)、(49,51)(49,51)、(50)(50)，前面，前面5050个组每个组的和都是个组每个组的和都是100100，因此结果，因此结果为为5050*100+50100+50。当然还有其他的方法。当然还有其他的方法。从空间上来评价从空间上来评价即为算法所需辅助空间越少越好即为算法所需辅助空间越少越好,用算法的空间复杂度来度量。一个算法的空间复杂用算法的空间复杂度来度量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一度，一般是指执行这个算法所需
20、要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。中所需要的额外空间。9.1.2 算法的概念及特征算法的概念及特征计算机基础知识162022-11-141)1)用自然语言表示用自然语言表示（教材中有例）（教材中有例）2)2)用传统流程图表示用传统流程图表示3)N-S3)N-S流程图流程图4)4)用伪代码表示用伪代码表示【例例】求求1+2+1001+2+100的和的和，算法描述如下。，算法描述如下。将将1 1赋值给赋值给x x。将将
21、2 2赋值给赋值给y y。将将x x与与y y相加，结果存放在相加，结果存放在x x中。中。将将y y加加1 1，结果存放在，结果存放在y y中。中。若若y y大于大于100100，则输出结果，则输出结果x x，算法结束，否则转步骤，算法结束，否则转步骤，算法继续执行。算法继续执行。9.1.3 算法的表示方法算法的表示方法计算机基础知识172022-11-14【例例】求求1+2+1001+2+100的和，的和，算法描述二：算法描述二：i1i1，sum0sum0（即将（即将1 1赋值给赋值给i i，0 0赋值给赋值给sumsum）。）。sumsum+isumsum+i（即将（即将sum+isum
22、+i的结果保存到的结果保存到sumsum中）。中）。ii+1ii+1。判断是否判断是否i100i100，如果是，转到步骤，否，如果是，转到步骤，否则，转到步骤。则，转到步骤。输出输出sumsum的值，算法结束。的值，算法结束。9.1.3 算法的表示方法算法的表示方法计算机基础知识182022-11-142)2)用传统流程图表示用传统流程图表示传统流程图是用规定的一组传统流程图是用规定的一组图形符号图形符号、流程线流程线和和文字说明来表示各种操作的算法表示方法。文字说明来表示各种操作的算法表示方法。9.1.3 算法的表示方法算法的表示方法计算机基础知识192022-11-14处理框处理框判断框判
23、断框输入输出框输入输出框连接点连接点流程线流程线起止框起止框2)2)用传统流程图表示用传统流程图表示在算法设计中常用到三种基本流程控制结构，即在算法设计中常用到三种基本流程控制结构，即顺序、分支和循环结构。顺序、分支和循环结构。顺序结构。每一个基本的处理单位顺序地被执顺序结构。每一个基本的处理单位顺序地被执行，行，9.1.3 算法的表示方法算法的表示方法计算机基础知识202022-11-14FT条件条件AB 分支结构。又称作分支结构。又称作选择结构，根据逻辑条选择结构，根据逻辑条件的成立与否，选择执件的成立与否，选择执行不同的处理，当逻辑行不同的处理，当逻辑条件成立时，执行处理条件成立时，执行
24、处理A A，否则执行处理，否则执行处理B B。2)2)用传统流程图表示用传统流程图表示 循环结构。当逻辑条件成立时，反复执行处循环结构。当逻辑条件成立时，反复执行处理理A A，直到逻辑条件不成立时结束（左）。，直到逻辑条件不成立时结束（左）。9.1.3 算法的表示方法算法的表示方法计算机基础知识212022-11-14FTA条件条件TFTA条件条件2)2)用传统流程图表示用传统流程图表示求求1 1到到100100的的自然数的和自然数的和流程图流程图9.1.3 算法的表示方法算法的表示方法计算机基础知识222022-11-14F FT T开始开始sum0sum0，i1i1sumsum+isums
25、um+ii100?i100?输出输出sumsum结束结束4)4)用伪代码表示用伪代码表示 赋值赋值给一个变量赋值给一个变量赋值 变量名变量名表达式表达式 例例 s12 s12 xs xs*6.2+86.2+8给多个变量赋相同的值给多个变量赋相同的值 变量名，变量名，变量名变量名，变量名，变量名表达式表达式例例 x,y,z3.5 x,y,z3.5 s,tx+y s,tx+y9.1.3 算法的表示方法算法的表示方法计算机基础知识232022-11-144)4)用伪代码表示用伪代码表示从键盘上输入数据到一个变量从键盘上输入数据到一个变量input“input“数据类型数据类型”to to 变量名变量
26、名例例 INPUT“INPUT“姓名姓名”TO XMTO XM INPUT“INPUT“数值数据数值数据”TO STO S输出一个或多个结果值输出一个或多个结果值output“output“结果提示结果提示”,表达式表达式，表达式，表达式例例 OUTPUT“OUTPUT“二次方程式的根为：二次方程式的根为：”,X,Y,X,Y output“1100 output“1100的数据和的数据和S=S=：”,s,s OUTPUT S OUTPUT S9.1.3 算法的表示方法算法的表示方法计算机基础知识242022-11-144)4)用伪代码表示用伪代码表示分支分支9.1.3 算法的表示方法算法的表示
27、方法计算机基础知识252022-11-14单分支单分支if if 语句组语句组endifendif双分支双分支if if 语句组语句组A Aelseelse 语句组语句组B Bendifendif4)4)用伪代码表示用伪代码表示分支分支9.1.3 算法的表示方法算法的表示方法计算机基础知识262022-11-14多分支（可省略）多分支（可省略）DO CASEDO CASE CASE CASE 1 语句组语句组1 1 CASE CASE 2 语句组语句组2 2 CASE CASE N 语句组语句组N N OTHER OTHER 语句组语句组N+1N+1 ENDCASE ENDCASE【注注】逻辑
28、运逻辑运算符算符3 3个：个：NOT NOT AND AND OROR4)4)用伪代码表示用伪代码表示循环循环9.1.3 算法的表示方法算法的表示方法计算机基础知识272022-11-14 DO WHILE/ENDDO DO WHILE/ENDDO结构结构(当条件为真时执行循环体当条件为真时执行循环体)DO WHILE DO WHILE 循环体循环体ENDDOENDDO FOR/NEXTFOR/NEXT结构结构(不超越终值时执行循环体不超越终值时执行循环体)FOR FOR 循环控制变量循环控制变量=初值初值(表达式表达式)TO)TO 终值终值(表达式表达式)STEP)STEP 步长值步长值(表
29、达式表达式)循环体循环体NEXTNEXT综合举例：综合举例：【例例1 1】求数列求数列1,1,2,3,5,8,13,211,1,2,3,5,8,13,21前前3030项的数据和。项的数据和。X X，Y1Y1N N，S2S2DO WHILE NDO WHILE N3030 GX+Y GX+Y XY XY YG YG SS+Y SS+Y NN+1 NN+1ENDDOENDDOOUTPUT“OUTPUT“数列数列1,1,2,3,5,8,13,211,1,2,3,5,8,13,21前前3030项的数据和项的数据和S=”,S S=”,S OUTPUT“OUTPUT“数列当前项为数列当前项为”,N,N9.
30、1.3 算法的表示方法算法的表示方法计算机基础知识282022-11-14【例例2 2】从键盘上任意输入十个非负数据，求平均值。从键盘上任意输入十个非负数据，求平均值。sum0sum0count1count1do while count10do while count10 input“input“输入数值数据输入数值数据”to xto x if not x0 if not x0 sum sum+x sum sum+x countcount+1 countcount+1 endif endifenddoenddooutput“10output“10个数据的平均值：个数据的平均值：”，sum/10
31、sum/109.1.3 算法的表示方法算法的表示方法计算机基础知识292022-11-14【例例3 3】求给定的十个数的平均值求给定的十个数的平均值(教材例教材例9.1)9.1)sum0sum0for count=1 to 10 step 1for count=1 to 10 step 1 input“input“输入数值数据输入数值数据”to xto xsumsum+xsumsum+xnextnextoutput“10output“10个数据的平均值：个数据的平均值：”，sum/10sum/109.1.3 算法的表示方法算法的表示方法计算机基础知识302022-11-14小小 结结程序：程序
32、：程序是指为让计算机完成特定的任务而设程序是指为让计算机完成特定的任务而设计的指令序列。计的指令序列。程序设计：程序设计：编写指令序列的过程就是程序设计编写指令序列的过程就是程序设计算法：算法：算法是指解题方案的准确而完整的描述。算法是指解题方案的准确而完整的描述。算法是程序的灵魂，计算机程序设计的实质是算法算法是程序的灵魂，计算机程序设计的实质是算法的设计。的设计。算法的表示方法算法的表示方法1)1)用自然语言表示用自然语言表示2)2)用传统流程图表示用传统流程图表示3)N-S3)N-S流程图流程图4)4)用伪代码表示用伪代码表示计算机基础知识312022-11-1432计算机基础知识小小 结结外部存储器、输入外部存储器、输入/输出设备输出设备2022-11-14
