资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,问题求解与程序设计第二讲 对局问题,李文新,2004.2,2004.6,内容提要,上周作业总结,放硬币问题,取火柴问题,取石子问题-,n,堆,取石子问题 1堆,作业 装箱问题,1005题,弗雷德先生想在路易斯安娜州买一块地造房子。在调查中他了解到由于密西西比河的侵蚀，路易斯安娜州正在以每年,50,平方英里的速度变小。因为弗雷德先生希望在他的新房子里生活直至终老，所以他想知道他的房子是否会被侵蚀掉。,1005题,经过进一步研究，弗雷德发现将要被侵蚀得陆地呈半圆形。半圆是一个以（,0,，,0,）点为中心的圆的一半，半圆的直边是,X,轴。,X,轴以下的部分在水中。在第一年的开始，圆的面积是,0,。（半圆如下图所示）。,1005 问题,1005 问题分析,1,）分析问题寻求算法,因为河水呈半圆形扩散，每年扩散,50,平方英里，所以当给定一点的坐标时，可以用它与原点的距离作为半径，计算以此为半径的半圆的面积，在用这一面积除以,50,，向上取整，得到的就是要求的年数。即使用如下公式计算：,1005 源代码,#,include/,将输入输出的库函数包含,#,include /,将用到的库函数包含进来,voidmain()/,程序开始,floatx,y;/,用来存放读入的坐标值,int,year;/,用于保存计算出来的年数,scanf,(“%f%f”,/,从键盘读入坐标值,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=,x d,2)(x-p)%23=0,3)(x-e)%28=0,4)(x-i)%33=0,1006题,一个最简单直观的做法就是枚举从,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-d,1006题,#,include,#include,void main(),int,p,e,i,d,j,no=1;,scanf,(%d%d%d%dn,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:the next triple peak occurs in%d days.n,no,j-d);,scanf,(%d%d%d%dn,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,堆,第一堆：,a,1,=3,第二堆：,a,2,=3,第三堆：,a,3,=1,图,1,游戏的一个初始局面,取石子问题,n,堆,对于游戏,A,来说，任意的一个初始局面,S=(a1,a2,an)，,我们把这里的,ai,都看成是二进制数。令,#,S=a1 a2 an。,若#,S0，,则先行者（甲）有必胜策略；否则,#,S=0，,这时后行者（乙）有必胜策略。,取石子问题,n,堆,例如,1,：,第一排，,a,1,=7,第二排，,a,2,=3,第三排，,a,3,=3,1 2 3 4 5 6 7,取石子问题,n,堆,1 1 1,0 1 1,0 1 1,-,1 1 1,先手必胜,取石子问题,n,堆,例2,：,第一排,1 01,第二排,2 10,第三排,3 11,-,00,后手必胜,取石子问题 1堆,问 题 描 述,有,N,粒石子，甲乙两人轮流从中拿取，一次至少拿一粒，至多拿先前对方一次所取石子数目的两倍。甲先拿，开始甲可以拿任意数目的石子（但不得拿完）。最先没有石子可拿的一方为败方。,请问，甲能否获胜？（,1,N,100）,取石子问题 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堆,甲必败,：,甲必胜,：,2,3,4,5,6,7,8,取石子问题 1堆,Fibonacci,数列,甲必败,：,甲必胜,：,2,3,4,5,6,7,8,取石子问题 1堆,猜,想,：,设,F,为,Fibonacci,数列,（,F,1,=2，F,2,=3，F,K,=F,K,-,1,+F,K,-,2,）,初始时有,N,粒石子，若,NF,则先手必败，否则先手必胜。,取石子问题 1堆,性质,1,：,若,KN，,则状态,（,N,K）,先手必胜,。,性质,2,：,若状态（,N,N-1）,先手必败，则状态（,N,K）K N,先手必败,。,性质,3,：,若状态（,N,K）K N，,则最后一次取走的石子数目不超过,2,N/3,。,取石子问题 1堆,结论,1,：状态,(,Fi,，A）A N-K,由性质,1,，后手获胜。,后手获胜，先手败,K,(N-K,2K),取石子问题,证 明,：,F,i-1,F,i,F,i,+,1,K,（,2,）若,K F,i-1,根据假设（,F,i-1,K,）,K 2，,先手必胜。,F,F,N,F,平衡状态,:,Fibonacci,数,决策规律,:,找最大,Fibonacci,数,小结,上周作业总结,放硬币问题,取火柴问题,取石子问题-,n,堆,取石子问题 1堆,作业 装箱问题,作业,1008,1013,
展开阅读全文