信息学奥赛基础试题解析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,试题解析,【,题目描述,】,五位好朋友相聚。第一位朋友带来了很多糖块赠送给各位朋友，使每人的糖块在各自原有的基础上,翻了一倍,；接着第二位好友也同样向每人赠送糖块，同样使每人的糖块在各自原有的数量基础上翻了一倍；第三、第四、第五位好友都照此方法操作。经过这样的赠送之后，每人的糖块恰好都为,n(n,=32),块。问各位好友原有的糖块数分别是多少,?,【,试题,1:,分糖果,】,【,题目分析,】,由题意可知，第五个人分完以后，每个人糖块数都是,32,，并且其它四个人都是在原来基础上翻了一倍，故可以推算出第五个人分之前每个人的糖块数，依次倒推，可得解也。,32,32,32,32,32,第五个人分之后,16,16,16,16,96,第五个人分之前,12345,888,88,48,第四个人分之前,44,84,4424,第三个人分之前,2,82,422212,第二个人分之前,81,4121116,第一个人分之前,【,算法设计,】,开始,num1.5:=32n:=5,n=1?,i:=1sum:=0,i=5?,numi,:=,numi,div 2,sum:=sum+,numi,in?,i:=i+1,n:=n-1,numn,:=,numn+sum,结束,输出,num1.5,Y,N,Y,Y,N,N,外循环,内循环,【,例程,】,program,ex1;,var,sum,i,n:integer,;,num:array1.5 of integer;,begin,for n:=1 to 5 do,numn,:=32;,初始化,for n:=5,downto,1 do ,处理五个人分发情况,begin,sum:=0;,累加器清零,for i:=1 to 5 do ,求四个接收者,if in then,begin,numi,:=,numi,div 2;,sum:=,sum+numi,;,求分发者分发出总量,end;,numn,:=,numn+sum,;,求分发者分发前总量,for i:=1 to 5 do write(numi:3,);,writeln,;,end;,end.,【,题目描述,】,某幼儿园里，有,5,个小朋友编号为：,1,、,2,、,3,、,4,、,5,，他们按自己的编号顺序围坐在一张圆桌旁。他们身上都有若干个糖果，现在他们做一个分糖果游戏。从,1,号小朋友开始，将他的糖果均分,3,份,(,如果有多余的，则他将多余的糖果吃掉），自己留,1,份，其余,2,份分给他的相邻的两个小朋友。接着,2,号、,3,号、,4,号、,5,号小朋友也这样做。问一轮后，每个小朋友手上分别有多少糖果,(0=,糖果数,=1000,）？,【,试题,2:,分糖果,】,【,题目分析,】,由题意可知，对于每个人的操作都是先平分三份，自己留一份，再将其它两份分给相邻的两个小朋友，所以从一号到五号顺序处理即可。,【,算法设计,】,开始,Readln(a,b,c,d,e,);,a=a div 3;e=,e+a;b,=,b+a,;,b=b div 3;a=,a+b;c,=,c+b,;,c=c div 3;b=,b+c;d,=,d+c,;,d=d div 3;c=,c+d;e,=,e+d,;,e=e div 3;a=,a+e;d,=,d+e,;,Writeln(a,b,c,d,e);,结束,【,题目描述,】,要求用户输入一个小写字母字符，求出该字母字符的前驱和后继字符，例如，,c,字符的前驱和后继分别是,b,和,d,，,a,字符的前驱和后继分别是,z,和,b,，,z,字符的前驱和后继分别是,y,和,a,。,【,试题,3:,小写字母转盘,】,a,b,c,d,e,f,z,y,x,.,.,.,【,题目分析,】,求前驱字母并不是简单地减,1,，如,:a,的前驱是,z,就不能通过减,1,来实现。在没有学条件控制之前，我们可以利用取余的特性，即任何一个整数除以,26(26,个字母,),的余数只能在,0,25,之间。我们可以以,z,为参考点，首先求出输入的字符,ch,(,假设是,w,),与,z,之间的字符偏移数,n=,z-ch,=,z-w,=3,，而,(n+1)mod 26=4,则是,ch,(,字母,w,),的前驱字母相对于,z,的偏移数，,z-(n+1)mod 26=122-4=118(,即字母,v,),就是,ch,(,字母,w,),的前驱字母。如下图,:,a b c d e f g h i j k l m n o p q r s t u,v,w,x,y z,前驱参考点,前驱偏移数,4,ch,求一个字母的后继也不是简单地加,1,就行，比如，,z,的后继是,a,就不能通过加,1,来实现。此时，可以,a,为参考点，首先求出输入的字符,ch,(,假设是,w),与,a,之间的字符偏移数,n=,ch,-a=w-a=22,，而,(n+1)mod 26=23,则是,ch,(,字母,w),的后继字母相对于,a,的偏移数，,a+(n+1)mod 26=97+23=120(,即字母,x),就是,ch,(,字母,w),的后继字母。,a b c d e f g h i j k l m n o p q r s t u,v,w,x,y z,后继参考点,后继偏移数,23,ch,【,问题描述,】,输入两个数，按先后顺序分别代表,x,、,y,坐标，判断这两个数确定的点是否在给定的圆环内。圆环为圆心为,(0,0),的同心圆。,【,输入格式,】,输入由两行组成。,第一行有两个数，分别表示横坐标和纵坐标。,第二行有两个数，表示圆环的下界和上界,(,上下界为平方数，如：,1 9,，分别表示半径为,1,的圆和半径为,3,的圆组成的圆环,),。,【,输出格式,】,输出文件包含一行，,TRUE,或者,FALSE,，分别表示在与不在圆环内。,【,试题,:,确定点位置,】,【,题目分析,】,o,x,y,x,y,A,|OA|*|OA|=,x,*,x,+,y,*,y,【,试题,:,约瑟夫环,】,【,问题描述,】,用循环线性链表解决约瑟夫问题。,【,题目分析,】,Order,1,2,3,4,5,Next,2,3,4,5,1,人员编号,指针：指向下一人,1,5,4,3,2,Next,5,4,3,2,1,Order,3,2/0,5,2/0,3,1,3,2/0,5,1,3,1,1,5,P,1,2/0,1,0,C,3,0,0,0,0,0,0,5,3,3,0,0,program,joseph(input,output,);,const,num=5;,type,node=record,order:integer,;,next:integer,;,end;,var,circle:array1.num of node;,p,c,i,n,m:integer,;,begin,m:=2;,for i:=1 to num do,begin,circlei.order,:=i;,circlei.next,:=i+1;,end;,p:=i;c:=0;circlep.next:=1;,while,circlep.next,p do,begin,c:=c+1;,if cm then,p:=,circlep.next,else,begin,i:=,circlep.next,;,circlep.next,:=,circlecirclep.next.next,;,circlei.order,:=0;,circlei.next,:=0;,c:=0;,end;,end;,end.,【,题目描述,】,数位求和,【,试题,:】,n,r,(n mod 10),123456,6,12345,5,1234,4,123,3,12,2,1,1,【,题目描述,】,填充魔方阵,【,试题,:,魔方阵,】,何谓魔方阵？,4 9 2,3 5 7,8 1 6,定义：由,n*n,个数字所组成的,n,阶方阵，具有各对角线，各横列与纵行的数字和都相等的性质，称为魔方阵。而这个相等的和称为魔术数字。若填入的数字是从,1,到,n*n,，称此种魔方阵为,n,阶正规魔方阵。,1.n=2k+1(,奇数时,)(k=1,2,3,4,5.),(1)1,放在第一行的中间位置上；,(2),下一个数放在当前位置的上一行、下一列；,(3),若当前位置是第一行，下一个数放在最后一行；若当前位置是最后一列，下一个数放在第一列；,(4),若下一个数要放的位置上已经有了数字，则下一个数字放在当前位置的下一行，相同列。,根据此规则填充的,3,阶魔方阵如下：,8,1,6,3,5,7,4,9,2,2.n=4k,(4,的整数倍时,)(n=4,8,12,16.k=1,2,3,4,5.),先说明一个定义：,互补：如果两个数的和，等于幻方最大数和最小数的和，即,n*n+1,，称为互补。,先看看,4,阶幻方的填法：将数字从左到右、从上到下按顺序填写：,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,这个方阵的对角线，已经用红色标出。将对角线上的数字，换成与它互补的数字。,这里，,n*n+1=4*4+1=17,；,把,1,换成,17-1=16,；把,6,换成,17-6=11,；把,11,换成,17-11=6,换完后就是一个四阶幻方。,16,2,3,13,5,11,10,8,9,7,6,12,4,14,15,1,对于,n=4k,阶幻方，我们先把数字按顺序填写。填好后，把它划分成,k*k,个,4*4,的方阵。因为,n,是,4,的倍数，一定能用,4*4,的小方阵分割。然后如同构造,4,阶幻方那样，把对角线上的数字换成与它互补的数字，就构成,n,阶幻方。,下面以,8,阶幻方的构造法为例：,(1),先把数字按顺序填。然后，按,4*4,把它分割成,2*2,个小方阵；,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,(2),每个小方阵对角线上的数字，换成和它互补的数。,64,2,3,61,60,6,7,57,9,55,54,12,13,51,50,16,17,47,46,20,21,43,42,24,40,26,27,37,36,30,31,33,32,34,35,29,28,38,39,25,41,23,22,44,45,19,18,48,49,15,14,52,53,11,10,56,8,58,59,5,4,62,63,1,3.n=4k+2(n,为偶数，且不能被,4,整除,)(n=6,，,10,，,14,，,18,，,22,;k=1,，,2,，,3,，,4,，,5,),这是三种里面最复杂的幻方。,以,n=10,为例。这时，,k=2,A,B,C,D,(1),把方阵分为,A,，,B,，,C,，,D,四个象限，这样每一个象限肯定是奇数阶。然后依次在,A,象限，,D,象限，,B,象限，,C,象限按奇数阶幻方的构造法填充。,17,24,1,8,15,67,74,51,58,65,23,5,7,14,16,73,55,57,64,66,4,6,13,20,22,54,56,63,70,72,10,12,19,21,3,60,62,69,71,53,11,18,25,2,9,61,68,75,52,59,92,99,76,83,90,42,49,26,33,40,98,80,82,89,91,48,30,32,39,41,79,81,88,95,97,29,31,38,45,47,85,87,94,96,78,35,37,44,46,28,86,93,100,77,84,36,43,50,27,34,17,24,1,8,15,67,74,51,58,65,23,5,7,14,16,73,55,57,64,66,4,6,13,20,22,54,56,63,70,72,10,12,19,21,3,60,62,69,71,53,11,18,25,2,9,61,68,75,52,59,92,99,76,83,90,42,49,26,33,40,98,80,82,89,91,48,30,32,39,41,79,81,88,95,97,29,31,38,45,47,85,87,94,96,78,35,37,44,46,28,86,93,100,77,84,36,43,50,27,34,(2),在,A,象限从中间格开始，按自左向右的方向，标记,k,个格。,A,象限的其它行则标记最左边的,k,个格。,(3),将,A,象限标记的格子和,C,象限中对应位置格子中的数字互换。,92,99,1,8,15,67,74,51,58,65,98,80,7,14,16,73,55,57,64,66,4,6,88,95,22,54,56,63,70,72,85,87,19,21,3,60,62,69,71,53,86,93,25,2,9,61,68,75,52,59,17,24,76,83,90,42,49,26,33,40,23,5,82,89,91,48,30,32,39,41,79,81,13,20,97,29,31,38,45,47,10,12,94,96,78,35,37,44,46,28,11,18,100,77,84,36,43,50,27,34,(4),在,B,象限从任一行的中间格，自右向左，标记出,k-1,列。,92,99,1,8,15,67,74,51,58,65,98,80,7,14,16,73,55,57,64,66,4,6,88,95,22,54,56,63,70,72,85,87,19,21,3,60,62,69,71,53,86,93,25,2,9,61,68,75,52,59,17,24,76,83,90,42,49,26,33,40,23,5,82,89,91,48,30,32,39,41,79,81,13,20,97,29,31,38,45,47,10,12,94,96,78,35,37,44,46,28,11,18,100,77,84,36,43,50,27,34,(5),将,B,象限标记的这些数，和,D,象限相对位置上的数进行交换，即可完成填充。,92,99,1,8,15,67,74,26,58,65,98,80,7,14,16,73,55,32,64,66,4,6,88,95,22,54,56,38,70,72,85,87,19,21,3,60,62,44,71,53,86,93,25,2,9,61,68,50,52,59,17,24,76,83,90,42,49,51,33,40,23,5,82,89,91,48,30,57,39,41,79,81,13,20,97,29,31,63,45,47,10,12,94,96,78,35,37,69,46,28,11,18,100,77,84,36,43,75,27,34,【,题目描述,】,现有一批战利品，数量为,n,（,1=n=20,），编号为,1n,。每一个战利品都有一定的体积,v,（,1=v=100,）和价值,p,（,1=p=1000,），假定你有一个总容量为,s,的背包，你可以在不超过背包容量的前提下随意从战利品中挑选,m,件战利品。编程序计算出能使自己所选战利品总价值最大的选择方案。,【,输入输出样例,】,输入：,12 4,3 4,4 5,5 7,8 10,输出：,1 2 3,16,【,题目描述,】,金明今天很开心，因为今天是他的生日，妈妈给了,N,元钱。今天一早，金明就开始做预算了，他从因特网上查到了,M,件物品的价格（每件物品的价格都不相同）。他希望从中购买一些物品能恰好将,N,元钱花完。请你帮助计算一下共有多少种不同的购物方案。,【,输入文件,】,第一行两个正整数,N,M,。第二行,M,个空格隔开的互不相等的正整数，表示,M,中物品的价格。,【,输出文件,】,一个正整数，为不同的购物方案数（所有数据都不超整形范围）。,【,试题,:,购物,(,shopping.pas/c/cpp,)】,样例：,输入文件：,shopping.in,5 6,1 2 3 4 5 6,输出文件：,shopping.out,3,样例说明：共,3,种方案：,（,1,）,a(1)+a(4)=1+4=5,（,2,）,a(2)=a(3)=2+3=5,（,3,）,a(5)=5,方法,1,：递归算法,Procedure,try(s,i,);,在已经花完,s,元的前提下去尝试购买第,i,件物品,Var,k,t:integer,；,Begin,如果物品编号没有越界，那么,for k:=1 down to 0 do,面对每种物品有两种尝试选择方案：买,/,不买,begin,t:=,s+costi,*k,尝试一种方案,;,如果没有超支，那么,如果刚好花完，说明产生一种方案，计数,否则尝试购买下一种物品,try(t,i+1);,end;,End;,K-1;t1;bt,10;bt,21;,初始状态,k k+1;,尝试下一条规则,s:=bt,1+costbt,2*k;,尝试一种方案,是否超支,?,false,true,t t+1;,bt,1 s;,刚好花完？,true,false,计数,;,k-1;,继续下一步,While (k1)do K0/1,，买,/,不买,Until t=0;,bt,2 bt-1,2+1;,bt,3 k;,t t-1;k bt,3;,回溯,:,指针减,1,，往回退并恢复数据,非递归算法流程图,还有物品吗,?,true,false,已经花费,物品编号,购买方案,6,5,4,3,2,1,样例：,输入文件：,shopping.in,5 6,1 2 3 4 5 6,输出文件：,shopping.out,3,尝试过程中需要保存那些数据？,1,、在尝试购买某物品前已经花费了多少钱？,2,、尝试到了哪一个物品？,3,、对某物品可以尝试的方案是否都已尝试完毕？,t,已经花费,物品编号,购买方案,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,1,-10,0,t,已经花费,物品编号,购买方案,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,2,-10,0,2,0,0,t,已经花费,物品编号,购买方案,0,6,0,0,5,0,0,4,0,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,6,-10,0,没有物品，所以实施方案,1,，尝试购买,6,号物品。,t,已经花费,物品编号,购买方案,0,6,0,0,5,0,0,4,0,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,6,1,6,无物品，实施方案,1,后，超支，下一步：回溯。,Dec(t,);,恢复,k;,尝试下一方案（,k+1,）,;,t,已经花费,物品编号,购买方案,0,6,0,0,5,0,0,4,0,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,5,1,5,得到一种购物方案，,Inc(,购物方案,);,物品,5,尝试完毕，下一步,回溯,;,t,已经花费,物品编号,购买方案,0,6,0,0,5,0,0,4,0,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,4,1,4,无超支，还有物品，保存现场，继续尝试！,t,已经花费,物品编号,购买方案,0,6,0,4,5,0,0,4,1,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,5,-10,4,无超支，还有物品，保存现场，继续尝试！,t,已经花费,物品编号,购买方案,4,6,0,4,5,0,0,4,1,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,6,-10,4,无超支，无物品，采取方案,1,，尝试！,t,已经花费,物品编号,购买方案,4,6,0,4,5,0,0,4,1,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,6,01,10,超支，所有方案尝试完毕，回溯！,t,已经花费,物品编号,购买方案,4,6,0,4,5,0,0,4,1,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,5,01,9,超支，所有方案尝试完毕，回溯！,t,已经花费,物品编号,购买方案,4,6,0,4,5,0,0,4,1,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,4,1,有物品，但所有方案尝试完毕，回溯！,t,已经花费,物品编号,购买方案,4,6,0,4,5,0,0,4,1,0,3,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,3,01,3,无超支，还有物品，保存现场，继续尝试！,t,已经花费,物品编号,购买方案,0,0,0,0,0,0,3,0,0,0,3,1,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,4,-10,3,往前的尝试均不能找到购物方案，回溯！,t,已经花费,物品编号,购买方案,0,0,0,0,0,0,3,0,0,0,3,1,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,3,1,本物品所有方案均已尝试，回溯！,t,已经花费,物品编号,购买方案,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,2,01,未超支，有物品，保存现场，继续尝试！,2,t,已经花费,物品编号,购买方案,0,0,0,0,0,0,0,0,0,2,3,0,0,2,1,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,3,-10,在,4,，,5,，,6,物品尝试中均得不到购物方案，因此最后回到,3,号物品，尝试下一方案！,2,t,已经花费,物品编号,购买方案,0,0,0,0,0,0,0,0,0,2,3,0,0,2,1,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,3,01,得到一种购物方案，,Inc(,购物方案,),，回溯！,5,t,已经花费,物品编号,购买方案,0,0,0,0,0,0,0,0,0,2,3,0,0,2,1,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,2,1,物品,2,尝试完毕，回溯！,t,已经花费,物品编号,购买方案,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,1,01,保存现场，继续尝试！,1,t,已经花费,物品编号,购买方案,0,0,0,0,0,0,0,0,0,0,0,0,1,2,0,0,1,1,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,2,-10,在已花,1,元基础上从,2,物品开始尝试，会得到最后一种购物方案（,1,，,4,），最终退回到物品,1,！,t,已经花费,物品编号,购买方案,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,物品,1,2,3,4,5,6,价格,1,2,3,4,5,6,MAX,5,t,k,s,1,1,物品,1,尝试完毕，回溯，,t=0,，全过程结束！,【,可以输出情况,】,1,、输出可行路径总数；,2,、输出最短路径及其长度；,3,、只有一条路径，输出之；,【,试题,:,迷宫求解,】,0,1,1,1,0,0,0,0,1,0,1,0,1,0,0,0,求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。,假设迷宫如下图所示,:,假设,“当前位置”,指的是“,在搜索过程中某一,时刻所在图中某个方块位置,”，则求迷宫中一条路,径的算法的,基本思想,是：,若当前位置,可通,，则纳,入,当前路径,，并继续朝“下一位置”探索，即切,换“下一位置”为“当前位置”，,如此重复直至到,达出口；,若当前位置“不可通”，则应顺着“来向”,退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块,。所谓,“下一位置”,指的是,“当前位置”四周四个方向（东、南、西、北）上相邻的方块,。假设以,栈,S,记录“当前路径”,，则,栈顶,中,存放的是“当前路径上最后一个通道块”,。由此，,“纳入路径”的操作即为“当前位置入栈”,；,“从当前路径上删除前一通道块”的操作即为“出栈”,。,K0;t1;b1,11;b1,21;pass1,1,1;,flagfalse,;,k k+1;,尝试下一条规则,x bt,1+d1,k;y bt,2+d2,k;,试走一步,可通否,?,true,false,t t+1;,bt,1 x;,到达终点？,true,false,flagtrue,;,计数,(,或打印,);,k 0;,继续下一步,While (k0,时,);,flagfalse,;,回溯,Until t=0;,bt,2 y;,passx,y,1;,bt,3 k;,设定当前位置的初值为入口位置；,do,若,当前位置可通，,则,将当前位置插入栈顶；,/,纳入路径,若,该位置是出口位置，,则,结束；,/,求得路径存放在栈中,否则,切换当前位置的东邻方块为新的当前位置；,否则,若,栈不空且栈顶位置尚有其他方向未被探索，,则,设定新的当前位置为,:,沿顺时针方向旋转,找到的栈顶位置的下一相邻块；,若,栈不空但栈顶位置的四周均不可通，,则,删去栈顶位置；,/,从路径中删去该通道块,若,栈不空，,则,重新测试新的栈顶位置，,直至,找到一个可通的相邻块或出栈至栈空；,while(,栈不空）,；,在此，尚需说明一点的是，所谓当前位置,可通,，指的是,未曾走到过的通道块,，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径后又从路径上删除的通道块（否则只能在死胡同内转圈）。,【,题目描述,】,在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。,每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过,n-1,次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。,因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为,1,，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。,例如有,3,种果子，数目依次为,1,，,2,，,9,。可以先将,1,、,2,堆合并，新堆数目为,3,，耗费体力为,3,。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为,12,，耗费体力为,12,。所以多多总共耗费体力,=3+12=15,。可以证明,15,为最小的体力耗费值。,【,试题,:,合并果子,】,【,题目分析,】,要想得到最优的体力耗费，须保证重量最大的果堆被搬运的次数最少，相反保证重量最少的果堆被尽可能多得搬运。因此很容易想到构造最优二叉树的算法。,此处可以把果堆的重量当做权重，被搬运的次数作为结点到根的路径。,【,样例输入,】,3,1 2 9,【,样例输出,】,15,1,2,9,3,12,1,1,1,1,MIN_WPL=1*2+2*2+9*1,堆栈,题,1,括号匹配,算法,:,(1),遇到左括号进栈；,(2),遇到右括号，弹出栈顶左括号，判断它和当前左括号是否匹配，如果不匹配即可结束，当字符串扫描完毕后，如果栈中还有左括号说明左括号多于右括号，不匹配。,堆栈,题,2,表达式计算,算法,1,：直接计算中缀表达式；,实现：维护优先级表（重点）；维护运算符号栈和数字栈或者变量符号栈；,遇到运算符，如果当前运算符优先级高于栈顶算符优先级，则当前优先级进栈，否则弹出算符栈顶算符，弹出数字栈顶,2,个元素或,1,个元素进行运算。运算结果压入数字栈，依次操作，直到栈空。,算法,2,：先转成后缀表达式，然后计算后缀式；,队列,应用,广搜,最短路,spfa,单调队列,队列,题,1,M,集合的最小,N,个产生数,M,集合元素满足条件：,初始元素为,x,；,2*x+1,同样属于,M,3*x+1,也属于,M.,求,m,中最小的前,n,个数。,解析,算法：,维持两个队列，一个产生,2*x+1,，一个产生,3*x+1,找出两个队头最小的数进行生成新数，然后将找到的最小的数出队，加入目的数组。重复同样的方法直到产生出,N,个数为止。,队列,题,2,合并果子,贪心法，按最优二叉树方法，每次找两个最小堆合并 但是要不断更新单调序列，数据大时会超时，效率低。,堆法；,单调队列法；,单调队列法,维持两个,