ACM-威佐夫博弈之取石子游戏——hdu1527

 admin  2020-03-29    评论

  所谓威佐夫博弈,是ACM题中罕见的组合游戏中的一种,大年夜致上是如许的:

  有两堆石子,无妨先认为一堆有 10,另外一堆有 15 个,双方轮番取走一些石子,正当的取法有以下两种:

  1、在一堆石子中取走任意多颗;

  2、在两堆石子中取走相反多的任意颗;

  约定取走最后一颗石子的报答赢家,求必胜计谋。

  两堆石头位置是一样的,我们用余下的石子数(a,b)来表现形状,并画在平面直角坐标系上。

  和前面相似,(0,0)必然是 P 态,又叫必败态。

  (0,k),(k,0),(k,k)系列的节点必然不是 P 态,而是必胜态,你面对如许的局面必然会胜,

  只需依照规矩取一次便可以了。

  再看 y=x 上方未被划去的格点,(1,2)是 P 态。

  k > 2 时,(1,k)不是 P 态,比如你如果面对(1,3)的局面,你是有能够赢的。

  同理,(k,2),(1 + k, 2 + k)也不是 P 态,划去这些点和它们的对称点,然后再找出 y=x 上方残剩的点,

  你会发明(3,5)是一个 P 态,如此下去,假设我们只找出 a ≤ b 的 P 态,则它们是(0,0),(1,2),(3,5),(4,7),(6,10)……它们有甚么规律吗?

  疏忽(0,0),很快会发明关于第 i 个 P 态的 a,a=i * (sqrt(5) + 1)/2 然后取整;而 b=a + i。居然和黄金联系点扯上了关系。

  前几个必败点以下:(0,0),(1,2),(3,5),(4,7),(6,10),(8,13)……可以发明,关于第k个必败点(m(k),n(k))来讲,m(k)是前面没有出现过的最小天然数,n(k)=m(k)+k。

  那么任给一个形势(a,b),如何辨别它是否是必败态呢?我们有以下公式:

  ? ak=[k(1+√5)/2],bk=ak + k? (k=0,1,2,…,n 方括号表现取整函数)

  以上为百度百科。。。反正我是没咋看懂。。。

  我的思路:

  关于一个形状(a,b)

  先对a,b大年夜小辨别,让a

  设置一个变量k为a,b差值(k=b-a)

  然后辨别 ? a==k*(1+sqrt(5.0))/2.0

  相等,则表现(a,b)为独特态。

  这个做完,可以做一做进阶版的

  hdu2177


上一篇:2019年10月11日cba季前赛北京首钢vs江苏直播 首钢男
下一篇:没有了
版权信息
永久链接://a/jrrd/20200329-58.html
转载请注明转自》365betACM-威佐夫博弈之取石子游戏——hdu1527
    相关文章