C++ 找出游戏的赢家，其中X先选1个，然后Y选2个，然后X选3个，依此类推

有两个玩家，X和Y，正在玩一个游戏。X将首先开始，并可以从无限个石头的集合中选择1个石头，然后轮到Y选择2个石头，然后X选择3个石头。游戏将交替进行，直到X选取的总石头数量小于或等于给定的数字A，或者Y选取的总石头数量小于或等于另一个给定的数字B。如果任何一位玩家的当前总和大于任何一位玩家的给定最大值，那么他将无法选择石头并输掉游戏。

输入

int a = 7 , b = 6;

输出

Y is the winner

解释：首先X将移除一块石头，然后Y将挑选2块石头，然后X将挑选3块石头，Y将挑选4块石头。

X的石头计数为4，如果他再挑选5块石头，将超过7，所以Y是赢家。

方法1

在这个方法中，我们将遍历while循环，并将当前数量的石头加到X和Y上。

例子

#include <bits/stdc++.h>
using namespace std;

// function to find the answer 
int findWinner(int a, int b){
    // creating variables to store the current number of stones for both the player's 
    int sumX = 0, sumY = 0;
    int current = 1; // variable to store the current count of stones 
    // traversing over the loop 
    while (sumX <= a && sumY <= b){
        if(current & 1){
           // x will always get the odd number of stones
           sumX += current;
        } else{
           sumY += current; // y will always get the even number of stones 
        }
       current = current + 1; // increasing the current value 
    }
    if(sumX > a){
       return 2; // indicating 2 (Y) is winner 
    } else{
       return 1; // indicating 1 (X) is winner 
    }
}
int main(){
    int a = 7, b = 5; // given upper limits 
    // calling the function 
    if(findWinner(a,b) == 1){
       cout<<"X is the winner of the game"<<endl;
    } else{
       cout<<"Y is the winner of the game"<<endl; 
    }
    return 0;
}

输出

X is the winner of the game

时间和空间复杂度

上述代码的时间复杂度为O(sqrt(min(A, B)))，其中A和B是给定的步数。在这里，我们在每一步增加计数，并且加法带来了平方根的因子。

上述代码的空间复杂度为O(1)，因为我们不使用任何额外的空间。

方法2

在这种方法中，我们将遍历for循环，并将当前的石头数量添加到x和y中。

示例

#include <bits/stdc++.h>
using namespace std;

// function to find the answer 
int findWinner(int a, int b){
    // creating variables to store the current number 
    // of stones for both the players 
    int sumX = 0, sumY = 0;
    // traversing over the loop 
    for(int i=1; sumX <= a && sumY <=b; i++){
        if(i & 1){
           sumX += i;
        } else{
           sumY += i; 
        }
    }
    if(sumX > a){
       return 2; // indicating 2 (Y) is winner 
    } else{
       return 1; // indicating 1 (X) is winner 
    }
}
int main(){
    int a = 7, b = 6; // given upper limits 
    // calling the function 
    if(findWinner(a,b) == 1){
       cout<<"X is the winner of the game"<<endl;
    } else{
       cout<<"Y is the winner of the game"<<endl; 
    }
    return 0;
}

输出

Y is the winner of the game

时间和空间复杂度

上面代码的时间复杂度为O(sqrt(min(A, B))), 因为我们只是改变了以前代码的循环方法。

上面代码的空间复杂度为O(1)，因为我们没有使用任何额外的空间。

方法3

在这个方法中，我们将使用数学公式来得到x和y的最大可能值，之后再比较它们。

例子

#include <bits/stdc++.h>
using namespace std;

int findWinner(int a, int b){
    // creating variables to store the current number of stones for both the players 
    int sumX = 0, sumY = 0;
   int maxA = sqrt(a);
   int maxB = (sqrt(4 * b + 1) - 1)/2;
   if(maxA*maxA == a){
      maxA++;
   }
   if((maxB * (maxB + 1)) == b){
      maxB++;
   }
    if(maxA <= maxB){
       return 2; // indicating 2 (Y) is winner 
    } else{
       return 1; // indicating 1 (X) is winner 
    }
}
int main(){
    int a = 7, b = 6; // given upper limits 
    if(findWinner(a,b) == 1){
       cout<<"X is the winner of the game"<<endl;
    } else{
       cout<<"Y is the winner of the game"<<endl; 
    }
    return 0;
}