【每日一道智力题】之 轮流取石子(简单的尼姆博弈)

简介: 【每日一道智力题】之 轮流取石子(简单的尼姆博弈)

题目:

一共有N颗石子(或者其他乱七八糟的东西),每次最多取M颗最少取1颗,A,B轮流取,谁最后会获胜?(假设他们每次都取最优解)。

解答:

结论:

假如A先取,N<M,A获胜;

     N>M,若N能被(M + 1)整除时,A失败;

        若N不能被(M + 1)整除时,A获胜;

假如B先取,(同上);

分析:(以A先手为例)

N<M时,A一次拿完(不可能给B留机会,前提就是每次取最优),不会给B留机会;

N>M时,A要想赢,必须要在自己倒数第二次取完的时候还剩下(M + 1)颗石子(此时A和B还可以再取一次就可以分出胜负游戏就结束了),这样不论B取几颗,A都获胜!但是要怎样才能控制最后一轮的石子数量?

分两种情况分析,

N不能被(M + 1)整除,A先拿走n颗石子就可以使得剩下的石子数量是(M + 1)的整数倍,那么下一次B拿走任意k颗石子时,A就拿走(M + 1)- k颗石子。这样不论B怎么拿A总能控制剩下的石子数量是(M + 1)的整数倍,那么最后一轮一定剩下(M + 1)颗石子;

N能被(M + 1)整除,A就认输吧。。。(B除非傻才会让A赢)无论A怎么拿,B可以控制石子数量(即当B拿完后总能使剩下的石子数量是(M + 1)的整数倍),在最后一轮之前B拿完后还剩(M + 1)颗,A拿多少颗都是输。

实际上,这就仅仅是运用了小学数学:余数永远比除数小这个特点

分析完了之后,我们就拿长安大学ACM的一道题来练练手吧!

问题描述:

学校会每周来检查一次宿舍,一般情况大多宿舍都是轮流安排值日。但是在1205宿舍,Alex想玩点「新花样」,他对Bob说:咱们来玩一个游戏吧,输了那个人去值日。

游戏规则是这样的:一开始有n个石子,Alex和Bob两个人轮流取石子,每次至少取一个至多取m个。取到最后一个石子的人获胜,也就是最后不能取的那个人输。

假设两个人都非常聪明,每次做出的都是最优选择。最开始Alex先取,问哪个人最终能获胜。

输入

输入第一行为一个整数T,表示一共有T组数据。 接下来有T行,每行有两个整数n(1 ≤ n ≤ 109)和m(1 ≤ m ≤ 109),中间用一个空格隔开。

输出

对于每组数据输出游戏最终获胜者的名字。

样例输入

3 7 3 5 4

样例输出

Alex Bob

下面我们就用c语言来实现这个代码:

#include<stdio.h>
int main()
{
    int T=0;
    int n,m;
    scanf("%d",&T);
    int i=0;
    for(i=0;i<T;i++)
    {
        scanf("%d %d",&n,&m);
        if(m>n||n%(m+1)!=0)
        {
            printf("Alex\n");
        }
        else
        {
                printf("Bob\n");
        }
    }
 } 

结果:

总结:

今天我们通过一道题目,大概的了解了简单的尼姆博弈,但是这个博弈到底是什么,怎么使用,我将会在明天的每日一题中进行深入讲解!这就是今天的每日一道智力题,如果对大佬们有帮助的话,麻烦帮忙点赞+关注哦😛!您的支持是我创造的动力!谢谢大佬们!😉

目录
相关文章
|
1月前
|
人工智能 算法 BI
AcWing 505. 火柴排队(每日一题)
AcWing 505. 火柴排队(每日一题)
|
6月前
|
算法 测试技术 C#
【广度优先搜索】【分类讨论】900. 最佳运动员的比拼回合
【广度优先搜索】【分类讨论】900. 最佳运动员的比拼回合
|
6月前
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
代码随想录Day29 贪心04 LeetCode T860 柠檬水找零 T406 根据身高重建队列 T452 用最少得箭引爆气球
41 0
|
C语言
【每日一道智力题】之高楼扔只因蛋
【每日一道智力题】之高楼扔只因蛋
163 0
|
机器学习/深度学习 C语言 决策智能
【每日一道智力题】之 轮流取石子(尼姆博弈的详解)
【每日一道智力题】之 轮流取石子(尼姆博弈的详解)
442 0
【每日一道智力题】之海盗分金币(上)
【每日一道智力题】之海盗分金币(上)
253 0
|
算法 C语言
假币问题:有n枚硬币,其中有一枚是假币,已知假币的重量较轻。现只有一个天平,要求用尽量少的比较次数找出这枚假币。
(2)当n为奇数时,将前后两部分,即1…n,放在天平的两端,较轻的一端里有假币,继续在较轻的这部分硬币中用同样的方法找出假币;若两端重量相等,则中间的硬币,即第 (n+1)/2枚硬币是假币。n,放在天平的两端,较轻的一端里有假币,继续在较轻的这部分硬币中用同样的方法找出假币;假币问题:有n枚硬币,其中有一枚是假币,已知假币的重量较轻。:因为30位偶数,所以至少要被分一次,然后成为奇数之后,那个假币就是奇数的中位数,所以只需要2次。若输入的硬币数为30,则最少的比较次数为(2),最多的比价次数为(4)。
553 0
铲雪车 骑马修栅栏 (欧拉路径和欧拉回路)
铲雪车 骑马修栅栏 (欧拉路径和欧拉回路)
180 0
UPC-排队出发+AcWing-耍杂技的牛(推公式的贪心)
UPC-排队出发+AcWing-耍杂技的牛(推公式的贪心)
80 0