首页 > 其他分享 >威佐夫博弈:有两堆各若干个石头,两个人轮流从某一堆或同时从两堆中取同样多的石头,规定每次至少取一个,多者不限,最后取光者得胜。

威佐夫博弈:有两堆各若干个石头,两个人轮流从某一堆或同时从两堆中取同样多的石头,规定每次至少取一个,多者不限,最后取光者得胜。

时间:2024-08-07 14:40:05浏览次数:6  
标签:取光者 两堆 右取 石头 奇异 局势 手胜

威佐夫博弈

规则:有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

首先,根据枚举法分析可能性情况得出规律。
当两堆石头处于以下的数量关系时,对先手者是不利的。如(0,0)(1,2)(3,5)(4,7)(6,10)…

举个例子,对于(1,2):
先手在左堆取1个得(0,2),后手取完右堆,后手胜。
先手在右堆取1个得(1,1),后手两堆同取1个,取完,后手胜。
先手在右堆取2个得(1,0),后手取一个,后手胜。

对于(3,5)的情况:
A左取1,(2,5),B右取4,(2,1),A面对此情况必输,后手胜。
A左取2,(1,5),B右取3,(1,2),A必输,后手胜。
A左取3,后手胜。
A右取1,(3,4),B同时取2,(1,2),后手胜。
A右取2,(3,3),后手胜。
A右取3,(3,2),B左取2,(1,2),后手胜。
A右取4,(3,1),B左取1,(2,1),后胜。
A右取5,后手胜。
可以发现,若B总是采取对他最有利的策略,则A面对(3,5)的情况是必输的。(这里留下一个问题,如果B不总是智商在线,那么A有没有翻盘的可能?)

推广到任意自然数:
若两堆石头个数为(a,b)规定a≤b。
a=k*(1+√5)/2 并向下取整 (其中(1+√5)/2为黄金比例)
b=a+k (k为自然数)
(a,b)此时面对此情况的选手为必输,即尽量避免自己面对此情况,并尽移动自己的石头使得对手得到这样的场景,称这样的场景为奇异局势。

奇异局势的性质:
1.对于任意一个数,都一定会是奇异局势中的一个,但是不一定是小的那个还是大的那个。
2.任何自然数都包含在一个且仅有一个奇异局势中。
3. 任意操作都可将奇异局势变为非奇异局势。
4. 采用适当的方法,可以将非奇异局势变为奇异局势。

如何判断自己的局势是否是奇异局势呢?
先将石头数排列成左小右大的情况,并设左边石头数为a,右边为b。
1,计算k=b-a
2,计算a1与b1。a1=k*(1+√5)/2 并向下取整,b1=a1+k
3,若a=a1并且b=b1,则当前局面是奇异局势

如何在自己的回合将局面转换成奇异局势呢?
排列石头左小右大,用(a,b)表示;设某奇异局势石头数为(ak,bk),(aj,bj)。
1,若两堆相等,则同时取走a(b)数量的石头,形成(0,0)的奇异局势。
2,若a=ak,b>bk,则右堆取b-bk个石头
3,若a=ak,b<bk,由于不同奇异局势的差值k都是唯一的,所以计算k=b-a,再两边同时拿去k个石头。
4,若a>ak,b=bk,则左取a-ak个。
5,若a<ak,b=bk,分两种情况(此时不能和3一样,因为左边的石头可能不够减)
(1)a=aj(即左边能构成奇异对的左边部分,只要使得b也凑成奇异对即可),计算k=a/((1+√5)/2 ),右边拿去k个石子。
(2)a=bj(a能构成奇异对的大的那个数,只要使得b凑成奇异对的小的那个数即可),计算k,联立a1和b1的计算式可得,bj-k= k*(1+√5)/2 ,bj=k*(1+ (1+√5)/2) ,k=bj/(1+ (1+√5)/2),随后右边拿k个石头。

