Nim Game이라는 게임을 다른 플레이어와 한다고 가정해 보겠습니다. 한 플레이어가 교대로 1~3개의 돌을 제거할 때마다 돌 더미가 있습니다. 마지막 돌을 제거하는 사람이 승자가 됩니다. Player1은 첫 번째 차례에 돌을 제거합니다. 두 선수 모두 매우 영리하고 게임에 대한 최적의 전략을 가지고 있습니다. 플레이어 1이 더미에 있는 돌의 수를 감안할 때 게임에서 이길 수 있는지 여부를 결정하는 알고리즘을 고안해야 합니다.
따라서 입력이 5와 같으면 5개의 스톤이 있으므로 출력이 true가 되므로 처음에 player1이 1개의 스톤을 가져갈 경우 두 번째 플레이어는 1-3개의 스톤을 가져갈 수 있습니다. , 플레이어 2의 턴 후에 최소 하나의 스톤이 남아 있으므로 플레이어 1이 이길 수 있습니다.
이것은 하나의 간단한 단계를 통해 해결할 수 있습니다 -
-
n mod 4가 0과 같지 않으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h> using namespace std; class Solution { public: bool canWinNim(int n) { return n%4!=0; } }; main(){ Solution ob; cout << (ob.canWinNim(5)); }
입력
5
출력
1