1、第二章程序的灵魂-算法教材第2章一个程序包括对数据的描述和对数据处理的描述。一个程序包括对数据的描述和对数据处理的描述。1对数据的描述，即数据结构。对数据的描述，即数据结构。在在C语言中，系统提供的数据结构，是以数据类型的形式语言中，系统提供的数据结构，是以数据类型的形式出现的。出现的。2对数据处理的描述，即计算机算法。算法是为解决一个对数据处理的描述，即计算机算法。算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。为此，著名计算问题而采取的方法和步骤，是程序的灵魂。为此，著名计算机科学家沃思（机科学家沃思（Nikiklaus Wirth）提出一个公式：）提出一个公式：数据结构数据结构+算
2、法算法+文档文档=程序程序 实际上，一个程序除了数据结构和算法外，还必须使用一实际上，一个程序除了数据结构和算法外，还必须使用一种计算机语言，并采用结构化方法来表示。种计算机语言，并采用结构化方法来表示。程序设计概述程序设计概述 算法算法:解决一个具体问题的意义明确的步骤的集合。解决一个具体问题的意义明确的步骤的集合。从程序来说，也可以说算法是一个有限条指令的集合，这从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。些指令确定了解决某一特定类型问题的运算序列。对于同一个问题可以有不同的解题方法和步骤，也就是有对于同一个问题可以有不同的解题方法和步骤，
3、也就是有不同的算法。算法有优劣，一般而言，应当选择简单的、运算不同的算法。算法有优劣，一般而言，应当选择简单的、运算步骤少的，即步骤少的，即运算快、内存开销小运算快、内存开销小的算法（算法的时空效率）。的算法（算法的时空效率）。买电视机的步骤：买电视机的步骤：选好货物开票付款拿发票取货回家考大学上大学的步骤考大学上大学的步骤填报名单交报名费拿准考证参加考试得到录取通知书报到注册n计算机算法计算机能执行的算法n数值运算算法n非数值运算算法例例1 求求12345。可先写出这样的算法：可先写出这样的算法：（1）先求）先求12，得到结果，得到结果2；（2）将步骤）将步骤1得到的结果再乘以得到的结果再乘
4、以3，得到结果，得到结果6；（3）将）将6再乘以再乘以4，得到，得到24；（4）将）将24再乘以再乘以5，得到，得到120。求求123499呢呢n上述算法太繁琐，我们找一种通用的表示方法。s1:设变量p，被乘数，p=1;s2:设变量i,代表乘数，i=2;s3:使pi,乘积放在被乘数变量p中，可表示为：p i p;s4:使i的值加1，即i+1 i;s5:如果i不大于5，返回重新执行步骤s3以及其后的s4、s5;否则，算法结束。最后得到的p就是5!的值。例例1：求：求12345上述算法稍作改动：上述算法稍作改动：s1:1 p;s2:3 i;s3:p i p;s4:i+2 is5:若i11,返回s3
5、;否则，结束。例例2.2.求求1 13 35 57 79 91111 请同学们仔细分析循环结束的条件，即请同学们仔细分析循环结束的条件，即 s5步骤，如果在求求步骤，如果在求求13579 11时，将时，将s5步骤写成：步骤写成：s5：若：若i2500,算法停止。算法停止。（1）使）使S=0（S作为累加变量）；作为累加变量）；（2）使）使N=1（N代表分母）；代表分母）；（3）S+1.0/N S （执行迭代，（执行迭代，S为迭代变量）；为迭代变量）；（4）N+1 N；（5）若）若N100，转去执行（转去执行（3）以及其后的各步骤；否则）以及其后的各步骤；否则执行（执行（6）；）；（6）打印）打印
6、S的值（即所求之总和）。的值（即所求之总和）。可以写出下面的算法可以写出下面的算法例例5.求下级数的值求下级数的值n1、有穷性：、有穷性：n2、确定性：、确定性：n3、有、有0个或多个输入个或多个输入（即：可以没有输入，（即：可以没有输入，也可以有输入）也可以有输入）n4、有、有1个或多个输出个或多个输出（即算法必须得到结果）（即算法必须得到结果）n5、有效性、有效性 为了表示一个算法，可以用不同的方法。为了表示一个算法，可以用不同的方法。常用的算法表示方法：常用的算法表示方法：自然语言，传统流程图，结构化流程图（自然语言，传统流程图，结构化流程图（N-S流流程图），伪代码、计算机语言等。程图
7、），伪代码、计算机语言等。（重点：传统流程图，（重点：传统流程图，N-S流程图）流程图）自然语言就是人们常用的语言，可以是汉自然语言就是人们常用的语言，可以是汉语、英语或其他语言。语、英语或其他语言。用自然语言表示通俗易懂；用自然语言表示通俗易懂；但文字冗长，容易出现但文字冗长，容易出现“歧义歧义”性；性；而且，用自然语言描述包含分支和循环的而且，用自然语言描述包含分支和循环的算法，不很方便。算法，不很方便。一般不使用自然语言描述算法一般不使用自然语言描述算法例如：描述计算并输出例如：描述计算并输出z=y/x的流程，可以用自的流程，可以用自然语言描述如下：然语言描述如下：（1）输入）输入x，y
8、。（2）判断）判断x是否为是否为0：若若x=0,则输出错误信息；则输出错误信息；否则计算否则计算 y/x z，且输出，且输出z。自然语言描述举例自然语言描述举例算法描述语言：算法描述语言：是为了说明程序的流程而专门规定的某种是为了说明程序的流程而专门规定的某种语言。它一般介于自然语言与程序设计语言之间，它具有自语言。它一般介于自然语言与程序设计语言之间，它具有自然语言灵活的特点，同时又接近于程序设计语言的描述。然语言灵活的特点，同时又接近于程序设计语言的描述。注意：注意：算法描述语言所描述的流程，一般不能直接作为程序算法描述语言所描述的流程，一般不能直接作为程序来使用，最后还需转换成用某种程序
9、设计语言所描述的程序。来使用，最后还需转换成用某种程序设计语言所描述的程序。与程序设计语言的区别：与程序设计语言的区别：前者比较自由，不象后者那样受语法的约束，只要描述得人前者比较自由，不象后者那样受语法的约束，只要描述得人们能理解就行，而不必考虑计算机处理时所要遵循的规定或们能理解就行，而不必考虑计算机处理时所要遵循的规定或其它一些细节。其它一些细节。算法描述语言算法描述语言 流程图：流程图：用一些约定的几何图形来描述算法。用某用一些约定的几何图形来描述算法。用某种图框表示某种操作，用箭头表示算法流程种图框表示某种操作，用箭头表示算法流程流程图（的符号及意义）流程图（的符号及意义）美国标准化
10、协会美国标准化协会ANSI规定规定了一些常用的流程图符号，已为世界各国程序工作者普了一些常用的流程图符号，已为世界各国程序工作者普遍采用：遍采用：启止框输入输出框判断选择框处理框流程线连接点注释框 t=1i=2t=t*ii=i+1i5结束 NY 开始例：例：求求5！三种基本结构是：三种基本结构是：（1）顺序结构）顺序结构 按指令的顺序依次执行按指令的顺序依次执行（2）判断选择结构：）判断选择结构：根据判别条件有选择地改变根据判别条件有选择地改变 执行流程执行流程（3）循环结构：）循环结构：有条件的重复地执行某个程序块有条件的重复地执行某个程序块n依次顺序执行程序语句依次顺序执行程序语句 a块块
11、b块块AB例如，令例如，令a、b的值的值分别为分别为5、10；a=5；b=10；(1)顺序结构程序设计顺序结构程序设计n首先判别条件，若条件满足，程序执行首先判别条件，若条件满足，程序执行a块，否则，执行块，否则，执行b块；块；n举例，求举例，求a、b两个两个 数中的最大值；数中的最大值；条件成立？条件成立？执行执行a块块执行执行b块块成立成立不成立不成立b max？Max=a；max=b；YN(2)判别选择结构程序设计判别选择结构程序设计n循环又分循环又分“当型循环当型循环”和和“直到型循环直到型循环”n举例，求1100的累加和。int i，sum=0；while（i=100)sum=sum
12、+i;i=i+1;i5打印打印t循环结构程序设计循环结构程序设计 当型循环：当型循环：当条件当条件p成立时，反复执行循成立时，反复执行循环体中指令，直到环体中指令，直到p条件不成立为止。当条件不成立为止。当型循环先判断，再决定是否执行循环体，型循环先判断，再决定是否执行循环体，所以在条件所以在条件p一次都不满足时，循环体可一次都不满足时，循环体可能一次都不执行能一次都不执行当条件当条件p满足时满足时执行循环中指令执行循环中指令 直到型循环：直到型循环：当条件当条件p不成立时，反复不成立时，反复执行循环体中的指令，直到执行循环体中的指令，直到p条件成立为条件成立为止。直到型循环先执行循环体，然后
13、再止。直到型循环先执行循环体，然后再判断条件判断条件p，所以循环体至少执行一次。，所以循环体至少执行一次。直到条件直到条件p满足为止满足为止执行循环中的指令执行循环中的指令用伪代码表示算法（常常用于算法设计）用伪代码表示算法（常常用于算法设计）用传统流程图、用传统流程图、N-S图表示算法，直观易懂，但绘制比图表示算法，直观易懂，但绘制比较麻烦，在设计一个算法时，可能要反复修改，而修改较麻烦，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的，因此，流程图适合表示算法，但流程图是比较麻烦的，因此，流程图适合表示算法，但在设计算法过程中使用不是很理想。为了设计算法方便，在设计算法过程中使用
14、不是很理想。为了设计算法方便，常使用伪代码工具。常使用伪代码工具。伪代码是用介于自然语言和计算机语言之间的文字和符伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号，书写方便，格式号来描述算法。伪代码不用图形符号，书写方便，格式紧凑，便于向计算机语言算法过渡紧凑，便于向计算机语言算法过渡 用某种程序设计语言编写的程序本质上也是用某种程序设计语言编写的程序本质上也是问题处理方案的描述，并且是最终的描述。问题处理方案的描述，并且是最终的描述。在一般的程序设计过程中，不提倡一开始就在一般的程序设计过程中，不提倡一开始就编写程序，特别是对于大型的程序。编写程序，特别是对于
15、大型的程序。程序是程序设计的最终产品，需要经过每一程序是程序设计的最终产品，需要经过每一步的细致加工才能得到，如果企图一开始就编步的细致加工才能得到，如果企图一开始就编写出程序，往往会适得其反，达不到预想的结写出程序，往往会适得其反，达不到预想的结果果。例例 求求5！，用！，用C语言表示语言表示void main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%d”,t);判断闰年的具体程序#include void main()int year,yes;year=2000;while(year=2500)if(year%4=0&year%100
16、!=0|year%400=0)printf(%d年是闰年n,year);elseprintf(%d年不是闰年n,year);year+;例例 求级数的值求级数的值void main()int sign=1;float deno=2.0,sun=1.0,term;while(deno=100)sign=-sign;term=sign/deno;sum=sum+term;deno=deno+1;printf(“%f”,sum);结构化程序设计方法n一个结构化程序就是用高级语言表示的结一个结构化程序就是用高级语言表示的结构化算法。构化算法。n1、自顶向下、自顶向下 2、逐步细化、逐步细化n3、模块化设计、模块化设计 4、结构化编码、结构化编码结构化程序设计方法结构化程序设计方法一个结构化程序就是用高级语言表示的结构化算法。一个结构化程序就是用高级语言表示的结构化算法。1、自顶向下、自顶向下 2、逐步细化、逐步细化3、模块化设计、模块化设计 4、结构化编码、结构化编码作业nP36n 4（1）（4）（5）n 8（2）
