,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,Saturday,February 2,2019,#,目录,第一章,绪论,第二章,算法与流程图,第三章,数据类型、运算符和表达式,第四章,程序的控制结构,第五章,函数,第六章,数组,第七章,指针,第八章,结构体,第九章,文件操作,第二章,算法与流程图,1,、程序数据结构算法,2,、简单算法举例,3,、算法特性,4,、算法的自然语言表示,5,、算法的流程图表示,6,、算法的伪代码表示,1,、程序数据结构算,法,Niklaus Wirth,designer of Pascal,Wirth,Niklaus(1976)(in English).Algorithms+Data Structures=Program.Prentice Hall.0130224189.ISBN 978-0130224187,程序：为计算机解题编制的一组指令集,算法：处理问题的策略,数据结构：处理信息的表示,Turing Award,1984,2,、简单算法举例,求和：,1+1/2+1/3+1/4+1/5+1/100,蛮力法：,S1,:,先计算,1/2=0.5,，再与,1,相加得,1.5,S2,:,计算,1/3=0.33333,，与,1.5,相加得,1.83333,S3,:,计算,1/4=0.25,，与,1.83333,相加得,2.08333,S99,:,计算,1/100=0.01,，与,5.177378,相加得,5.187378,。,2,、简单算法举例,求和：,1+1/2+1/3+1/4+1/5+1/100,改进的算法：,S1,:,初始化,sum=0,i=1,S2,:,如果,i,100,，执行,S3,；否则执行,S5,S3,:sum=sum+1/i,S4,:i=i+1,，跳转到,S2,S5,:,输出,sum,，算法结束,2,、简单算法举例,从,3,个数,A,、,B,、,C,中找出最大的数。,算法,1,：,S1,:,如果,AB,，执行,S2,；否则执行,S3,S2,:,如果,AC,，执行,S4,；否则执行,S6,S3,:,如果,BC,，执行,S5,；否则执行,S6,S4,:,输出,A,S5,:,输出,B,S6,:,输出,C,2,、简单算法举例,从,3,个数,A,、,B,、,C,中找出最大的数。,算法,2,：,S1,:,初始化,max=A,S2,:,如果,AB,，执行,S3,；否则,max=B,，执行,S3,S3,:,如果,maxC,，执行,S4,；否则,max=C,，执行,S4,S4,:,输出,max,算法的五个特点：,有输入,(Input),：,零个,或多个输入。,有输出,(Output),：,一个,或多个输出。,有穷性,(Finiteness),：对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。,可行性,(,Effectiveness,),：所有操作都可通过已经实现的,基本操作,运算有限次来实现。,确定性,(,Definiteness,),：算法中每一步的描述都,无二义性,，只要输入相同，初始状态相同，无论执行多少遍，结果都应该相同。,Turing Award,1974,3,、算法的特性,“,好,”算法的特点：,正确性,(Correctness),：满足问题的需求。,易读性,(Readability),：便于理解、测试和修改。,健壮性,(Robustness),：输入非法数据时，算法能做出适当处理，不会产生难以预料的结果。,时空效率,(Efficiency),：执行时间短，低存储。,3,、算法的特性,4,、算法的自然语言表示,优点,通俗易懂,缺点,文字冗长、不直观,不适合描述分支循环结构,从,3,个数,A,、,B,、,C,中找出最大的数。,S1,:,如果,AB,，执行,S2,；否则执行,S3,S2,:,如果,AC,，执行,S4,；否则执行,S6,S3,:,如果,BC,，执行,S5,；否则执行,S6,S4,:,输出,A,S5,:,输出,B,S6,:,输出,C,5,、,算法的流程图表,示,从,3,个数,A,、,B,、,C,中找出最大的数。,开始,结束,输入,A,B,C,AB,AC,CB,输出,B,输出,C,输出,A,是,是,是,否,否,否,5.1,流程图基本单元,起止框,输入,/,输出框,处理框,判断框,连结点,流程线,5.2,流程图绘制例,输入,50,个学生的姓名和成绩，输出不及格学生的名单。,开始,结束,i=1,输入,n,i,s,i,i50,是,i=1,s,i,50,是,i=i+1,否,是,否,否,5.2,流程图绘制例,输入,50,个学生的姓名和成绩，输出不及格学生的名单。,开始,结束,i=1,输入,n,i,s,i,i50,是,i=1,s,i,50,是,i=i+1,否,是,否,否,1,1,5.3,三种基本结构对应流程图,（,1,）顺序结构,A,B,5.3,三种基本结构对应流程图,（,2,）选择结构,A,B,p,是,否,5.3,三种基本结构对应流程图,（,3,）循环结构：当型,while(p)B;,B,p,是,否,5.3,三种基本结构对应流程图,（,3,）循环结构：直到型,do B;while(p);,B,p,是,否,5.4,练习,（,1,）用流程图表示判断闰年的算法。,（,2,）用流程图表示判断一个正整数是否是素数的算法。,5.5,用伪代码表示算法,用介于自然语言和计算机语言之间的文字和符号表示算法,无固定严格的语法规则,beginend,ifelse,dowhile,while,=,，,=,input,print,例如：求和算法的伪代码,1+1/2+1/3+1/4+1/5+1/100,begin,sum=0,i=1,while(i 100),begin,sum=sum+1/i,i=i+1,end,print sum,end,本章小结,“好”算法的特点,算法的流程图表示,