资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,问题求解与程序设计第三讲 称重问题,李文新,2004.2,2004.6,内容提要,作业总结 - 1008,作业总结 - 1013,何林冬令营报告 称球问题,自学及讨论 征服者,作业,作业总结 - 1008,题意,Haab,19,个月 前18个月每月20天 第19个月5天,0-19 月名 0-5 月名,Tzolkin,13,个月 天数为20个轮转,1,mix 2- 3- ,问题,将,Haab,日期转换成,Tzolkin,日期,源程序,1008 源程序,作业总结 - 1013,题意,12枚硬币，其中一枚是假币，可能轻也可能重,称三次，每次左右硬币数目相等，结果：轻重平,问题,求出假币，并给出其轻重,源程序,1013源程序,一类称球问题的解法,长沙雅礼中学 何林,问题的提出,给定,N,个球,有个比标准球重的次品混入其中,你有一架天平，用最少的次数找出这个次品。,N = 3,1,2,3,1,2,是,次品,1,2,是次品,1,2,是次品,N=3,时称,1,次就可以找出次品,N = 9,1,2,3,4,5,6,7,8,9,A,B,C,A,B,次品在,A,中,次品在,B,中,A,B,通过一次称量，可以把次品可能存在的范围从,9,个，缩小到,3,个,N = 3,的时候一次就能称出次品,N = 9,时称,2,次,次品在,C,中,A,B,更一般的情况,N = 3k,1,2,k,1,2,k,1,2,k,A,B,C,更一般的情况,A,B,A,B,A,B,次品在,A,中,次品在,B,中,次品在,C,中,范围缩小到原来的,1/3,更一般的情况,n = 3k+1, n = 3k+2,和,n=3k,类似，也是均分成三堆,每次称量把范围大致缩小到原来的,1/3,因此：从,n,个球中找次品至多要称,log,3,n,次。（,统一表示取上整）,判定树,log,3,n,无疑是可行解。,最优性,为什么三分？,因为天平只有三种可能：左偏、右偏、平衡,判定树,称(1, 2),=,=,1,3,=,7,9,=,4,6,=,= log,3,n,log,3,n,是最优解,小结,引进了有力工具：判定树。将主观的直觉严谨化。,三分法是解决这类问题的根本着眼点。,三分时必须充分的均匀,Problem,Conquerors,batalion,Table of Contents,The problem,Solution,The problem,CENTRAL EUROPEAN OLYMPIAD IN INFORMATICS,30 June 6 July 2002,Day 1: conquer,Conquerors battalion,Time limit: 1 s,Memory limit: 16 MB,The problem,In the whole history of mankind one can find several curious battles, like the following one in France, in 1747. . .,The problem,There was a fortress in,Bassignac,-le-,Haut, a small village lying on the left bank,of river Dordogne, just over the,Chastang,dam. From the dam up to the fortress,there was a wide staircase made out of,red marble.,The problem,One day in the morning, the guard,spotted a large battalion,Approaching the fortress, with a,dreaded leader The Conqueror.,The problem,When The Conqueror reached the,fortress, he was already awaited by its,commandant. The commandant,proposed: “I see that you have many,soldiers behind you, standing on the,stairs. We can play a small game:,The problem,In each round, you will divide your,soldiers into two groups in an arbitrary,way. Then I will decide which one of,them stays and which one goes home.,Each soldier that stays will then move,up one stair.,The problem,If at least one of your soldiers reaches,the uppermost stair, you will be the,winner, in the other case, you will be the,loser.,The problem,The Conqueror immediately liked,this game, so he agreed and started,to conquer.,The problem,Task,Your role is The Conquerors now. There,are N stairs to the fortress (2 = N =,2000) and you have at most 1 000 000 000,soldiers.,The problem,For each stair, you are given the number,of soldiers standing on it, with number 1,being the uppermost stair and N the,bottom one. None of your soldiers,stands on stair 1 at the beginning.,The problem,For each starting position given to your,program, if the position is winning (i.e. there,is a strategy that enables you to win the,game regardless of your opponents moves),Your program should win. Otherwise it,should just play the game (and lose),correctly.,The problem,This is an interactive problem; you will play,against a library as specified below. In,each round, your program will describe a,group of soldiers to our library. The library,returns 1 or 2 specifying which group of,soldiers should stay (1 means the group you,described, 2 means the rest of the soldiers).,The problem,In case the game ends (either because,you won or there are no more soldiers,in the game), the library will terminate,your program correctly. Your program,may not terminate in any other way.,The problem,Library interface,The library,libconq,provides two routines:, start returns the number N and fills an array stairs with numbers of soldiers,standing on the stairs (i.e. there are stairsi soldiers standing on stair i),The problem, step takes an array subset (with at,least N1 elements), describing the,group of soldiers you chose, and,returns 1 or 2 as described above; the,group of soldiers is specified by,numbers of soldiers on each stair, as in,the start function,The problem,If you fail to specify a valid group of,soldiers, the game will be terminated,and your program will score zero points,for the particular test case. Please note,that also in C/C+ the stairs are,numbered starting from 1.,The problem,Following are the declarations of these routines in,FreePascal,and C/C+:,procedure start(,var,N:,longint,;,var,stairs:array of,longint,);,function step(subset:array of,longint,):,longint,;,void start(,int,*N,int,*stairs);,int,step(,int,*subset);,The problem,Below you can find examples of library,usage in both,FreePascal,and C/C+; both,fragments do the same start the game and,then play one round, with the chosen group,containing all soldiers on randomly chosen,stairs. Your real program will probably play,the rounds in an infinite loop.,The problem,You are strongly encouraged to define,the arrays stairs and subset in the same,way as they are defined in the example,below.,The problem,FreePascal,example:,uses,libconq,;,var,stairs: array1.2000 of,longint,;,subset: array1.2000 of,longint,;,i,N,result:,longint,;,.,start(N,stairs);,.,.,for i:=1 to N do,if random(2)=0 then subseti:=0,else subseti:=stairsi;,result:=step(subset);,.,The problem,C/C+ example:,#include ,libconq,.h,int,stairs2001;,int,subset2001;,int,i,N,result;,.,start(,.,for (i=1;i=N;i+),if (rand()%2=0) subseti=0;,else subseti=stairsi;,result=step(subset);,.,The problem,You have to link the library to your,program by uses,libconq,; in,FreePascal,and by #include ,libconq,.h“,in C/C+, where you have to compile,your program by adding,libconq,.c to the,compiler arguments.,The problem,An example of the game,You: Library:,start(N,stairs) N=8, stairs=(0,1,1,0,3,3,4,0),step(0,1,0,0,1,0,1,0) returns 2(,0,0,1,0,2,3,3,0,0,),step(0,1,0,0,0,1,0,0) returns 2(,0,0,0,2,3,2,0,0,0,),step(0,0,0,3,2,0,0,0) returns 1(,0,0,0,3,2,0,0,0,0,),step(0,0,2,0,0,0,0,0) returns 2(,0,0,1,2,0,0,0,0,0,),step(0,1,0,0,0,0,0,0) returns 2(,0,0,2,0,0,0,0,0,0,),step(0,1,0,0,0,0,0,0) no return: you won,The problem,The file,libconq,.,dat,for the example,above,would look like this:,8,0 1 1 0 3 3 4 0,Solution,Lets try to tell somehow how good a position is. If we have two soldiers on the same stair (and no other soldiers), in the next round we will have at most only one soldier but one stair higher. In this way, one soldier on the stair S is equivalent to two soldiers on the stairs S+1.,Solution,From now on a soldier on the stair S will have the value 2,N-S,. The value of a position will be the sum of the values of all the soldiers. Note that all positions, where the Conqueror has won, have the value at least 2,N-1,because there is a soldier on the stair number 1.,Solution,1,2,4,5,3,1,2,4,8,16,2,5-1,2*2,5-2,4*2,5-3,8*2,5-4,16*2,5-5,A soldier on stair S,has value 2,N-S,Solution,1,2,4,5,3,n1,n2,n3,n1*2,5-2,n2*2,5-3,n3*2,5-4,A positions value = sum (all soldiers),Solution,Losing positions,If the value of the position is less than 2,N-1,and the commandant plays optimally, the Conqueror will lose.,Solution,Proof,If the value is less than 2,N-1, the Conqueror didnt win yet. Lets take a look at one round of the game. The Conqueror divides his soldiers in some way. The commandant will choose this group to stay and the other to leave.,Solution,When any soldier moves up one stair, his value doubles. Therefore the value of the new position will be less than 2*2,N-2,=2,N-1,and the number of the soldier will decrease. There is a finite number of soldiers, and so the game ends in a finite number of moves. The value of a position will always be less than 2,N-1, also at the end there will be no soldiers and the Conqueror will lose.,Solution,Losing position,2,N-1,=a,1,=,a,M, M=2) be powers of two with sum(a,i,1= 2,N-2,. Then for some K holds sum(a,i,1=i=2,3,= 2,3,= 2,2,=2,2,(M=4, N=6),2,3,+ 2,3,+ 2,2,+2,2, 2,4,Then K=2, 2,3,+ 2,3,= 2,4,Solution,Proof,Induction on M. For M=2 the lemma holds.,2,N-2,= a,1,=,a,2,a,1,+,a,2,=,2,N-2,Either a,1,=,2,N-2,(k=1),or (,a,1,=,a,2,=,2,N-3,and,a,1,+,a,2,=,2,N-2,(k=2),Solution,Now let M2 and,sum(a,i,1 2,N-2,Because,a,i,s,are multiple of 2,sum(a,i,1=i=M) = k,1,a,M,2,N-2,= k,2,a,M,Therefore sum(a,i,1= 2,N-2,+a,M,Then sum(a,i,1=2,N-2,We may apply the induction assumption.,Solution,From the lemma we get that if the sum of the soldiers values is at least 2,N-1, we may select the first (,eg,. Closet to the top of the staircase) few of them so that the sum of their values will be exactly 2,N-2,. The Conqueror may also divide his soldiers into these two groups.,Solution,3,2,N-3,4,2,N-4,4,2,N-4,5,2,N-5,2,N-2,Solution,If we are in a losing position, we choose an empty set and loose instantly. If we are in a winning position, we find the place where to split the soldiers by adding the values of soldiers on stairs 1,2,until the value reaches 2,N-2,.,本节课小结,作业总结 - 1008,作业总结 - 1013,何林冬令营报告 称球问题,自学及讨论 征服者,作业,作业,1016,1048,
展开阅读全文