第二章程序的灵魂——算法

《第二章程序的灵魂——算法》由会员分享，可在线阅读，更多相关《第二章程序的灵魂——算法（42页珍藏版）》请在装配图网上搜索。

1、第二章程序的灵魂算法第二章程序的灵魂算法程序设计概述一个程序应包括对数据的描述和对数据处理的描述。1对数据的描述，即数据结构。数据结构是计算机学科的核心课程之一，有许多专门著作论述，本课程就不再赘述。在C语言中，系统提供的数据结构，是以数据类型的形式出现的。2对数据处理的描述，即计算机算法。算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。为此，著名计算机科学家沃思（Nikiklaus Wirth）提出一个公式：数据结构+算法=程序 实际上，一个程序除了数据结构和算法外，还必须使用一种计算机语言，并采用结构化方法来表示。算法:是指解决一个具体问题的意义明确的步骤的集合。是有限的 概括地说，

2、算法是指解题方案的准确而完整的描述。从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。对于同一个问题可以有不同的解题方法和步骤，也就是有不同的算法。算法有优劣，一般而言，应当选择简单的、运算步骤少的，既运算快、内存开销小的算法（算法的时空效率）。买电视机的步骤：选好货物开票付款拿发票取货回家考大学上大学的步骤填报名单交报名费拿准考证参加考试得到录取通知书报到注册例1 求12345。可先写出这样的算法：（1）先求12，得到结果2；（2）将步骤1得到的结果再乘以3，得到结果6；（3）将6再乘以4，得到24；（4）将24再乘以5，得到120。求12345

3、上述算法太繁琐，我们找一种通用的表示方法。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!的值。例2.求13579 11 如果题目改为求13579 11。上述算法稍作改动：s1:1 p;s2:3 i;s3:p i p;s4:i+2 is5:若i11,返回s3;否则，结束。求13579 11 可以看出，用这种方法表示的算法具有通用性、灵活性。S3到s5 组成一个循环，在实现算法时，要反复

4、多次执行s3、s4、s5等步骤，直到某一时刻，执行s5步骤时经过判断，乘数i已超过规定的数值而不返回s3步骤为止。计算机实现循环是轻而易举。求13579 11请同学们仔细分析循环结束的条件，即s5步骤，如果在求求13579 11时，将s5步骤写成：s5：若I2500,算法停止。（1）使S=0（S作为累加变量）；（2）使N=1（N代表分母）；（3）S+1/N S （执行迭代，S为迭代变量）；（4）N+1 N；（5）若N100，转去执行（3）以及其后的各步骤；否则执行（6）；（6）打印S的值（即所求之总和）。例例5.求下列级数的值求下列级数的值可以写出下面的算法可以写出下面的算法 1、有穷性：、有

5、穷性：一个算法应当包含一个算法应当包含有限的步骤，有限的步骤，而不能是无而不能是无限的步骤；同时一个算法应当在执行一定数量的步骤后，限的步骤；同时一个算法应当在执行一定数量的步骤后，算法结束，算法结束，不能死循环不能死循环。事实上事实上“有穷性有穷性”往往指往往指“在合理的范围之内在合理的范围之内”的有限的有限步骤。如果让计算机执行一个历时步骤。如果让计算机执行一个历时1000年才结束的算法，年才结束的算法，算法尽管有穷，但超过了合理的限度，人们也不认为此算法尽管有穷，但超过了合理的限度，人们也不认为此算法是有用的。算法是有用的。2、确定性：、确定性：算法中的算法中的每一个步骤都应当是确定的每

6、一个步骤都应当是确定的，而不，而不是含糊的、摸棱两可的。也就是说不应当产生歧义。特是含糊的、摸棱两可的。也就是说不应当产生歧义。特别是算法用自然语言描述时应当注意这点。别是算法用自然语言描述时应当注意这点。例如：例如：“将成绩优秀的同学名单打印输出将成绩优秀的同学名单打印输出”就是有歧义就是有歧义的。的。“成绩优秀成绩优秀”是要求每门课程都是要求每门课程都90分以上，还是平分以上，还是平均成绩在均成绩在90分以上？不明确，有歧义，不适合描述算法分以上？不明确，有歧义，不适合描述算法步骤。步骤。3、有、有0个或多个输入个或多个输入（即：可以没有输入，也可以有输（即：可以没有输入，也可以有输入）入

7、）所谓输入是指算法执行时所谓输入是指算法执行时从外界获取必要信息从外界获取必要信息。（外界。（外界是相对算法本身的，输入可以是人工键盘输入的数据，是相对算法本身的，输入可以是人工键盘输入的数据，也可以是程序其它部分传递给算法的数据）也可以是程序其它部分传递给算法的数据）例如：不需要输入任何信息，就可以计算出例如：不需要输入任何信息，就可以计算出5！；（！；（0个个输入）输入）例如：如果要计算两个整数的最大公约数，则需要输入例如：如果要计算两个整数的最大公约数，则需要输入2个整数个整数m，n。（。（2个输入）个输入）4、有、有1个或多个输出个或多个输出（即算法必须得到结果）（即算法必须得到结果）

