找出游戏的获胜者，其中 X 选 1，然后 Y 选 2，然后 X 选 3，等等
有两个玩家，X 和 Y，正在玩游戏。X 将首先开始，并且可以从无限数量的石头中挑选 1 颗石头，然后 Y 将开始并可以挑选 2 颗石头，然后 X 将挑选 3 颗，依此类推，游戏将交替进行，直到 X 挑选的总石头数小于或等于给定数字 A 或 Y 挑选的总石头数小于或等于另一个给定数字 B。如果任何玩家的当前总和大于给定的最大值，则他无法挑选石头并输掉游戏。
输入
int a = 7 , b = 6;
输出
Y 是赢家
解释:首先 X 会移除 1 颗石子，然后 Y 会挑选 2 颗石子，再次 X 会挑选 3 颗石子，Y 会挑选 4 颗石子。
X 的石子数量为 4，如果他再挑选 5 颗，石子数量将超过 7，因此 y 是赢家。
方法 1
在此方法中，我们将遍历 while 循环并将当前石子数量添加到 x 和 y。
示例
#include <bits/stdc++.h>
using namespace std;
// 函数用于查找答案
int findWinner(int a, int b){
// 创建变量来存储玩家的当前石头数量
int sumX = 0, sumY = 0;
int current = 1; // 变量用于存储当前的石头数量
// 遍历循环
while (sumX <= a && sumY <= b){
if(current & 1){
// x 总是会得到奇数个石头
sumX += current;
} else{
sumY += current; // y 总是会得到偶数个石头
}
current = current + 1; // 增加当前值
}
if(sumX > a){
return 2; // 表示 2 (Y) 是赢家
} else{
return 1; // 表示 1 (X) 是赢家
}
}
int main(){
int a = 7, b = 5; // 给定上限
// 调用函数
if(findWinner(a,b) == 1){
cout<<"X 是游戏的赢家"<<endl;
} else{
cout<<"Y 是游戏的赢家"<<endl;
}
return 0;
}
输出
X 是游戏的赢家
时间和空间复杂度
上述代码的时间复杂度为 O(sqrt(min(A, B)))，其中 A 和 B 是给定的步数。在这里，我们在每个步骤增加计数，并且加法带来平方根的因子。
上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
方法 2
在这种方法中，我们将遍历 for 循环并将当前的石头数量添加到 x 和 y。
示例
#include <bits/stdc++.h>
using namespace std;
// 函数用于查找答案
int findWinner(int a, int b){
// 创建变量来存储当前玩家的石头数量
//
int sumX = 0, sumY = 0;
// 遍历循环
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
// 调用函数
if(findWinner(a,b) == 1){
cout<<"X 是游戏的赢家"<<endl;
} else{
cout<<"Y 是游戏的赢家"<<endl;
}
return 0;
}
输出
Y 是游戏的赢家
时间和空间复杂度
上述代码的时间复杂度为 O(sqrt(min(A, B)))，因为我们只是改变了之前代码中的循环方法。
上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外空间。
方法 3
在这种方法中，我们将使用数学公式来获取 x 和 y 的最大可能值，然后对它们进行比较。
示例
#include <bits/stdc++.h>
using namespace std;
int findWinner(int a, int b){
// 创建变量来存储双方玩家当前的棋子数量
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 是游戏的赢家"<<endl;
} else{
cout<<"Y 是游戏的赢家"<<endl;
}
return 0;
}
输出
Y 是游戏的赢家
时间和空间复杂度
上述代码的时间复杂度为 O(log(A + B))，因为我们使用的是 sqrt 方法，它在对数时间内工作。
上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外空间。
结论
在本教程中，我们实现了三种不同的方法来找出两个玩家之间的赢家，这两个玩家正在玩游戏，第一个人挑选奇数颗石头，另一个人挑选偶数颗连续的石头，直到给定数字 A 和 B 的最大和。哪个玩家先无法挑选石头就会输。
