程序的灵魂-算法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 程序的灵魂算法,算法的概念,简单算法举例,算法的特征,怎样表示一个算法,结构化程序设计方法,数据结构,算法,程序,程序,算法,数据结构,程序设计方法,语言工具和环境,目标,理解算法的作用以及特性,用自然语言表示算法,用流程图表示算法,用,c,语言表示算法,什么是程序,程序一词来自生活，通常指完成某些事务的一种既定方式和过程,在日常生活中，可以将程序看成对一系列动作的执行过程的描述,2.1,算法的概念,一个程序应包括：,对数据的描述：,在程序中要指定数据的类型和数据的组织形式，即数据结构（,data structure,）。,对操作的描述：,即操作步骤，也就是算法（,algorithm,）。,返回,2.1,算法的概念,一、算法的概念,广义地讲：算法是为完成一项任务所应当遵照的一步一步的规则的、精确的、无歧义的描述，它的总步数是有限的。,狭义地讲：算法是解决一个问题采取的方法和步骤的描述,二、算法的描述,1.,日常自然语言,2.,伪代码（自然语言与程序设计语言相结合）,3.,流程图,(,传统流程图、,NS,流程图）,4.,程序设计语言,三、简单的算法举例,例,2.1,交换两个变量的值,算法：,a=t, b=a, t=b,Nikiklaus,Wirth,提出的公式：,数据结构,+,算法,=,程序,再进一步：,程序,=,算法,+,数据结构,+,程序设计方法,+,语言工具和环境,2.1,算法的概念,做任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤，就称为算法。,计算机算法：计算机能够执行的算法。,计算机算法可分为两大类：,数值运算算法：求解数值；,非数值运算算法：事务管理领域。,算法,计算长方形的面积,问题：,1.,接收用户输入的长方形长度和宽度两个值；,2.,判断长度和宽度的值是否大于零；,3.,如果大于零，将长度和宽度两个值相乘得到面积，否则显示输入错误；,4.,显示面积。,算法,：解决问题的具体方法和步骤,八皇后问题,问题定义：,八皇后问题是一个著名而古老的问题。该问题要求在,88,的国际象棋棋盘上放置,8,个皇后，使得它们不能相互攻击，即,任意两个皇后不能处于同一行、同一列或者同一斜线上,。问有多少种放置的方案？,Q,Q,Q,Q,Q,Q,Q,Q,Q,i,j,Q,i,j,j:,行号,i:,列号,每行一个皇后,即每个,j,值对应一个,i,值。试探法,(1) j=1 i=1,Q,i,j,j:,行号,i:,列号,每行一个皇后,即每个,j,值对应一个,i,值。试探法,(1) j=1 i=1,(2) j=2 i=3,，,4,，,8 i=3,Q,Q,i,j,j:,行号,i:,列号,每行一个皇后,即每个,j,值对应一个,i,值。试探法,(1) j=1 i=1,(2) j=2 i=3,，,4,，,8 i=3,Q,(3) j=3 i=5,，,6,，,7,，,8 i=5,Q,Q,i,j,j:,行号,i:,列号,每行一个皇后,即每个,j,值对应一个,i,值。试探法,(1) j=1 i=1,(2) j=2 i=3,，,4,，,8 i=3,Q,(3) j=3 i=5,，,6,，,7,，,8 i=5,Q,(4) j=4 i=2,，,7,，,8 i=2,Q,Q,i,j,j:,行号,i:,列号,每行一个皇后,即每个,j,值对应一个,i,值。试探法,(1) j=1 i=1,(2) j=2 i=3,，,4,，,8 i=3,Q,(3) j=3 i=5,，,6,，,7,，,8 i=5,Q,(4) j=4 i=2,，,7,，,8 i=2,(5) j=5 i=4,，,8 i=4,Q,(6) j=6 i,无法选取回退一步,Q,i,j,j:,行号,i:,列号,每行一个皇后,即每个,j,值对应一个,i,值。试探法,(1) j=1 i=1,(2) j=2 i=3,，,4,，,8 i=3,Q,(3) j=3 i=5,，,6,，,7,，,8 i=5,Q,(4) j=4 i=2,，,7,，,8 i=2,Q,(6) j=6 i,无法选取回退一步,(5) j=5 i=4,，,8 i=8,Q,i,j,j:,行号,i:,列号,每行一个皇后,即每个,j,值对应一个,i,值。试探法,(1) j=1 i=1,(2) j=2 i=3,，,4,，,8 i=3,Q,(3) j=3 i=5,，,6,，,7,，,8 i=5,Q,(4) j=4 i=2,，,7,，,8 i=2,(5) j=5 i=4,，,8 i=4,Q,(6) j=6 i,无法选取回退一步,(5) j=5 i=4,，,8 i=8,(6) j=6 i,无法选取回退一步,(4) j=4 i=2,，,7,，,8 i=7,依次类推,Q,i,j,j:,行号,i:,列号,每行一个皇后,即每个,j,值对应一个,i,值。试探法,(1) j=1 i=1,(2) j=2 i=3,，,4,，,8 i=3,Q,(3) j=3 i=5,，,6,，,7,，,8 i=5,Q,Q,(4) j=4 i=2,，,7,，,8 i=7,依次类推,如何表示一具体方案,如何表示一具体方案？,int,queen8;,queenj, j=0,1,2,7;,表示第,j+1,行皇后放在第,queenj+1,列上,即（,queeni+1,j+1),放置一个皇后。,Q,Q,Q,Q,Q,Q,Q,Q,皇后放置问题,Q,Q,Q,Q,Q,Q,Q,Q,如何表示（,queeni+1,j+1),放置一个皇后以后，与该皇后同列、两个对角线不能再放置皇后？,int,b8,c15,d15;,bj, j=0,1,2,7;,表示第,j+1,列上已有皇后,如果第,i+1,行、第,j+1,列上放置一个皇后，则,bj,=1,第,j+1,列上已有皇后,ci+j,主对角线上已有皇后,di-j+7,从对角线已有皇后,算法描述,初始化棋盘,为第,1,个皇后选择合适位置,第,2,步定义成一个递归函数,try,void,try(int,i);,该函数作用是放置第,i+1,个（,i=0,1,，,7,）皇后,(,第,i+1,行皇后,放置）：,for(j,=0;j8;j+),/*,每个皇后都有,8,种可能位置*,/,2-1,如果不存在位置冲突，则,2-2,位置（,i+1,j+1,）上放置皇后,2-3,如果第,8,个皇后还没有放置好，则,继续放置下一个皇后,/*try(i+1),调用*,/,否则,输出当前解,2-4,释放位置（,i+1,j+1,）,#include ,int,queen8,b8,c15,d15;,int,queennum,=0; /*,当前解的序号*,/,/*,找到一个解后，输出当前解*,/,void print(),int,k;,queennum,+;,printf(%d:,queennum,);,for (k=0;k8;k+),printf(t,%,d,queenk,);,printf(n,);,程序源代码,void,try(int,i),int,j; /*,每个皇后都有,8,种可能位置*,/,for (j=0;j8;j+), if (,bj,=0) &(,ci+j,=0)& (di-j+7=0) /*,判断位置是否冲突*,/,queeni,=j; /*,摆放皇后*,/,bj,=1; /*,宣布占领第,j+1,行*,/,ci+j,=1; /*,占领两个对角线*,/,di-j+7=1;,if (i7),try(i+1); /*8,个皇后没有摆完，递归摆放下一皇后*,/,else,print(); /*,完成任务，打印结果*,/,bj,=0; /*,回溯*,/,ci+j,=0;,di-j+7=0;,int,main(),int,k;/*,数据初始化*,/,for( k=0;k15;k+),if(k,8),bk,=0;,ck,=0;,dk,=0;,try(0);/*,从第,1,个皇后开始放置*,/,return 0;,主函数,一、算法,(,最短路径问题,),：,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,求从,A,到,E,的最短路径,一、算法,(,最短路径问题,),：,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,5,(E)=0,一、算法,(,最短路径问题,),：,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,1,)=5,f,5,(E)=0,一、算法,(,最短路径问题,),：,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,4,(D,1,)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,1,)=8,f,4,(D,1,)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,2,)=7,f,4,(D,1,)=5,f,3,(C,1,)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,3,(C,1,)=8,f,3,(C,2,)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,1,)=20,f,3,(C,2,)=7,f,3,(C,1,)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,2,)=14,f,3,(C,2,)=7,f,3,(C,1,)=8,f,2,(B,1,)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,2,(B,1,)=21,f,2,(B,2,)=14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14,f,2,(B,1,)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C,1,C,3,D,1,A,B,1,B,3,B,2,D,2,E,C,2,f,4,(D,2,)=2,f,5,(E)=0,f,3,(C,3,)=12,f,4,(D,1,)=5,f,2,(B,3,)=19,f,3,(C,2,)=7,f,3,(C,1,)=8,f,1,(A)=19,f,2,(B,2,)=14,f,2,(B,1,)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A,（,A,，,B,2,）,B,2,（,B,2,，,C,1,）,C,1,（,C,1,，,D,1,）,D,1,（,D,1,，,E,）,E,从,A,到,E,的最短路径为,19,，路线为,AB,2,C,1,D,1,E,一、算法,(,资源分配问题,),4,万元资金，如何分配给,A,、,B,、,C,三个项目，使总效益最大,4,万元,2,万元,1,万元,0,万元,4,万元,2,万元,1,万元,0,万元,4,万元,2,万元,1,万元,0,万元,4,万元,x,1,A,项目,x,2,B,项目,x,3,C,项目,x,4,3,万元,3,万元,3,万元,0,f,2.2,简单算法举例,例,2.2,求,12345,。,最原始方法：,步骤,1,：先求,12,，得到结果,2,。,步骤,2,：将步骤,1,得到的乘积,2,乘以,3,，得到结果,6,。,步骤,3,：将,6,再乘以,4,，得,24,。,步骤,4,：将,24,再乘以,5,，得,120,。,这样的算法虽然正确，但太繁。,返回,改进的算法：,S1:,使,t=1,S2:,使,i=2,S3:,使,ti,乘积仍然放在在变量,t,中，可表示为,tit,S4:,使,i,的值,+1,，即,i+1i,S5:,如果,i5,返回重新执行步骤,S3,以及其后的,S4,和,S5,；,否则，算法结束。,如果计算,100,！只需将,S5:,若,i5,改成,i100,即可。,如果该求,1357911,，算法也只需做很少的改动：,S1: 1t,S2: 3i,S3: tit,S4: i+2t,S5:,若,i11,返回,S3,，,否则，结束。,该算法不仅正确，而且是计算机较好的算法，因为计算机是高速运算的自动机器，实现循环轻而易举。,例,2.3,有,50,个学生，要求将他们之中成绩在,80,分以上者打印出来。,如果，,n,表示学生学号，,n,i,表示第,i,个学生学号；,g,表示学生成绩，,g,i,表示第,i,个学生成绩，则算法可表示如下：,S1: 1i,S2:,如果,g,i,80,，,则打印,n,i,和,g,i,，,否则不打印,S3: i+1i,S4:,若,i50,返回,S2,，,否则，结束。,例,2.4,判定,2000 2500,年中的每一年是否闰年，将结果输出。,闰年的条件：,能被,4,整除，但不能被,100,整除的年份；,能被,100,整除，又能被,400,整除的年份；,设,y,为被检测的年份，则算法可表示如下：,S1: 2000y,S2:,若,y,不能被,4,整除，则输出,y“,不是闰年”，然后转到,S6,S3:,若,y,能被,4,整除，不能被,100,整除，则输出,y“,是闰年”，然后转到,S6,S4:,若,y,能被,100,整除，又能被,400,整除，输出,y“,是闰年” 否则输出,y“,不是闰年”，然后转到,S6,S5:,输出,y“,不是闰年”。,S6:y+1y,S7:,当,y2500,时,返回,S2,继续执行，否则，结束。,例,2.5,求,算法可表示如下：,S1: sigh=1,S2: sum=1,S3:,deno,=2,S4: sigh=(-1)sigh,S5: term= sigh(1/deno ),S6: term=,sum+term,S7:,deno,=,deno,+1,S8:,若,deno100,，返回,S4,；否则，结束。,例,2.6,对一个大于或等于,3,的正整数，判断它是不是一个素数。,算法可表示如下：,S1:,输入,n,的值,S2: i=2,S3: n,被,i,除，得余数,r,S4:,如果,r=0,，表示,n,能被,i,整除，则打印,n“,不是素数”，算法结束；否则执行,S5,S5: i+1i,S6:,如果,in-1,，返回,S3,；否则打印,n“,是素数”；然后算法结束。,S1:,输入,n,的值,S2: i=2,S3: n,被,i,除，得余数,r,S4:,如果,r=0,，表示,n,能被,i,整除，则打印,n“,不是素数”，算法结束；否则执行,S5,S5: i+1i,S6:,如果,i,，返回,S3,；否则打印,n“,是素数”,;,然后算法结束。,改进,算法可表示如下：,2.3,算法的特性,有穷性：一个算法应包含有限的操作步骤而不能是无限的。,确定性：算法中每一个步骤应当是确定的，而不能应当是含糊的、模棱两可的。,有零个或多个输入。,有一个或多个输出。,有效性：算法中每一个步骤应当能有效地执行，并得到确定的结果。,返回,2.4,怎样表示一个算法,一、用自然语言表示算法,二、传统流程图,处理框,起止框,I/O框,判断框,流程线,连接点,1,、传统流程图中的基本符号,返回,2,、三种基本结构的表示,（,1,）顺序结构,条件,语句,1,语句,2,Y,N,语句,1,语句,2,（,2,）选择结构,条件,语句,条件,语句,（,3,）循环结构,a),当型,循环,b),直到循环,Y,N,Y,N,三种基本结构的特点：,（,1,）只有一个入口,（,2,）只有一个出口,（,3,）不存在死语句,（,4,）不存在死循环,例： 画出从,10,个数中选出最大的数的流程图,由以上三种基本结构组成的算法结构,可以解决任何复杂的问题。,由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和跳转。,N=Max,Max =A,输入,A,开始,再输入给,A,N=N+1,打印,Max,结束,Y,N,N,Y,四、,NS,流程图,将,全部算法写在一个矩形框内，在矩形内还可包含其它从属于它的框,三种,基本结构的,NS,图表示：,语句,A,语句,B,语句,A,语句,B,条件,Y,N,1,、顺序结构,2,、选择结构,语句组,（,3,）循环结构,a),当型,循环,b),直到循环,当条件成立,语句组,直到当条件成立,例： 画出从,10,个数中选出最大的数的,NS,流程图,输入,A,当N=10,Max =A,N=N+1,打印,Max,输入,A,NS,流程图,传统流程图,N=Max,Max =A,输入,A,开始,再输入给,A,N=N+1,打印,Max,结束,Y,N,N,Y,A=Max,Y,N,N-S,图比文字描述直观、形象、易于理解；,比流程图紧凑易画，尤其是它废除了流程线，整个算法结构是由各个接纳结构按顺序组成的。,N-S,图中的上下顺序就是执行时的顺序，即图中位置在上面的先执行，位置在下面的后执行。,写算法和看算法只需从上到下进行就可以了，十分方便。,五、用计算机语言表示算法,#,include,main( ),int,max,n,a;,n=1;,scanf(“%d”,&a,);,max=a;,while,(n=10),scanf(“%d”,&a,);,if (maxy,while yy,END,（算法结束）,伪代码书写格式比较自由，可以随手写下去，容易表达出设计者的思想。,用伪代码写的算法容易修改，容易写出结构化的算法。,但是，用伪代码写算法不如流程图直观，可能出现逻辑上的错误。,2.4.6,用计算机语言表示算法,我们的任务是用计算机解题，就是用计算机实现算法；,用计算机语言表示算法必须严格遵循所用语言的语法规则。,例,2.11,求,12345,用,C,语言表示。,main(),int,i,t,;,t=1;,i=2;,while,(i,=5),t=t*i;,i=i+1;,printf(“%d”,t,);,例,2.12,求级数的值。,main(),int,sigh=1;,float,deno,=2.0,sum=1.0,term;,while,(deno,=100), sigh= -sigh;,term= sigh/,deno,;,sum=,sum+term,;,deno,=deno+1;,printf(“%f”,sum,);,2.5,结构化程序设计方法,一、用计算机解决问题的过程,提出、分析问题,确定算法模型,设计算法,编写程序,调试程序,分析输出结果,正确合理,结束,不正确,返回,二、结构化程序设计思想,自顶,向下、逐步细化、模块化,自顶,向下：先从全局、整体设计,逐步细化：将一个问题分解成几个较小的问题解决,模块化： 将一个大任务分解成若干个较小的部分，,每 个部分承担一定功能，称为“功能模块”,例,2.13,给,100,个整数，打印输出其中的素数,输入,100,个数存入,x,1,，,x,2,x,100,打印,x,1,.x,100,中,不等于,0,的数,S1,NS,流程图,让,x,1,x,2,x,100,中的非素变为,0,S3,S2,输入,x,i,当i=100,i=i+1,i=1,S1,细化,x,i,0,当i=100,i=i+1,i=1,Y,N,打印,x,i,S3,细化,输入,100,个数存入,X,1,，,x,2,x,100,打印,1,.x,100,中不等于,0,的数,S1,NS,流程图,让,x,1,，,x,100,中的非素变为,0,S3,S2,判断,x,i,是否是素数，若不是则将,x,i,=0,当i=100,i=i+1,i=1,S2,细化,r=0,r,sqrt(x,i,),S21,细化,输入,x,i,当i=100,i=i+1,i=1,当i,sqrt(x,i,),i=i+1,x,i,0,当i=100,i=i+1,i=1,Y,N,打印,x,i,输入,100,个数存入,X,1,，,x,2,x,100,打印,x,1,.x,100,中不等于,0,的数,让,x,1,，,x,100,中的非素变为,0,细化后的流程图,从,上面的例子中可以看出，结构化程序设计方法是解决复杂问题的有效的方法。,总结,算法有穷性、确定性、有效性,算法有零个或多个输入,有一个或多个输出,算法的表示,