北京大学ACM国际大学生程序设计竞赛课件2

问题求解与程序设计第二讲对局问题李文新2004.2–2004.6内容提要上周作业总结放硬币问题取火柴问题取石子问题-n堆取石子问题–1堆作业–装箱问题1005题弗雷德先生想在路易斯安娜州买一块地造房子。在调查中他了解到由于密西西比河的侵蚀，路易斯安娜州正在以每年50平方英里的速度变小。因为弗雷德先生希望在他的新房子里生活直至终老，所以他想知道他的房子是否会被侵蚀掉。1005题经过进一步研究，弗雷德发现将要被侵蚀得陆地呈半圆形。半圆是一个以（0，0）点为中心的圆的一半，半圆的直边是X轴。X轴以下的部分在水中。在第一年的开始，圆的面积是0。（半圆如下图所示）。1005–问题1005–问题分析1）分析问题寻求算法因为河水呈半圆形扩散，每年扩散50平方英里，所以当给定一点的坐标时，可以用它与原点的距离作为半径，计算以此为半径的半圆的面积，在用这一面积除以50，向上取整，得到的就是要求的年数。即使用如下公式计算：1005–源代码#includestdio.h//将输入输出的库函数包含#includemath.h//将用到的库函数包含进来voidmain(){//程序开始floatx,y;//用来存放读入的坐标值intyear;//用于保存计算出来的年数scanf(“%f%f”,&x,&y);//从键盘读入坐标值year=(int)ceil((x*x+y*y)*3.1415926/2/50);//套用公式计算年数printf(“第%d年年末\n”,year);//将算出来的年数输出到屏幕上}//程序结束1006题人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。1006题输入输入四个整数：p,e,i和d。p,e,i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d是给定的时间，可能小于p,e,或i。所有给定时间是非负的并且小于365,所求的时间小于21252。输出从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。1006题问题分析令所求的时间为当年的第x天，则x具有如下性质：1)21252=xd2)(x-p)%23=03)(x-e)%28=04)(x-i)%33=01006题一个最简单直观的做法就是枚举从d+1到21252之间所有的数字，寻找第一个满足条件2）3）4）的数字，注意输出时间减去d.。1006题可以做的进一步改进是从d+1开始逐一枚举寻找满足条件2）的数字a，从a开始每步加23寻找满足条件2）3）的数字b，从b开始每步加23*28寻找满足条件2）3）4）的数字x。x就是我们要找的数字，输出时输出x-d。1006题程序设计//读入p,e,i,d//j从d+1循环到21252，如果(j-p)%23==0，跳出循环//j从上次跳出循环的值循环到21252，如果(j-e)%28==0，跳出循环//j从上次跳出循环的值循环到21252，如果(j-i)%33==0，跳出循环//输出j-d1006题#includestdio.h#includemath.hvoidmain(){intp,e,i,d,j,no=1;scanf(%d%d%d%d\n,&p,&e,&i,&d);while(p!=-1&&e!=-1&&i!=-1&&d!=-1){for(j=d+1;j=21252;j++)if((j-p)%23==0)break;for(;j=21252;j=j+23)if((j-e)%28==0)break;for(;j=21252;j=j+23*28)if((j-i)%33==0)break;printf(Case%d:thenexttriplepeakoccursin%ddays.\n,no,j-d);scanf(%d%d%d%d\n,&p,&e,&i,&d);no++;}}放硬币问题在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？放硬币问题事实上，甲只要先在圆桌中心放下一枚硬币，此后无论乙怎么放，甲总在其关于中心对称处放一枚，最终甲必然获胜。甲乙取火柴问题一堆火柴有N根，A，B两人轮流取出。每次可以取1根或2根，问先取者能否有必胜策略？取火柴问题•一般解答：分情况讨论：N=3k后手胜和N！=3k先手胜(k为正整数)•推广：每次可以取1..n根火柴(n为正整数，且1=nN)则N=k(n+1)后手胜，N！=k(n+1)先手胜(k为正整数)取石子问题–n堆甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如图1所示的初始局面：共n=3堆，其中第一堆的石子数a1=3，第二堆石子数a2=3，第三堆石子数a3=1。两人轮流按下列规则取走一些石子，游戏的规则如下：•每一步应取走至少一枚石子；•每一步只能从某一堆中取走部分或全部石子；•如果谁无法按规则取子，谁就是输家。取石子问题–n堆第一堆：a1=3第二堆：a2=3第三堆：a3=1图1游戏的一个初始局面取石子问题–n堆对于游戏A来说，任意的一个初始局面S=(a1,a2,…,an)，我们把这里的ai都看成是二进制数。令#S=a1a2…an。若#S≠0，则先行者（甲）有必胜策略；否则#S=0，这时后行者（乙）有必胜策略。取石子问题–n堆例如1：第一排，a1=7第二排，a2=3第三排，a3=31234567取石子问题–n堆111011011----------------111先手必胜取石子问题–n堆例2：第一排101第二排210第三排311-------------00后手必胜取石子问题–1堆问题描述有N粒石子，甲乙两人轮流从中拿取，一次至少拿一粒，至多拿先前对方一次所取石子数目的两倍。甲先拿，开始甲可以拿任意数目的石子（但不得拿完）。最先没有石子可拿的一方为败方。请问，甲能否获胜？（1N100）取石子问题–1堆用一个简单例子分析：假设有N=4粒石子，则一开始甲最多能取3粒，用（4，3）来表示初始状态。状态转移的拓扑结构甲取1粒甲取2粒甲取3粒乙取1粒乙取2粒乙取1粒乙取2粒乙取1粒甲取1粒甲取2粒甲取1粒甲取1粒乙取1粒（4,3）（3,2）（2,2）（1,1）（2,2）（1,1）（1,1）（0,0）（0,0）（0,0）（1,1）（0,0）（0,0）（0,0）自顶而下构造取石子问题–1堆（4,3）（3,2）（2,2）（1,1）（2,2）（1,1）（1,1）（0,0）（0,0）（0,0）（1,1）（0,0）（0,0）（0,0）败败败败败败注：这里的胜败指的均是先手胜败。1如果一个状态没有子状态，是结局，则根据题目条件判定胜负取石子问题–1堆胜胜胜胜胜胜（4,3）（3,2）（2,2）（1,1）（2,2）（1,1）（1,1）（0,0）（0,0）（0,0）（1,1）（0,0）（0,0）（0,0）败败败败败败注：这里的胜败指的均是先手胜败。1如果一个状态至少有一个子状态是先手败，则该状态是先手胜取石子问题–1堆胜败胜胜胜胜胜胜（4,3）（3,2）（2,2）（1,1）（2,2）（1,1）（1,1）（0,0）（0,0）（0,0）（1,1）（0,0）（0,0）（0,0）败败败败败败注：这里的胜败指的均是先手胜败。1如果一个状态的所有子状态都是先手胜，则该状态是先手败取石子问题–1堆甲必败：甲必胜：2345678…………取石子问题–1堆Fibonacci数列甲必败：甲必胜：2345678…………取石子问题–1堆猜想：设{F}为Fibonacci数列（F1=2，F2=3，FK=FK-1+FK-2）初始时有N粒石子，若N∈{F}则先手必败，否则先手必胜。取石子问题–1堆性质1：若K≥N，则状态（N,K）先手必胜。性质2：若状态（N,N-1）先手必败，则状态（N,K）KN先手必败。性质3：若状态（N,K）KN，则最后一次取走的石子数目不超过2N/3。取石子问题–1堆结论1：状态(Fi，A）AFi先手必败。证明：（一）F1(=2)，F2(=3)时，显然成立。Fi-1FiFi+1（二）若F1至Fi成立，则Fi+1成立。设先手取K粒石子。（1）若K≥Fi-1后手得状态(N-K,2K)2K≥2Fi-1≥Fi-1+Fi-2=FiN-K由性质1，后手获胜。后手获胜，先手败K(N-K,2K)取石子问题证明：Fi-1FiFi+1K（2）若KFi-1根据假设（Fi-1,K）KFi-1必败，所以后手可以使先手面临(Fi，X)状态。(Fi,X)由性质3：X≤2Fi-1/3×2=4Fi-1/3≤Fi-1+½Fi-1≤Fi-1+Fi-2≤Fi因此(Fi,X)是必败取石子问题结论2：状态(N，N-1）N不属于{F}且N2，先手必胜。FF’NF’’平衡状态:Fibonacci数决策规律:找最大Fibonacci数小结上周作业总结放硬币问题取火柴问题取石子问题-n堆取石子问题–1堆作业–装箱问题作业10081013