数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在一个游戏中，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 先取走 1 个石子，然后 Y 取走 2 个石子，X 再取走 3 个石子，Y 取走 4 个石子。
X 的石子数量为 4，如果他再取 5 个，就会超过 7，所以 Y 获胜。
方法一
在这个方法中，我们将遍历 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)，因为我们没有使用任何额外的空间。
方法二
在这个方法中，我们将遍历 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)，因为我们没有使用任何额外的空间。
方法三
在这个方法中，我们将使用数学公式来获得 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;
}
输出
Y is the winner of the game
时间和空间复杂度
上述代码的时间复杂度为 O(log(A + B))，因为我们使用了在对数时间内工作的 sqrt 方法。
上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
结论
在本教程中，我们实现了三种不同的方法来找出两个玩家之间的获胜者，他们玩的游戏是第一个人取奇数个石子，另一个人取连续的偶数个石子，直到给定数字 A 和 B 的最大总和。第一个无法取石子的玩家将输掉游戏。
46 次浏览
