※ 引述《superds (托福?..这东西能吃吗?￾ )》之铭言： : 请教大家个问题 : 共有n个石子 两名玩家轮流取石子 : 1. 第一名玩家 可以取 1 到 n-1 颗石子（但不能一次取完）。 : 2. 之後的每次最多取 前一位玩家取石数量的 3 倍，但至少要取 1 个石子。 : 3. 取完最後一颗石子的人获胜。 : 是否有必胜策略。 : 基本上就是Fibonacci博弈 : 不过是取石数量从2倍改成3倍 : 又如果是4倍时，要如何解？ : 谢谢大家 : ----- : Sent from JPTT on my Xiaomi 2211133G. 设 前一手拿 p 颗, 还剩下 n 颗时 (p=0 代表初始回合) 不管 p,n 为何, 接下来游戏一定会在有限回合内分出胜负(不会有平局) 而接下来可能的过程也是有限种 所以一定有先必胜或後手必胜策略 令 n>0 时 f(p,n) = { 1, 若先手有必胜法 0, 若後手有必胜法 当p=0时 (初始回合) 先手可以拿 1 ~ n-1个 f(0,n) = { 0, 若 f(k,n-k), k=1~n-1 都是 1 (後手有必胜法) 1, 若 f(k,n-k), k=1~n-1 中至少有一个为0, 先手获胜策略就是拿走使得 f(k,n-k)=0 的k的数量的石子 当p>0时, 先手可以拿 1 ~ min(3p,n) 个 f(p,n) ={ 1, 若 p>=n/3, 直接拿完就获胜 0, 若 p<n/3, 且f(k,n-k), k=1~3p 都是1, (後手有必胜法) 1, 若 p<n/3, 且f(k,n-k), k=1~3p 至少有一个是0, 先手获胜策略为拿走使得 f(k,n-k)=0 的k 的数量的石子 从 n=1 开始建表 f(0,1) 未定义 f(p,1) = 1 对所有 p>=1 n=2 f(0,2) = 0, 因为拿走一颗之後, f(1,1)=1, f(p,2) = 1 对所有 p>=1 以此类推可以画出一张表用填的 填法如下: 从左边第一栏开始, 从上往下填 n=1时, 除了p=0无定义之外, 底下都是1 第二栏以後, 只要看(1,n-1)往左下斜过去的格子 ( (2,n-2), (3,n-3),... ), 只要有一个是0, 那(0,n) 就是1 (先手必胜), 否则就是0(後手有必胜法) 如果对过去第一个为零的格子是 (k,n-k), 那 0<p<k/3 的格子为0, p>=k/3 为1 如果对过去都是1, 那 p<n/3 的格子都是0, p>=n/3 的格子为1 用程式填到 n=100 的结果如下图 (程式码连结放在推文) https://i.imgur.com/8NInX0v.png 第一列 f(0,n) =1 的格子就是一开始先手有必胜法的情形 底下 f(p,n) = 1 就是当对手拿了 p 个之後剩下n 个, 轮到我的时候有必胜法的状况 必胜的走法就是从f(1,n-1), f(2,n-2), ... 往左下找到第几个格子是0,就拿几个石头 从图上可以读出100以内只有 n=2,3,4,6,8,11,15,21,29,40,55,76 时後手有必胜法, 其余都是先手有必胜法 这个方法不管允许拿的最大数量是前一手的2倍(原始的斐波那契拈), 或是改成3倍或4倍都适用 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.224.33.70 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1741272264.A.FC0.html ※ 编辑: mantour (36.224.33.70 台湾), 03/06/2025 22:50:51 ※ 编辑: mantour (36.224.33.70 台湾), 03/06/2025 22:53:48