当前位置:首页 > 算法 > 正文内容

【算法】博弈论——取石子游戏

亿万年的星光3个月前 (04-04)算法283

【题目描述】

有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。

【输入描述】

输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。

【输出描述】

输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。

【样例输入】

BASIC
2	1

【样例输出】

BASIC
0

【题目分析】

这道题目描述的是一个经典的博弈论问题,称为威佐夫博弈(Wythoff's Game)。游戏规则如下:

BASIC
有两堆石子,数量分别为 a 和 b。
两名玩家轮流操作,每次可以选择:
 从其中一堆取走任意数量的石子(至少取 1 颗);
 从两堆中同时取走相同数量的石子。
取走最后一颗石子的人获胜。

我们需要判断给定初始状态 (a, b) 时,先手玩家是否有必胜策略。

【例子分析】

输入(1,2),输出0,先手必败

BASIC
当前玩家无法避免将游戏转移到必胜态:
从第一堆取1个:(0, 2)(对手可从第二堆取2个,直接获胜);
从第二堆取1个:(1, 1)(对手可同时从两堆取1个,直接获胜);
从第二堆取2个:(1, 0)(对手可从第一堆取1个,直接获胜);
从两堆同时取1个:(0, 1)(对手可从第二堆取1个,直接获胜)。
无论怎么操作,对手都能获胜,因此 (1, 2) 是必败态。

输入(3,5),输出0,先手必败

BASIC
所有可能的操作均导致必胜态:
从第一堆取1个:(2, 5)(对手可转移到 (2, 1)(1, 3) 等必胜策略);
从第一堆取2个:(1, 5)(对手可转移到 (1, 2) 必败态,但需强制转移);
从第二堆取2个:(3, 3)(对手可同时取3个直接获胜);
从两堆同时取3个:(0, 2)(对手可从第二堆取2个直接获胜)。
无论怎么操作,对手都能将游戏转移到必败态或直接获胜。

输入(4,7),输出0,先手必败

BASIC
所有操作均导致对手必胜:
从第一堆取1个:(3, 7)(对手可转移到 (3, 5) 必败态);
从第二堆取3个:(4, 4)(对手可同时取4个直接获胜);
从两堆同时取4个:(0, 3)(对手可从第二堆取3个直接获胜)。

输入(2,1),输出0,先手必败


输入(1,1),输出1,先手必胜

BASIC
分析:
必败态均为两堆石子数不等(如 (1,2)(3,5)),因此 (1,1) 是必胜态。
策略:直接取光两堆石子,立即获胜。
步骤:从两堆各取1个,得到 (0, 0),对手无法操作,先手胜。

输入(2,3),输出1,先手必胜

BASIC
从两堆各取1个:(2,3)(1,2)
对手面临 (1,2)(必败态),先手必胜。

输入(4,6),输出1,先手必胜

BASIC
从两堆各取1个:(4,6)(3,5)。
对手面临 (3,5)(必败态),先手必胜。

输入(5,8),输出1,先手必胜

BASIC
从两堆各取1个:(5,8)(4,7)。
对手面临 (4,7)(必败态),先手必胜。

判断方法

给定 (a, b)(假设 a ≤ b),判断是否为必败态的方法:

  1. 计算 k=ba

  2. 计算 aexpected=ϕk

  3. 如果 a=aexpected,则当前状态是必败态(先手必败),否则先手有必胜策略。

具体步骤如下:

  1. 计算 ϕ=1+52

  2. 对于输入 (a, b),假设 a ≤ b,计算 k=ba

  3. 计算 tmp=kϕ

  4. 如果 tmp == a,则当前是必败态,输出 0;否则输出 1

【参考代码】

C++
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    while(cin>>a>>b){
        if(a>b){
            swap(a,b);
        }
        if(a==b){
            cout<<1<<endl;
        }
        if(a==(int)(((sqrt(5)+1)/2*(b-a)))){
            cout<<0<<endl;
        }
        else{
            cout<<1<<endl;
        }
    }
    return 0;
}
阅读剩余的59%

扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

相关文章

【分治】----快速幂

【分治】----快速幂

1.幂幂(power)是指乘方运算的结果。n^m指该式意义为m个n相乘。把n^m看作乘方的结果,叫做n的m次幂,也叫n的m次方。2.幂的数学表示和规则2^3  *   2...

【排序】----选择排序

【排序】----选择排序

1.基本思想每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在待排序的数列最前,直到全部待排序的数据排完。2.过程首先初始化最小元素索引值为首元素。依次遍历待排序数列,遇到小于该最小索引...

【算法】动态规划(一)

1.基本概念在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖...

【算法】归并排序

【算法】归并排序

一、基本思想归并排序的核心思想是将两个已经有序的子序列合并成一个有序序列。整个过程分为两个主要步骤: 1.分解:将待排序的序列不断二分,直到每个子序列只包含一个元素(此时自然有序) ...

【贪心】----基本概念

一、基本概念所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,它所做出的仅仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架,算法设计的关键是贪...

【DFS】搜索回溯基础

【DFS】搜索回溯基础

0.前言       搜索与回溯是计算机解题中常用的算法,很多问题无法根据某种确定的计算法则来求解,可以利用搜索与回溯的技术求解。...