Chương trình tìm chỉ mục bắt đầu của đứa trẻ nhận được bong bóng cuối cùng trong Python?

Giả sử chúng ta có n trẻ em đứng trong một vòng tròn, và chúng đang chờ lấy một quả bóng bay. Việc phân phối được thực hiện bắt đầu từ con thứ k (đầu tiên ở chỉ số 0), và cho chúng một quả bóng bay để chúng rời khỏi vòng tròn. Bây giờ mỗi đứa trẻ thứ k nhận được một quả bóng bay theo chiều kim đồng hồ cho đến khi chỉ còn lại một đứa trẻ nhận được quả bóng. Vì vậy, nếu chúng ta có n và k, chúng ta phải tìm chỉ số bắt đầu của con nhận được bong bóng cuối cùng.

Vì vậy, nếu đầu vào là n =3 k =2, thì đầu ra sẽ là 1, trong vòng đầu tiên, con 2 nhận được một quả bóng bay, và rời đi vì vậy hình tròn sẽ là [0, 1]. Trong vòng thứ hai, con 0 nhận được một quả bóng bay, vòng tròn sẽ là [1].

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

• arr:=một danh sách mới từ phạm vi 0 đến n

• init:=0

• trong khi kích thước của arr> 1, thực hiện

  • remove:=(init + k) kích thước mod của arr

  • xóa arr [remove]

  • init:=remove

• return arr [0]

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

Ví dụ

class Solution:
   def solve(self, n, k):
      arr = list(range(0, n))
      init = 0
      while len(arr) > 1:
         remove = (init + k) % len(arr)
         del arr[remove]
         init = remove
      return arr[0]

ob = Solution()
n = 3
k = 2
print(ob.solve(n, k))

Đầu vào

3,2

Đầu ra

1