Chương trình kiểm tra thắng thua trong trò chơi lấy viên bi vuông Python

Trò chơi hai người với n viên bi. Mỗi lượt, người chơi phải lấy số viên bi là số chính phương dương. Người không lấy được thì thua. Bạn đi trước và chọn tối ưu. Xác định có thắng được hay không.

Ví dụ: n = 14 → True (lấy 9, đối thủ lấy tối đa 4, bạn lấy 1 còn lại).

Giải thuật (Đệ quy + Memoization)

1. Nếu n <= 0 trả về False
2. Duyệt i từ int(sqrt(n)) xuống 1
3. Nếu i*i > n thì break
4. ans = ans OR (not solve(n - i*i))
5. Nếu ans thành True thì trả về ngay

Ví dụ triển khai

from math import sqrt

def solve(n):
    if n <= 0:
        return False
    ans = False
    for i in range(int(sqrt(n)), 0, -1):
        if i * i > n:
            break
        ans = ans or (not solve(n - i * i))
        if ans:
            return ans
    return ans

print(solve(14))

Đầu vào

14

Đầu ra

True