博弈 基础的巴什博弈

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1066

有一堆石子共有N个。A B两个人轮流拿,A先拿。每次最少拿1颗,最多拿K颗,拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N和K,问最后谁能赢得比赛。
例如N = 3,K = 2。无论A如何拿,B都可以拿到最后1颗石子。
巴什博弈,后手可以和先手总共拿k+1个

只有一堆物品,共有n个,两人轮流从这对物品取,规定每次至少取一个,最多取m个,取最后一个胜。

1、当n<=m时,先取者可一次去完,所以先取者胜;

2、当n=m+1时,无论先取者如何取,后取者都可一次性取完,所以后取者胜,

       只要n=k(m+1),后去者只要采取正确的取法(取m+1与先取者之间的差),后去者一 

       定能获胜。走到这里规律已经很明显了,先取者要想获胜就必须让后取者面对 

        k(m+1)个。

     综上所述:胜利者一定要让失败者面对看k(m+1)个物品。要判断谁胜利,只需看 

     n%(m+1))(取余),若余数为0,先取者必败,否则后取者必败。

原文地址:https://www.cnblogs.com/heimao5027/p/5517161.html