資料結構
網路
關係資料庫管理系統 (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 次瀏覽
