《(6.8)--补充课件第02讲-程序的灵魂——算法.ppt》由会员分享，可在线阅读，更多相关《(6.8)--补充课件第02讲-程序的灵魂——算法.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二讲第二讲程序的灵魂算法程序的灵魂算法C语言程序设计语言程序设计 The C Programming Language2C语言程序设计语言程序设计 温州理工学院温州理工学院 2程序的灵魂算法程序的灵魂算法程序设计概述程序设计概述算法算法怎样表示一个算法怎样表示一个算法小结小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间3C语言程序设计语言程序设计 温州理工学院温州理工学院 3程序的灵魂算法程序的灵魂算法程序设计概述程序设计概述算法算法怎样表示一个算法怎样表示一个算法小结小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间4C语言程序设计语言程序设计 温州理工学院温州理工学院 4程
2、序设计概述程序设计概述Niklaus E.Wirth(1934-)SwitzerlandPascal,Structured Programming 1984,Turing Award5C语言程序设计语言程序设计 温州理工学院温州理工学院 5算法、语言、程序的关系算法、语言、程序的关系算法算法：描述了数据对象的元素之间的关系（包：描述了数据对象的元素之间的关系（包括数据逻辑关系、括数据逻辑关系、存储关系描述）。存储关系描述）。描述算法的工具：算法可用自然语言、框图或描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。高级程序设计语言进行描述。自然语言简单但易于产生二义，框图直观自然
3、语言简单但易于产生二义，框图直观但不擅长表达数据的组织结构，但不擅长表达数据的组织结构，而高级程而高级程序语言则较为准确但又比较严谨。序语言则较为准确但又比较严谨。程序程序是算法在计算机中的实现是算法在计算机中的实现(与所用计算机与所用计算机及语言有关及语言有关)。6C语言程序设计语言程序设计 温州理工学院温州理工学院 6算法、语言、程序的关系算法、语言、程序的关系Niklaus E.Wirth给出的公式：算法给出的公式：算法+数据结构数据结构=程序，说明数据结构和算法是程序的两大要程序，说明数据结构和算法是程序的两大要素，二者相辅相成，缺一不可。算法是程序的素，二者相辅相成，缺一不可。算法是
4、程序的灵魂。灵魂。算法算法和和程序程序都是用来表达解决问题的逻辑步骤，都是用来表达解决问题的逻辑步骤，但算法独立于具体的计算机，与具体的程序设但算法独立于具体的计算机，与具体的程序设计语言无关，而程序正好相反；程序是算法，计语言无关，而程序正好相反；程序是算法，但算法不一定是程序。但算法不一定是程序。7C语言程序设计语言程序设计 温州理工学院温州理工学院 7程序的灵魂算法程序的灵魂算法程序设计概述程序设计概述算法算法算法的概念算法的概念简单算法举例简单算法举例算法的特性算法的特性怎样怎样表示一个算法表示一个算法小结小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间8C语言程序设计语言程序
5、设计 温州理工学院温州理工学院 8What is an algorithm?The Art of Computer Programming,Addison-Wesley.Vol 1-Fundamental Algorithms Donald E.Knuth(January 10,1938-)Turing Award(1974)“A finite set of rules which gives a sequence of operations for solving a specific type of problem.”算法是规则的有限集合，算法是规则的有限集合，是为是为解决特定问题而规定的
6、一系列解决特定问题而规定的一系列操作。操作。9C语言程序设计语言程序设计 温州理工学院温州理工学院 9算法的概念算法的概念算法算法算法算法是指解决一个具体问题的意义明确的步骤是指解决一个具体问题的意义明确的步骤的集合。是有限的。的集合。是有限的。概括地说，概括地说，算法算法是指解题方案的准确而完整的是指解题方案的准确而完整的描述。从程序来说，也可以说算法是一个有限描述。从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。类型问题的运算序列。对于同一个问题可以有不同的解题方法和步骤，对于同一个问题可以有不同的解题方
7、法和步骤，也就是有不同的算法。也就是有不同的算法。算法有优劣算法有优劣，一般而言，一般而言，应当选择简单的、运算步骤少的，既运算快、应当选择简单的、运算步骤少的，既运算快、内存开销小的算法（算法的时空效率）。内存开销小的算法（算法的时空效率）。10C语言程序设计语言程序设计 温州理工学院温州理工学院 10简单算法举例简单算法举例例例1 求求12345。可先写出这样的算法：可先写出这样的算法：先求先求12，得到结果，得到结果2；将步骤将步骤1得到的结果再乘以得到的结果再乘以3，得到结果，得到结果6；将将6再乘以再乘以4，得到，得到24；将将24再乘以再乘以5，得到，得到120。上述算法太繁琐，我
8、们找一种通用的表示方法。上述算法太繁琐，我们找一种通用的表示方法。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!的值。的值。11简单算法举例简单算法举例例例2.求求13579 11上述算法稍作改动：上述算法稍作改动：s1:1 p;s2:3 i
9、;s3:p i p;s4:i+2 is5:若若i 11,返回返回s3;否则，否则，结束。结束。用这种方法表示的算法具有用这种方法表示的算法具有通用性、灵活性。通用性、灵活性。s3到到s5 组组成一个循环，在实现算法时，成一个循环，在实现算法时，要反复多次执行要反复多次执行s3、s4、s5等步骤，直到某一时刻，执等步骤，直到某一时刻，执行行s5步骤时经过判断，乘数步骤时经过判断，乘数i已超过规定的数值而不返回已超过规定的数值而不返回s3步骤为止。步骤为止。计算机实现循环是轻而易举。计算机实现循环是轻而易举。将将s5步骤写成：步骤写成：“s5：若：若i2500,算法停止。算法停止。16简单算法举例
10、简单算法举例例例5.求下列级数的值求下列级数的值可以写出下面的算法可以写出下面的算法（1）使）使S=0（S作为累加变量）；作为累加变量）；（2）使）使N=1（N代表分母）；代表分母）；（3）S+1/N S （执行迭代，（执行迭代，S为迭代变量）；为迭代变量）；（4）N+1 N；（5）若）若N100，转去执行（转去执行（3）以及其后的各步骤；否则执）以及其后的各步骤；否则执行（行（6）；）；（6）打印）打印S的值（即所求之总和）。的值（即所求之总和）。17C语言程序设计语言程序设计 温州理工学院温州理工学院 17算法的特性算法的特性有穷性有穷性一一个个算算法法应应当当包包含含有有限限的的步步骤骤
11、，而而不不能能是是无无限限的的步步骤骤；同同时时一一个个算法应当在执行一定数量的步骤后，算法结束，算法应当在执行一定数量的步骤后，算法结束，不能死循环不能死循环。事事实实上上“有有穷穷性性”往往往往指指“在在合合理理的的范范围围之之内内”的的有有限限步步骤骤。如如果果让让计计算算机机执执行行一一个个历历时时1000年年才才结结束束的的算算法法，算算法法尽尽管管有有穷穷，但超过了合理的限度，人们也不认为此算法是有用的。但超过了合理的限度，人们也不认为此算法是有用的。确定性确定性算算法法中中的的每每一一个个步步骤骤都都应应当当是是确确定定的的，而而不不是是含含糊糊的的、摸摸棱棱两两可可的的。也也就
12、就是是说说不不应应当当产产生生歧歧义义。特特别别是是算算法法用用自自然然语语言言描描述述时时应应当注意这点。当注意这点。例例如如：“将将成成绩绩优优秀秀的的同同学学名名单单打打印印输输出出”就就是是有有歧歧义义的的。“成成绩绩优优秀秀”是是要要求求每每门门课课程程都都90分分以以上上，还还是是平平均均成成绩绩在在90分分以以上上？不明确，有歧义，不适合描述算法步骤。？不明确，有歧义，不适合描述算法步骤。18C语言程序设计语言程序设计 温州理工学院温州理工学院 18算法的特性算法的特性有有0个或多个输入（即：可以没有输入，也可以有输入）个或多个输入（即：可以没有输入，也可以有输入）所所谓谓输输入
13、入是是指指算算法法执执行行时时从从外外界界获获取取必必要要信信息息。（外外界界是是相相对对算算法法本本身身的的，输输入入可可以以是是人人工工键键盘盘输输入入的的数数据据，也也可可以以是是程程序序其其它它部部分分传传递递给给算算法的数据）法的数据）例如：不需要输入任何信息，就可以计算出例如：不需要输入任何信息，就可以计算出5！；（！；（0个输入）个输入）例例如如：如如果果要要计计算算两两个个整整数数的的最最大大公公约约数数，则则需需要要输输入入2个个整整数数m，n。（2个输入）个输入）有有1个或多个输出（即算法必须得到结果）个或多个输出（即算法必须得到结果）算算法法的的输输出出：算算法法得得到到
14、的的结结果果。算算法法必必须须有有结结果果，没没有有结结果果的的算算法法没没有有意意义义。（结结果果可可以以是是显显示示在在屏屏幕幕上上的的，也也可可以以是是将将结结果果数数据据传传递递给给程程序序的其它部分）的其它部分）有效性有效性算算法法的的每每个个步步骤骤都都应应当当能能有有效效执执行行，并并能能得得到到确确定定的的结结果果。例例如如：b=0，则执行，则执行a/b是不能有效执行的。是不能有效执行的。19C语言程序设计语言程序设计 温州理工学院温州理工学院 19怎样表示一个算法？怎样表示一个算法？为了表示一个算法，可以用不同的方法。常用为了表示一个算法，可以用不同的方法。常用的算法表示方法
15、：的算法表示方法：自然语言自然语言传统流程图传统流程图结构化流程图（结构化流程图（N-S流程图）流程图）伪代码伪代码计算机语言等。计算机语言等。重点：传统流程图，重点：传统流程图，N-S流程图流程图20C语言程序设计语言程序设计 温州理工学院温州理工学院 20程序的灵魂算法程序的灵魂算法程序设计概述程序设计概述算法算法怎样表示一个算法怎样表示一个算法自然语言自然语言传统流程图传统流程图结构化流程图（结构化流程图（N-SN-S流程图）流程图）伪代码伪代码计算机语言计算机语言小结小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间21C语言程序设计语言程序设计 温州理工学院温州理工学院 21用
16、自然语言表示算法用自然语言表示算法自然语言就是人们常用的语言，可以是汉语、英语或其他自然语言就是人们常用的语言，可以是汉语、英语或其他语言。语言。用自然语言表示通俗易懂；用自然语言表示通俗易懂；但文字冗长，容易出现但文字冗长，容易出现“歧义歧义”性；性；而且，用自然语言描述包含分支和循环的算法，不很方便。而且，用自然语言描述包含分支和循环的算法，不很方便。一般不使用自然语言描述算法一般不使用自然语言描述算法自然语言描述举例自然语言描述举例例如：描述计算并输出例如：描述计算并输出z=y/x的流程，可以用自然语言描述如下：的流程，可以用自然语言描述如下：（1）输入）输入x，y。（2）判断）判断x是
17、否为是否为0：若若X=0,则输出错误信息；则输出错误信息；否则计算否则计算 y/x z，且输出，且输出z。22C语言程序设计语言程序设计 温州理工学院温州理工学院 22算法描述语言算法描述语言算法描述语言算法描述语言为了说明程序的流程而专门规定的某种语言。它一为了说明程序的流程而专门规定的某种语言。它一般介于自然语言与程序设计语言之间，它具有自然般介于自然语言与程序设计语言之间，它具有自然语言灵活的特点，同时又接近于程序设计语言的描语言灵活的特点，同时又接近于程序设计语言的描述。述。算法描述语言所描述的流程，一般不能直接作为程算法描述语言所描述的流程，一般不能直接作为程序来使用，最后还需转换成
18、用某种程序设计语言所序来使用，最后还需转换成用某种程序设计语言所描述的程序。描述的程序。与程序设计语言的区别与程序设计语言的区别前者比较自由，不象后者那样受语法的约束，只要前者比较自由，不象后者那样受语法的约束，只要描述得人们能理解就行，而不必考虑计算机处理时描述得人们能理解就行，而不必考虑计算机处理时所要遵循的规定或其它一些细节。所要遵循的规定或其它一些细节。23C语言程序设计语言程序设计 温州理工学院温州理工学院 23用流程图表示算法用流程图表示算法流程的描述流程的描述在程序设计过程中，一般不可能在一开始就用某种程序设在程序设计过程中，一般不可能在一开始就用某种程序设计语言编制计算机程序，
19、而是先用某种简单、直观、灵活计语言编制计算机程序，而是先用某种简单、直观、灵活的描述工具来描述处理问题的流程。的描述工具来描述处理问题的流程。当方案确定以后，再将这样的流程转换成计算机程序，这当方案确定以后，再将这样的流程转换成计算机程序，这种转换往往是机械的，已经不涉及功能的重新设计或控制种转换往往是机械的，已经不涉及功能的重新设计或控制流程的变化，而只需考虑程序设计语言所规定的语法要求流程的变化，而只需考虑程序设计语言所规定的语法要求以及一细节问题。以及一细节问题。流程图流程图用一些约定的几何图形来描述算法。用某种图框表示某种用一些约定的几何图形来描述算法。用某种图框表示某种操作，用箭头表
20、示算法流程。操作，用箭头表示算法流程。24C语言程序设计语言程序设计 温州理工学院温州理工学院 24用流程图表示算法用流程图表示算法流程图（的符号及意义）美国标准化协会流程图（的符号及意义）美国标准化协会ANSI规定了规定了一些常用的流程图符号，已为世界各国程序工作者普一些常用的流程图符号，已为世界各国程序工作者普遍采用：遍采用：25C语言程序设计语言程序设计 温州理工学院温州理工学院 25用流程图表示算法用流程图表示算法起止框起止框表示算法的开始和结束。一般内部只写表示算法的开始和结束。一般内部只写“开始开始”或或“结束结束”。处理框处理框表示算法的某个处理步骤，一般内部常常填写赋值操作。表
21、示算法的某个处理步骤，一般内部常常填写赋值操作。输入输出框输入输出框表表示示算算法法请请求求输输入入需需要要的的数数据据或或算算法法将将某某些些结结果果输输出出。一一般内部常常填写般内部常常填写“输入输入”,“打印打印/显示显示”菱形框（判断框）菱形框（判断框）作作用用主主要要是是对对一一个个给给定定条条件件进进行行判判断断，根根据据给给定定的的条条件件是是否否成成立立来来决决定定如如何何执执行行其其后后的的操操作作。它它有有一一个个入入口口，两两个个出口。出口。26C语言程序设计语言程序设计 温州理工学院温州理工学院 26用流程图表示算法用流程图表示算法连接点连接点用用于于将将画画在在不不同
22、同地地方方的的流流程程线线连连接接起起来来。同同一一个个编编号号的的点点是是相相互互连连接接在在一一起起的的，实实际际上上同同一一编编号号的的点点是是同同一一个个点点，只只是是画画不不下下才才分分开开画画。使使用用连连接接点点，还还可可以以避避免免流流程程线线的的交叉或过长，使流程图更加清晰。交叉或过长，使流程图更加清晰。注释框注释框注注释释框框不不是是流流程程图图中中必必须须的的部部分分，不不反反映映流流程程和和操操作作，它它只只是是对对流流程程图图中中某某些些框框的的操操作作做做必必要要的的补补充充说说明明，以以帮帮助助阅读流程图的人更好地理解流程图的作用。阅读流程图的人更好地理解流程图的
23、作用。27C语言程序设计语言程序设计 温州理工学院温州理工学院 27用流程图表示算法用流程图表示算法例：例：求求5！该流程能获得正确的结该流程能获得正确的结果吗果吗？为什么？为什么？28C语言程序设计语言程序设计 温州理工学院温州理工学院 28传统流程图、三种基本结构和改进的流程图传统流程图、三种基本结构和改进的流程图传统流程图的缺点传统流程图的缺点传统流程图采用流程线指出各框的执行顺序，传统流程图采用流程线指出各框的执行顺序，对对流程线的使用没有严格限制流程线的使用没有严格限制。因此，使用者可以。因此，使用者可以不受限制地使流程转来转去，使流程图变得毫无不受限制地使流程转来转去，使流程图变得
24、毫无规律。规律。人们对这种流程图进行改进，规定几种基本的结人们对这种流程图进行改进，规定几种基本的结构，然后由这些基本结构按一定规律组成算法结构，然后由这些基本结构按一定规律组成算法结构，整个算法结构是构，整个算法结构是由上而下由上而下地将各个基本结构地将各个基本结构顺序排列起来。这样可以在一定程度上，提高算顺序排列起来。这样可以在一定程度上，提高算法的质量。法的质量。29C语言程序设计语言程序设计 温州理工学院温州理工学院 29三种基本结构和改进的流程图三种基本结构和改进的流程图三种基本结构的流程图三种基本结构的流程图30C语言程序设计语言程序设计 温州理工学院温州理工学院 30(1)顺序结
25、构程序设计顺序结构程序设计依次顺序执行程序语句依次顺序执行程序语句执行执行a块块执行执行b块块a块块b块块AB例如，令例如，令a、b的值的值分别为分别为5、10；a=5；b=10；31C语言程序设计语言程序设计 温州理工学院温州理工学院 31(2)判别选择结构程序设计判别选择结构程序设计首先判别条件，若条件满足，程序执行首先判别条件，若条件满足，程序执行a块，否则，执块，否则，执行行b块；块；举例，求举例，求a、b两个数中的最大值；两个数中的最大值；满足条件否满足条件否满足满足不满足不满足执行执行a块块执行执行b块块条件成立？条件成立？执行执行a块块执行执行b块块成立成立不成立不成立b max
26、？max=a；max=b；YN32C语言程序设计语言程序设计 温州理工学院温州理工学院 32(3)循环结构程序设计循环结构程序设计循环又分循环又分“当型循环当型循环”和和“直到型循环直到型循环”举例，求举例，求1100的累加和。的累加和。直到条件满足为止直到条件满足为止执行循环中的指令执行循环中的指令当条件满足时当条件满足时执行循环中指令执行循环中指令sum=sum+i;i=i+1;Ysum=0;Nib THENa maxELSEb maxIF cmax THEN c maxPRINT maxENDBEGININPUT a,b,ca maxIF maxb THEN b maxIF maxc T
27、HEN c maxPRINT maxEND43C语言程序设计语言程序设计 温州理工学院温州理工学院 43用计算机语言表示算法用计算机语言表示算法用某种程序设计语言编写的程序本质上也是问用某种程序设计语言编写的程序本质上也是问题处理方案的描述，并且是最终的描述。题处理方案的描述，并且是最终的描述。在一般的程序设计过程中，不提倡一开始就编在一般的程序设计过程中，不提倡一开始就编写程序，特别是对于大型的程序。写程序，特别是对于大型的程序。程序是程序设计的最终产品，需要经过每一步程序是程序设计的最终产品，需要经过每一步的细致加工才能得到，如果企图一开始就编写的细致加工才能得到，如果企图一开始就编写出程
28、序，往往会适得其反，达不到预想的结果出程序，往往会适得其反，达不到预想的结果。44C语言程序设计语言程序设计 温州理工学院温州理工学院 44结构化程序设计方法结构化程序设计方法结构化程序设计方法强调程序设计风格和程序结结构化程序设计方法强调程序设计风格和程序结构的规范化，提倡构的规范化，提倡 清晰的结构。清晰的结构。结构化程序设计方法的基本思路是：把一个复杂结构化程序设计方法的基本思路是：把一个复杂的问题的求解过程分阶段进行的问题的求解过程分阶段进行,每个阶段处理的问每个阶段处理的问题都控制在人们容易理解和处理的范围内。题都控制在人们容易理解和处理的范围内。为保证程序满足结构化程序设计，可以采
29、取如下为保证程序满足结构化程序设计，可以采取如下方法方法自顶向下自顶向下逐步细化逐步细化模块化设计模块化设计 结构化编码结构化编码45C语言程序设计语言程序设计 温州理工学院温州理工学院 45结构化程序设计方法结构化程序设计方法对于一个具体问题一般有两种方法对于一个具体问题一般有两种方法自顶向下、逐步细化自顶向下、逐步细化 自下而上、逐步积累自下而上、逐步积累例如：写文章、建造房屋例如：写文章、建造房屋提倡采用自顶向下、逐步细化的程序设计方法，提倡采用自顶向下、逐步细化的程序设计方法，其过程是将问题求解由抽象逐步具体化的过程。其过程是将问题求解由抽象逐步具体化的过程。注意：用这种方法便于验证算
30、法的正确性，在向下注意：用这种方法便于验证算法的正确性，在向下一层展开之前应仔细检查本层设计是否正确，只有一层展开之前应仔细检查本层设计是否正确，只有上一层是正确的才能向下细化。上一层是正确的才能向下细化。46C语言程序设计语言程序设计 温州理工学院温州理工学院 46用计算机语言表示算法用计算机语言表示算法例例:求求5！(用用C语言表示语言表示)47C语言程序设计语言程序设计 温州理工学院温州理工学院 47用计算机语言表示算法用计算机语言表示算法例例:求求 (用用C语言表示语言表示)48C语言程序设计语言程序设计 温州理工学院温州理工学院 48程序的灵魂算法程序的灵魂算法程序设计概述程序设计概
31、述算法算法怎样表示一个算法怎样表示一个算法小结小结参考书目及网络资源参考书目及网络资源讨论时间讨论时间49C语言程序设计语言程序设计 温州理工学院温州理工学院 49小结小结算法的概念算法的概念算法、语言、程序的关系算法、语言、程序的关系算法和程序都是用来表达解决问题的逻辑步骤，但算法独算法和程序都是用来表达解决问题的逻辑步骤，但算法独立于具体的计算机，与具体的程序设计语言无关，而程序立于具体的计算机，与具体的程序设计语言无关，而程序正好相反；程序是算法，但算法不一定是程序。正好相反；程序是算法，但算法不一定是程序。怎样表示一个算法怎样表示一个算法自然语言自然语言传统流程图传统流程图结构化流程图
32、（结构化流程图（N-SN-S流程图）流程图）伪代码伪代码计算机语言计算机语言50C语言程序设计语言程序设计 温州理工学院温州理工学院 50参考书目参考书目Donald E.Knuth(高德纳高德纳)，1974年年图灵奖获得者。图灵奖获得者。51C语言程序设计语言程序设计 温州理工学院温州理工学院 51参考书目参考书目52C语言程序设计语言程序设计 温州理工学院温州理工学院 52网络资源网络资源http:/(教学站点教学站点)http:/cpp.ga- 温州理工学院温州理工学院 53Questions-Discussion54C语言程序设计语言程序设计 温州理工学院温州理工学院 54作业提交作业
33、提交作业提交作业提交2.4、2.8实验报告提交实验报告提交http:/10.172.250.252:116155C语言程序设计语言程序设计 温州理工学院温州理工学院 55再再 见见15868725161376458575Algorithms+Data Structures=ProgramsCopyright 2021 Wenzhou University of Technology.All rights reserved.This presentation,slides,or hardcopy may NOT be used for short courses,industry seminars,or consulting purposes.The names of actual companies and products mentioned herein may be the trademarks of their respective owners.This presentation is for informational purposes only.C语言程序设计语言程序设计 The C Programming Language