8、算法的输出：算法得到的结果。算法的输出：算法得到的结果。算法必须有结果，没有算法必须有结果，没有结果的算法没有意义。结果的算法没有意义。（结果可以是显示在屏幕上的，（结果可以是显示在屏幕上的，也可以是将结果数据传递给程序的其它部分）也可以是将结果数据传递给程序的其它部分）5、有效性、有效性 算法的每个步骤都应当能有效执行，并能得到确定的结算法的每个步骤都应当能有效执行，并能得到确定的结果。例如：果。例如：b=0，则执行，则执行a/b是不能有效执行的。是不能有效执行的。为了表示一个算法，可以用不同的方法。常用为了表示一个算法，可以用不同的方法。常用的算法表示方法：的算法表示方法：自然语言，传统流

9、程图，结构化流程图自然语言，传统流程图，结构化流程图（N-S流程图），伪代码、计算机语言等。（重流程图），伪代码、计算机语言等。（重点：传统流程图，点：传统流程图，N-S流程图）流程图）自然语言就是人们常用的语言，可以是汉自然语言就是人们常用的语言，可以是汉语、英语或其他语言。语、英语或其他语言。用自然语言表示通俗易懂；用自然语言表示通俗易懂；但文字冗长，容易出现但文字冗长，容易出现“歧义歧义”性；性；而且，用自然语言描述包含分支和循环的而且，用自然语言描述包含分支和循环的算法，不很方便。算法，不很方便。一般不使用自然语言描述算法一般不使用自然语言描述算法例如：描述计算并输出例如：描述计算并输

10、出z=y/x的流程，可以用自的流程，可以用自然语言描述如下：然语言描述如下：（1）输入）输入x，y。（2）判断）判断x是否为是否为0：若若X=0,则输出错误信息；则输出错误信息；否则计算否则计算 y/x z，且输出，且输出z。自然语言描述举例自然语言描述举例算法描述语言：是为了说明程序的流程而专门规是为了说明程序的流程而专门规定的某种语言。它一般介于自然语言与程序设计语定的某种语言。它一般介于自然语言与程序设计语言之间，它具有自然语言灵活的特点，同时又接近言之间，它具有自然语言灵活的特点，同时又接近于程序设计语言的描述。于程序设计语言的描述。注意：算法描述语言所描述的流程，一般不能直接算法描述

11、语言所描述的流程，一般不能直接作为程序来使用，最后还需转换成用某种程序设计作为程序来使用，最后还需转换成用某种程序设计语言所描述的程序。语言所描述的程序。与程序设计语言的区别：前者比较自由，不象后者那样受语法的约束，只要前者比较自由，不象后者那样受语法的约束，只要描述得人们能理解就行，而不必考虑计算机处理时描述得人们能理解就行，而不必考虑计算机处理时所要遵循的规定或其它一些细节。所要遵循的规定或其它一些细节。算法描述语言算法描述语言在程序设计过程中，一般不可能在一开始就用某种程序设计语言编制计算机程序，而是先用某种简单、直观、灵活的描述工具来描述处理问题的流程。当方案确定以后，再将这样的流程转

12、换成计算机程序，这种转换往往是机械的，已经不涉及功能的重新设计或控制流程的变化，而只需考虑程序设计语言所规定的语法要求以及一细节问题。一、流程的描述一、流程的描述流程图：用一些约定的几何图形来描述算法。用某种流程图：用一些约定的几何图形来描述算法。用某种图框表示某种操作，用箭头表示算法流程图框表示某种操作，用箭头表示算法流程流程图（的符号及意义）美国标准化协会流程图（的符号及意义）美国标准化协会ANSI规定了一规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用：些常用的流程图符号，已为世界各国程序工作者普遍采用：启止框输入输出框判断选择框处理框流程线连接点注释框 l起止框：起止框：表示

13、算法的开始和结束。一般内部只写表示算法的开始和结束。一般内部只写“开始开始”或或“结束结束”。l l 处理框：处理框：表示算法的某个处理步骤，一般内部常常填写表示算法的某个处理步骤，一般内部常常填写赋值操作。赋值操作。l l输入输出框：输入输出框：表示算法请求输入输入需要的数据或算法表示算法请求输入输入需要的数据或算法将某些结果输出。一般内部常常填写将某些结果输出。一般内部常常填写“输入输入”,“打印打印/显示显示”l l菱形框（判断框）菱形框（判断框）：作用主要是对一个给定条件进行判作用主要是对一个给定条件进行判断，根据给定的条件是否成立来决定如何执行其后的操作。断，根据给定的条件是否成立来

