《程序的灵魂算法课件》由会员分享，可在线阅读，更多相关《程序的灵魂算法课件（39页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章程序的灵魂程序的灵魂算法算法1 1程序的灵魂算法程序设计概述程序设计概述一个程序应包括对数据的描述和对数据处理的描述。 1对数据的描述，即数据结构。数据结构是计算机学科的核心课程之一，有许多专门著作论述，本课程就不再赘述。 在C语言中，系统提供的数据结构，是以数据类型的形式出现的。 2对数据处理的描述，即计算机算法。算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。为此，著名计算机科学家沃思（Nikiklaus Wirth）提出一个公式： 数据结构 + 算法 = 程序 实际上，一个程序除了数据结构和算法外，还必须使用一种计算机语言，并采用结构化方法来表示。2 2程序的灵魂算法算
2、法:是指解决一个具体问题的意义明确的步骤的集合,是有限的。 概括地说，算法是指解题方案的准确而完整的描述。从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。 对于同一个问题可以有不同的解题方法和步骤，也就是有不同的算法。算法有优劣，一般而言，应当选择简单的、运算步骤少的，既运算快、内存开销小的算法（算法的时空效率）。2.1 算法的概念3 3程序的灵魂算法买电视机的步骤：选好货物开票付款拿发票取货回家考大学上大学的步骤填报名单交报名费拿准考证参加考试得到录取通知书报到注册4 4程序的灵魂算法 2.2、 简单算法举例例例1求求12345。可先写出这样的算
3、法：可先写出这样的算法：（1）先求）先求12，得到结果，得到结果2；（2）将步骤）将步骤1得到的结果再乘以得到的结果再乘以3，得到结，得到结果果6；（3）将）将6再乘以再乘以4，得到，得到24；（4）将）将24再乘以再乘以5，得到，得到120。5 5程序的灵魂算法求12345上述算法太繁琐，我们找一种通用上述算法太繁琐，我们找一种通用的表示方法。的表示方法。S1:设变量设变量p，被乘数，被乘数，p=1;s2:设变量设变量i,代表乘数，代表乘数，i=2;s3:使使pi,乘积放在被乘数变量乘积放在被乘数变量p中，可中，可表示为：表示为：pip;s4:使使i的值加的值加1，即，即i+1i;s5:如果
4、如果i不大于不大于5，返回重新执行步骤，返回重新执行步骤s3以及其后的以及其后的s4、s5;否则，算法结否则，算法结束。最后得到的束。最后得到的p就是就是5!的值。的值。6 6程序的灵魂算法例2.求13579 11如果题目改为求如果题目改为求1357911。上述算法稍作改动：上述算法稍作改动：s1:1p;s2:3i;s3:pip;s4:i+2is5:若若i 11,返回返回s3;否则，结束。否则，结束。7 7程序的灵魂算法求13579 11 可以看出，用这种方法表示的算法可以看出，用这种方法表示的算法具有通用性、灵活性。具有通用性、灵活性。S3到到s5组成一个组成一个循环，在实现算法时，要反复多
5、次执行循环，在实现算法时，要反复多次执行s3、s4、s5等步骤，直到某一时刻，执等步骤，直到某一时刻，执行行s5步骤时经过判断，乘数步骤时经过判断，乘数i已超过规定已超过规定的数值而不返回的数值而不返回s3步骤为止。步骤为止。计算机实现循环是轻而易举。计算机实现循环是轻而易举。8 8程序的灵魂算法求13579 11请同学们仔细分析循环结束的条件，即请同学们仔细分析循环结束的条件，即s5步骤，如果在求求步骤，如果在求求1357911时，将时，将s5步骤写成：步骤写成：s5：若：若I2500,算法停止。算法停止。1313程序的灵魂算法（1）使）使S=0（S作为累加变量）；作为累加变量）；（2）使）
6、使N=1（N代表分母）；代表分母）；（3）S+1/NS（执行迭代，（执行迭代，S为迭代变量）；为迭代变量）；（4）N+1N；（5）若）若N100，转去执行（转去执行（3）以及其后的各步骤；）以及其后的各步骤；否则执行（否则执行（6）；）；（6）打印）打印S的值（即所求之总和）。的值（即所求之总和）。例例5.求下列级数的值求下列级数的值可以写出下面的算法可以写出下面的算法1414程序的灵魂算法1、有有穷穷性性：一一个个算算法法应应当当包包含含有有限限的的步步骤骤，而而不不能能是是无无限限的的步步骤骤；同同时时一一个个算算法法应应当当在在执执行行一一定定数数量量的的步步骤骤后后，算法结束，不能死循
7、环。算法结束，不能死循环。事事实实上上“有有穷穷性性”往往往往指指“在在合合理理的的范范围围之之内内”的的有有限限步步骤骤。如如果果让让计计算算机机执执行行一一个个历历时时1000年年才才结结束束的的算算法法，算算法法尽尽管管有有穷穷，但但超超过过了了合合理理的的限限度度，人人们们也也不不认认为为此此算法是有用的。算法是有用的。2、确确定定性性：算算法法中中的的每每一一个个步步骤骤都都应应当当是是确确定定的的，而而不不是是含含糊糊的的、摸摸棱棱两两可可的的。也也就就是是说说不不应应当当产产生生歧歧义义。特特别是算法用自然语言描述时应当注意这点。别是算法用自然语言描述时应当注意这点。例例如如：“
8、将将成成绩绩优优秀秀的的同同学学名名单单打打印印输输出出”就就是是有有歧歧义义的的。“成成绩绩优优秀秀”是是要要求求每每门门课课程程都都90分分以以上上，还还是是平平均均成成绩绩在在90分分以以上上？不不明明确确，有有歧歧义义，不不适适合合描描述述算算法法步骤。步骤。2.3. 算法的特性1515程序的灵魂算法3、有有0个个或或多多个个输输入入（即即：可可以以没没有有输输入入，也也可可以以有有输输入）入）所所谓谓输输入入是是指指算算法法执执行行时时从从外外界界获获取取必必要要信信息息。（外外界界是是相相对对算算法法本本身身的的，输输入入可可以以是是人人工工键键盘盘输输入入的的数数据据，也可以是程
9、序其它部分传递给算法的数据）也可以是程序其它部分传递给算法的数据）例例如如：不不需需要要输输入入任任何何信信息息，就就可可以以计计算算出出5！；（0个个输入）输入）例例如如：如如果果要要计计算算两两个个整整数数的的最最大大公公约约数数，则则需需要要输输入入2个整数个整数m，n。（。（2个输入）个输入）4、有、有1个或多个输出（即算法必须得到结果）个或多个输出（即算法必须得到结果）算算法法的的输输出出：算算法法得得到到的的结结果果。算算法法必必须须有有结结果果，没没有有结结果果的的算算法法没没有有意意义义。（结结果果可可以以是是显显示示在在屏屏幕幕上上的的，也可以是将结果数据传递给程序的其它部分
10、）也可以是将结果数据传递给程序的其它部分）5、有效性、有效性算算法法的的每每个个步步骤骤都都应应当当能能有有效效执执行行，并并能能得得到到确确定定的的结结果。例如：果。例如：b=0，则执行，则执行a/b是不能有效执行的。是不能有效执行的。1616程序的灵魂算法2.4.怎样表示一个算法？怎样表示一个算法？为了表示一个算法，可以用不同的方法。常用为了表示一个算法，可以用不同的方法。常用的算法表示方法：的算法表示方法：自然语言，传统流程图，结构化流程图自然语言，传统流程图，结构化流程图（N-S流程图），伪代码、计算机语言等。（重流程图），伪代码、计算机语言等。（重点：传统流程图，点：传统流程图，N-
11、S流程图）流程图）1717程序的灵魂算法2.4.1用自然语言表示算法用自然语言表示算法 自然语言就是人们常用的语言，可以是汉自然语言就是人们常用的语言，可以是汉语、英语或其他语言。语、英语或其他语言。用自然语言表示通俗易懂；用自然语言表示通俗易懂；但文字冗长，容易出现但文字冗长，容易出现“歧义歧义”性；性；而且，用自然语言描述包含分支和循环的而且，用自然语言描述包含分支和循环的算法，不很方便。算法，不很方便。一般不使用自然语言描述算法一般不使用自然语言描述算法1818程序的灵魂算法例如：描述计算并输出例如：描述计算并输出z=y/x的流程，可以用自然的流程，可以用自然语言描述如下：语言描述如下：
12、（1）输入）输入x，y。（2）判断）判断x是否为是否为0： 若若X=0,则输出错误信息；则输出错误信息； 否则计算否则计算 y/x z，且输出，且输出z。自然语言描述举例自然语言描述举例1919程序的灵魂算法算法描述语言算法描述语言：是为了说明程序的流程而专门规是为了说明程序的流程而专门规定的某种语言。它一般介于自然语言与程序设计语定的某种语言。它一般介于自然语言与程序设计语言之间，它具有自然语言灵活的特点，同时又接近言之间，它具有自然语言灵活的特点，同时又接近于程序设计语言的描述。于程序设计语言的描述。注意注意：算法描述语言所描述的流程，一般不能直接算法描述语言所描述的流程，一般不能直接作为
13、程序来使用，最后还需转换成用某种程序设计作为程序来使用，最后还需转换成用某种程序设计语言所描述的程序。语言所描述的程序。与程序设计语言的区别与程序设计语言的区别： 前者比较自由，不象后者那样受语法的约束，只要前者比较自由，不象后者那样受语法的约束，只要描述得人们能理解就行，而不必考虑计算机处理时描述得人们能理解就行，而不必考虑计算机处理时所要遵循的规定或其它一些细节。所要遵循的规定或其它一些细节。算法描述语言算法描述语言2020程序的灵魂算法在程序设计过程中，一般不可能在一开始就用在程序设计过程中，一般不可能在一开始就用某种程序设计语言编制计算机程序，而是先用某某种程序设计语言编制计算机程序，
14、而是先用某种简单、直观、灵活的描述工具来描述处理问题种简单、直观、灵活的描述工具来描述处理问题的流程。当方案确定以后，再将这样的流程转换的流程。当方案确定以后，再将这样的流程转换成计算机程序，这种转换往往是机械的，已经不成计算机程序，这种转换往往是机械的，已经不涉及功能的重新设计或控制流程的变化，而只需涉及功能的重新设计或控制流程的变化，而只需考虑程序设计语言所规定的语法要求以及一细节考虑程序设计语言所规定的语法要求以及一细节问题。问题。一、流程的描述一、流程的描述2.4.2用流程图表示算法用流程图表示算法2121程序的灵魂算法流程图：用一些约定的几何图形来描述算法。用某种图流程图：用一些约定
15、的几何图形来描述算法。用某种图框表示某种操作，用箭头表示算法流程框表示某种操作，用箭头表示算法流程流程图（的符号及意义）美国标准化协会流程图（的符号及意义）美国标准化协会ANSI规定了一规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用：些常用的流程图符号，已为世界各国程序工作者普遍采用：启止框输入输出框判断选择框处理框流程线连接点注释框2222程序的灵魂算法l起起止止框框：表表示示算算法法的的开开始始和和结结束束。一一般般内内部部只只写写“开开始始”或或“结束结束”。l l处处理理框框：表表示示算算法法的的某某个个处处理理步步骤骤，一一般般内内部部常常常常填填写写赋值操作。赋值操作。
16、l l输输入入输输出出框框：表表示示算算法法请请求求输输入入输输入入需需要要的的数数据据或或算算法法将将某某些些结结果果输输出出。一一般般内内部部常常常常填填写写“输输入入”,“打打印印/显显示示”l l菱菱形形框框（判判断断框框）：作作用用主主要要是是对对一一个个给给定定条条件件进进行行判判断断，根根据据给给定定的的条条件件是是否否成成立立来来决决定定如如何何执执行行其其后后的的操操作作。它有一个入口，两个出口。它有一个入口，两个出口。l l连连接接点点：用用于于将将画画在在不不同同地地方方的的流流程程线线连连接接起起来来。同同一一个个编编号号的的点点是是相相互互连连接接在在一一起起的的，实
17、实际际上上同同一一编编号号的的点点是是同同一一个个点点，只只是是画画不不下下才才分分开开画画。使使用用连连接接点点，还还可可以以避避免流程线的交叉或过长，使流程图更加清晰。免流程线的交叉或过长，使流程图更加清晰。l l注注释释框框：注注释释框框不不是是流流程程图图中中必必须须的的部部分分，不不反反映映流流程程和和操操作作，它它只只是是对对流流程程图图中中某某些些框框的的操操作作做做必必要要的的补补充充说说明，以帮助阅读流程图的人更好地理解流程图的作用。明，以帮助阅读流程图的人更好地理解流程图的作用。2323程序的灵魂算法例：例： 求求5 5！t=1i=2t=t*ii=i+1i5结束 NY 开始
18、2424程序的灵魂算法传传统统流流程程图图采采用用流流程程线线指指出出各各框框的的执执行行顺顺序序，对对流流程程线线的的使使用用没没有有严严格格限限制制。因因此此，使使用用者者可可以以不不受受限限制制地地使使流流程程转转来来转转去去，使使流流程程图图变变得得毫毫无无规规律律。人人们们对对这这种种流流程程图图进进行行改改进进，规规定定几几种种基基本本的的结结构构，然然后后由由这这些些基基本本结结构构按按一一定定规规律律组组成成算算法法结结构构，整整个个算算法法结结构构是是由由上上而而下下地地将将各各个个基基本本结结构构顺顺序序排排列列起起来来。这这样样可可以以在在一一定定程程度度上上，提高算法的
19、质量。提高算法的质量。2525程序的灵魂算法三种基本结构是：三种基本结构是：（1）顺序结构）顺序结构按指令的顺序依次执行按指令的顺序依次执行（2）判断选择结构：）判断选择结构：根据判别条件有选择地改变根据判别条件有选择地改变执行流程执行流程（3）循环结构：）循环结构：有条件的重复地执行某个程序块有条件的重复地执行某个程序块2.4.3三种基本结构和改进的流程图三种基本结构和改进的流程图2626程序的灵魂算法(1)顺序结构程序设计依次顺序执行程序语句 执行执行a块块执行执行b块块a块块b块块AB例如，令例如，令a、b的值的值分别为分别为5、10； a = 5； b = 10；2727程序的灵魂算法
20、(2)判别选择结构程序设计首先判别条件，若条件满足，程序执行首先判别条件，若条件满足，程序执行a块，否则，执行块，否则，执行b块；块；举例，求举例，求a、b两个两个数中的最大值；数中的最大值；满足条件否满足条件否满足满足不满足不满足执行执行a块块执行执行b块块条件成立？条件成立？执行执行a块块执行执行b块块成立成立不成立不成立b max？Max = a；max = b；YN2828程序的灵魂算法(3)循环结构程序设计循环又分循环又分“当型循环当型循环”和和“直到型循环直到型循环”举例，求举例，求1100的累加和。的累加和。inti，sum=0；while（i=100)sum=sum+i;i=i
21、+1;直到条件满足为止直到条件满足为止执行循环中的指令执行循环中的指令当条件满足时当条件满足时执行循环中指令执行循环中指令i5打印打印t3434程序的灵魂算法当型循环：当条件当型循环：当条件p成立时，反复执行成立时，反复执行循环体中指令，直到循环体中指令，直到p条件不成立为止。条件不成立为止。当型循环先判断，再决定是否执行循环当型循环先判断，再决定是否执行循环体，所以在条件体，所以在条件p一次都不满足时，循一次都不满足时，循环体可能一次都不执行环体可能一次都不执行当条件当条件p满足时满足时执行循环中指令执行循环中指令3535程序的灵魂算法直直到到型型循循环环：当当条条件件p不不成成立立时时，反
22、反复复执执行行循循环环体体中中的的指指令令，直直到到p条条件件成成立立为为止止。直直到到型型循循环环先先执执行行循循环环体体，然然后后再再判判断断条件条件p，所以循环体至少执行一次。，所以循环体至少执行一次。直到条件直到条件p满足为止满足为止执行循环中的指令执行循环中的指令3636程序的灵魂算法2.4.5用伪代码表示算法用伪代码表示算法用伪代码表示算法（常常用于算法设计）用伪代码表示算法（常常用于算法设计）用传统流程图、用传统流程图、N-S图表示算法，直观易懂，但绘制图表示算法，直观易懂，但绘制比较麻烦，在设计一个算法时，可能要反复修改，而比较麻烦，在设计一个算法时，可能要反复修改，而修改流程
23、图是比较麻烦的，因此，流程图适合表示算修改流程图是比较麻烦的，因此，流程图适合表示算法，但在设计算法过程中使用不是很理想。为了设计法，但在设计算法过程中使用不是很理想。为了设计算法方便，常使用伪代码工具。算法方便，常使用伪代码工具。伪代码是用介于自然语言和计算机语言之间的文字和伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号，书写方便，符号来描述算法。伪代码不用图形符号，书写方便，格式紧凑，便于向计算机语言算法过渡格式紧凑，便于向计算机语言算法过渡3737程序的灵魂算法 用某种程序设计语言编写的程序本质上也用某种程序设计语言编写的程序本质上也是问题处理方案的描述
24、，并且是最终的描是问题处理方案的描述，并且是最终的描述。述。在一般的程序设计过程中，不提倡一开在一般的程序设计过程中，不提倡一开始就编写程序，特别是对于大型的程序。始就编写程序，特别是对于大型的程序。程序是程序设计的最终产品，需要经过程序是程序设计的最终产品，需要经过每一步的细致加工才能得到，如果企图一每一步的细致加工才能得到，如果企图一开始就编写出程序，往往会适得其反，达开始就编写出程序，往往会适得其反，达不到预想的结果不到预想的结果。2.4.6用计算机语言表示算法用计算机语言表示算法3838程序的灵魂算法例题例题例例2.20 求求5！，用！，用C语言表示语言表示Main ( )int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%d”,t);3939程序的灵魂算法
