Nim Game ใน C++

แนวคิด

สมมติว่าเล่น Nim Game กับอีกคน มีกองหิน แต่ละครั้งผู้เล่นสลับกันเอาหิน 1-3 ก้อน ผู้ที่เอาหินก้อนสุดท้ายชนะ ผู้เล่น 1 เริ่มก่อน ทั้งคู่ฉลาดและมีกลยุทธ์เหมาะสม ต้องหาว่าผู้เล่น 1 ชนะได้หรือไม่จากจำนวนหินในกอง

เช่น ถ้าอินพุตคือ 5 ผลลัพธ์คือ true มีหิน 5 ก้อน ตอนเริ่ม ถ้าผู้เล่น 1 เอา 1 ก้อน ผู้เล่น 2 เอา 1-3 ก้อน จะเหลืออย่างน้อย 1 ก้อนหลังผู้เล่น 2 จบターン ผู้เล่น 1 จึงชนะ

แก้ได้ด้วยขั้นตอนเดียว:

• คืนค่า true เมื่อ n mod 4 ไม่เท่ากับ 0 มิฉะนั้น 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