Chương trình tìm người chiến thắng trò chơi loại bỏ phần tử tập hợp bằng Python

Giả sử Ta có tập hợp n số tự nhiên đầu tiên {1..n}. Amal và Bimal đang chơi một trò chơi. Luật chơi như dưới đây

Amal luôn chơi trước
Trong mỗi lần di chuyển, người chơi hiện tại chọn một số nguyên tố p từ tập hợp. Sau đó, người chơi loại bỏ p và tất cả các bội số của nó khỏi tập hợp.
Ai không có nước đi sẽ thua trò chơi Nếu có n, chúng ta phải tìm ra tên người chiến thắng.

Vì vậy, nếu đầu vào là n =5, thì đầu ra sẽ là Amal, vì tập ban đầu là {1,2,3,4,5}. Bây giờ, hãy để Amal chọn một số p =2 và loại bỏ 2, 4 khỏi tập hợp, do đó tập hợp hiện tại là {1,3,5}, còn lại hai số nguyên tố, vì vậy Bimal có thể chọn bất kỳ số nào trong số chúng nhưng không có phần tử còn lại để loại bỏ và cuối cùng Amal loại bỏ một số nguyên tố khác và giành chiến thắng trong trò chơi.

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

số nguyên tố:=một mảng có kích thước 100000, ban đầu tất cả đều là 0
sàng:=một mảng có kích thước 100000, ban đầu tất cả đều là 0
đối với tôi trong phạm vi từ 2 đến 99999, hãy thực hiện
- nếu sàng [i] giống 0, thì
  - primes [i]:=primes [i-1] +1
  - đối với j trong phạm vi i đến 100000, cập nhật từng bước theo i, thực hiện
    - sàng [j]:=i
- nếu không,
  - primes [i]:=primes [i-1]
Từ phương thức chính, hãy làm như sau -
trả về "Số thập phân" nếu số nguyên tố [n] là số lẻ, ngược lại là "Amal"

Ví dụ

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

primes = [0 for i in range(100001)]
sieve = [0 for i in range(100001)]
for i in range(2, 100000):
   if sieve[i] == 0:
      primes[i] = primes[i-1]+1

      for j in range(i, 100001, i):
         sieve[j] = i
   else:
      primes[i] = primes[i-1]

def solve(n):
   return "Bimal" if primes[n] % 2 == 0 else "Amal"

n = 5
print(solve(n))

Đầu vào

Đầu ra

Amal