Chương trình tìm hiểu xem chúng ta có thắng trong một trò chơi bằng Python hay không

Giả sử chúng ta đang chơi trò chơi hai người trong đó có n viên bi và trong mỗi vòng, một người chơi phải lấy một số bi bình phương dương. Nếu người chơi không thể lấy số bi bình phương đó, người đó sẽ thua. Vì vậy, với một số n, chúng ta phải tìm xem chúng ta có thể thắng trò chơi hay không. Chúng tôi luôn thực hiện lượt đi đầu tiên và chọn số viên bi tối ưu.

Vì vậy, nếu đầu vào là 14, thì đầu ra sẽ là True. Vì ở lượt đầu tiên, ta lấy 9 viên bi. Điều đó để lại 5 viên bi mà từ đó người chơi kia có thể lấy tối đa 4 viên bi để lại 1 viên bi. Vì vậy, trong lượt tiếp theo, chúng ta lấy viên bi cuối cùng để lại 0 viên bi phía sau đối phương không thể di chuyển. Do đó, chúng tôi giành chiến thắng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu n <=0, thì
  • trả về Sai
• ans:=Sai
• đối với tôi trong phạm vi phần nguyên của (căn bậc hai của (n)) thành -1, giảm đi 1, thực hiện
  • nếu tôi * i> n, thì
    • ra khỏi vòng lặp
  • ans:=ans HOẶC (không giải quyết (n - i * i))
  • nếu ans là True, thì
    • trả lại ans
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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 | (not solve(n - i * i))
      if ans:
         return ans
   return ans

print(solve(14))

Đầu vào

14

Đầu ra

True