Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm người chiến thắng trò chơi ném đá bằng Python

Giả sử Amal và Bimal đang chơi một trò chơi và lượt của Amal là người đầu tiên. Trò chơi như dưới đây -

Có n viên đá trong một đống. Mỗi người chơi có thể lấy một viên đá từ đống và nhận điểm dựa trên vị trí của viên đá đó. Amal và Bimal có thể định giá các viên đá theo cách khác nhau.

Chúng ta có hai mảng có cùng độ dài, A_Values ​​và B_Values. Mỗi A_Values ​​[i] và B_Values ​​[i] đại diện cho cách Amal và Bimal, tương ứng, định giá viên đá thứ i. Ở đây ai có số điểm tối đa, người đó sẽ là người chiến thắng sau khi lấy hết đá. Nếu hòa, trò chơi có kết quả hòa. Cả hai người chơi sẽ chơi một cách tối ưu. Cả hai người họ đều biết giá trị của đối phương. Vì vậy, nếu Amal thắng, trả về 1. Nếu Bimal thắng, trả về -1. Và đối với một trận hòa, trả về 0.

Vì vậy, nếu đầu vào là A_Values ​​=[2,4] B_Values ​​=[3,5], thì đầu ra sẽ là 1 vì Amal sẽ chọn viên đá thứ hai với điểm 4, vì vậy Bimal chỉ có một cơ hội để lấy viên đá đầu tiên có điểm 3, nhưng vì Amal có số điểm cao hơn nên anh ấy thắng.

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

  • n:=kích thước của A_Values ​​
  • mergeValues:=một danh sách mới
  • đối với tôi trong phạm vi từ 0 đến n, thực hiện
    • tmpV:=A_Values ​​[i] + B_Values ​​[i]
    • chèn cặp (temV, i) vào giá trị kết hợp ở cuối
  • sắp xếp danh sách kết hợp Giá trị theo thứ tự ngược lại
  • score_a:=0, score_b:=0
  • đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
    • curV:=mergeValues ​​[i]
    • nếu tôi mod 2 giống 0, thì
      • score_a:=score_a + A_Values ​​[curV [1]]
    • nếu không,
      • score_b:=score_b + B_Values ​​[curV [1]]
  • nếu score_a> score_b, thì
    • trả lại 1
  • ngược lại, khi score_a giống như score_b, thì
    • trả về 0
  • nếu không,
    • trả về -1

Ví dụ

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

def solve(A_Values, B_Values):
   n = len(A_Values)
   combinedValues = []
   for i in range(n):
      tmpV = A_Values[i] + B_Values[i]
      combinedValues.append([tmpV, i])

   combinedValues.sort(reverse=True)

   score_a, score_b = 0, 0
   for i in range(n):
      curV = combinedValues[i]
      if (i % 2 == 0):
         score_a += A_Values[curV[1]]
      else:
         score_b += B_Values[curV[1]]

   if (score_a > score_b):
      return 1
   elif (score_a == score_b):
      return 0
   else:
      return -1

A_Values = [2,4]
B_Values = [3,5]
print(solve(A_Values, B_Values))

Đầu vào 

[2,4], [3,5]

Đầu ra 

1