14、决定如何执行其后的操作。它有一个入口，两个出口。它有一个入口，两个出口。l l连接点连接点：用于将画在不同地方的流程线连接起来。同一用于将画在不同地方的流程线连接起来。同一个编号的点是相互连接在一起的，实际上同一编号的点是个编号的点是相互连接在一起的，实际上同一编号的点是同一个点，只是画不下才分开画。使用连接点，还可以避同一个点，只是画不下才分开画。使用连接点，还可以避免流程线的交叉或过长，使流程图更加清晰。免流程线的交叉或过长，使流程图更加清晰。l l注释框注释框：注释框不是流程图中必须的部分，不反映流程注释框不是流程图中必须的部分，不反映流程和操作，它只是对流程图中某些框的操作做必要的补充

15、说和操作，它只是对流程图中某些框的操作做必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。明，以帮助阅读流程图的人更好地理解流程图的作用。例：例：求求5 5！t=1i=2t=t*ii=i+1i5结束 NY 开始 传统流程图采用流程线指出各框的执行顺序，传统流程图采用流程线指出各框的执行顺序，对对流程线的使用没有严格限制流程线的使用没有严格限制。因此，使用者可以。因此，使用者可以不受限制地使流程转来转去，使流程图变得毫无不受限制地使流程转来转去，使流程图变得毫无规律规律。人们对这种流程图进行改进，。人们对这种流程图进行改进，规定几种基规定几种基本的结构，然后由这些基本结构按一定规律组成

16、本的结构，然后由这些基本结构按一定规律组成算法结构，整个算法结构是由上而下地将各个基算法结构，整个算法结构是由上而下地将各个基本结构顺序排列起来本结构顺序排列起来。这样可以在一定程度上，。这样可以在一定程度上，提高算法的质量。提高算法的质量。三种基本结构是：（1）顺序结构 按指令的顺序依次执行（2）判断选择结构：根据判别条件有选择地改变 执行流程（3）循环结构：有条件的重复地执行某个程序块(1)顺序结构程序设计 依次顺序执行程序语句 执行执行a块块执行执行b块块a块块b块块AB例如，令例如，令a、b的值的值分别为分别为5、10；a=5；b=10；(2)判别选择结构程序设计 首先判别条件，若条件

17、满足，程序执行a块，否则，执行b块；举例，求a、b两个 数中的最大值；满足条件否满足条件否满足满足不满足不满足执行执行a块块执行执行b块块条件成立？条件成立？执行执行a块块执行执行b块块成立成立不成立不成立b max？Max=a；max=b；YN(3)循环结构程序设计 循环又分“当型循环”和“直到型循环”举例，求1100的累加和。int i，sum=0；while（i=100)sum=sum+i;i=i+1;直到条件满足为止直到条件满足为止执行循环中的指令执行循环中的指令当条件满足时当条件满足时执行循环中指令执行循环中指令i5打印打印t 当型循环：当型循环：当条件当条件p成立时，反复执行成立时

18、，反复执行循环体中指令，直到循环体中指令，直到p条件不成立为止。条件不成立为止。当型循环先判断，再决定是否执行循环当型循环先判断，再决定是否执行循环体，所以在条件体，所以在条件p一次都不满足时，循一次都不满足时，循环体可能一次都不执行环体可能一次都不执行当条件当条件p满足时满足时执行循环中指令执行循环中指令 直到型循环：直到型循环：当条件当条件p不成立时，反复执不成立时，反复执行循环体中的指令，直到行循环体中的指令，直到p条件成立为止。条件成立为止。直到型循环先执行循环体，然后再判断直到型循环先执行循环体，然后再判断条件条件p，所以循环体至少执行一次。，所以循环体至少执行一次。直到条件直到条件

19、p满足为止满足为止执行循环中的指令执行循环中的指令用伪代码表示算法（常常用于算法设计）用伪代码表示算法（常常用于算法设计）用传统流程图、用传统流程图、N-S图表示算法，直观易懂，但绘制图表示算法，直观易懂，但绘制比较麻烦，在设计一个算法时，可能要反复修改，而比较麻烦，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的，因此，流程图适合表示算修改流程图是比较麻烦的，因此，流程图适合表示算法，但在设计算法过程中使用不是很理想。为了设计法，但在设计算法过程中使用不是很理想。为了设计算法方便，常使用伪代码工具。算法方便，常使用伪代码工具。伪代码是用介于自然语言和计算机语言之间的文字和伪代码是用

20、介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号，书写方便，符号来描述算法。伪代码不用图形符号，书写方便，格式紧凑，便于向计算机语言算法过渡格式紧凑，便于向计算机语言算法过渡 用某种程序设计语言编写的程序本质上也是问题处理方案的描述，并且是最终的描述。在一般的程序设计过程中，不提倡一开始就编写程序，特别是对于大型的程序。程序是程序设计的最终产品，需要经过每一步的细致加工才能得到，如果企图一开始就编写出程序，往往会适得其反，达不到预想的结果。例题例题例例2.20 求求5！，用！，用C语言表示语言表示Main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%d”,t);例例 求级数的值求级数的值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);请参见书中P32演讲完毕，谢谢观看！