标签:取光者,两堆,右取,石头,奇异,局势,手胜
From: https://www.cnblogs.com/zilin-wang/p/18346989

相关文章

  • 代码随想录训练第三十一天|LeetCode1049.最后一块石头的重量II、LeetCode494.目标和、
    文章目录1049.最后一块石头的重量II思路一维数组二维数组494.目标和思路一维数组解法二维数组解法474.一和零思路1049.最后一块石头的重量II有一堆石头,用整数数组stones表示。其中stones[i]表示第i块石头的重量。每一回合,从中选出任意两块石头,然后将它们一......
  • 洛谷 跳石头
    原题题目描述一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直......
  • *算法训练(leetcode)第三十一天 | 1049. 最后一块石头的重量 II、494. 目标和、474. 一
    刷题记录*1049.最后一块石头的重量II*494.目标和474.一和零*1049.最后一块石头的重量IIleetcode题目地址本题与分割等和子集类似,要达到碰撞最后的石头重量最小,则尽可能把石头等分为两堆。时间复杂度:O......
  • # 代码随想录算法训练营第38天 | 01背包问题:1049.最后一块石头的重量II(最多能装多少)、
    1049.最后一块石头的重量IIhttps://leetcode.cn/problems/last-stone-weight-ii/代码随想录https://programmercarl.com/1049.最后一块石头的重量II.html#算法公开课494.目标和https://leetcode.cn/problems/target-sum/description/代码随想录https://programmercarl.com......
  • 2850. 将石头分散到网格图的最少移动次数 Medium
    给你一个大小为 3*3 ,下标从 0 开始的二维整数矩阵 grid ,分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头,一个格子里可能会有 多个 石头。每一次操作中,你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。请你返回每个格子恰......
  • 题解:洛谷 P2678 [NOIP2015 提高组] 跳石头
    题解:洛谷P2678[NOIP2015提高组]跳石头标签:二分,贪心题意给定一个数列,\(a_0=0,a_{N+1}=L\),从其中删除不超过\(M\)个数,使得\(a_i-a_{i-1}\)的最小值最大。思路从最小值最大不难想到二分答案。统计\(a_i-a_j<mid\)的数量\(k\),如果不满足的话说明不删,\(j\getsi\)。......
  • Day 38 | 1049. 最后一块石头的重量 II 、494. 目标和 、474.一和零
    1049.最后一块石头的重量II本题就和昨天的416.分割等和子集很像了,可以尝试先自己思考做一做。视频讲解:https://www.bilibili.com/video/BV14M411C7oVhttps://programmercarl.com/1049.最后一块石头的重量II.html有一堆石头,每块石头的重量都是正整数。每一回合,从中选出......
  • Python实战,桌面小游戏,剪刀石头布
    注意:本文的下载教程,与以下文章的思路有相同点,也有不同点,最终目标只是让读者从多维度去熟练掌握本知识点。下载教程:Python项目开发实战_桌面小游戏-剪刀石头布_编程案例解析实例详解课程教程.pdf创建一个基于Python的桌面小游戏“剪刀石头布”是一个很好的编程实践项目,它......
  • 代码随想录算法训练营第四十二天 | 1049最后一块石头的重量II 494.目标和 474.一和零
    1049.最后一块石头的重量题目链接文章讲解视频讲解解题思路:  将石头尽量分为相等的两堆,两堆最差即为所求结果  石头的重量就是石头的价值动规五部曲:dp[j]:表示背包容量为j时可以装的石头的总价值递推公式:dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]初始化:均......
  • 猜拳游戏 (石头剪刀布)
    1、需求分析参与游戏的角色有两个(玩家与电脑,人机对战),玩家手工出拳,电脑随机出拳,根据石头剪刀布判断输赢。玩家:player(玩家手工输入石头0、剪刀1、布2)电脑:computer(随机出拳)输赢结果很重要,有三种情况:①玩家赢☆player:石头 赢computer:剪☆player:剪刀 赢computer:布......