โปรแกรมหาดัชนีเริ่มต้นของเด็กที่ได้บอลลูนตัวสุดท้ายใน Python

สมมติว่ามีเด็ก n คนยืนวงกลม รอรับบอลลูน การแจกเริ่มจากเด็กคนที่ k (ดัชนีเริ่มจาก 0) เด็กที่ได้บอลลูนจะออกจากวงกลม แล้วต่อไปทุกคนที่ k จะได้บอลลูน ตามทิศทางเข็มนาฬิกา จนเหลือเด็กคนสุดท้าย หาดัชนีเริ่มต้นของเด็กคนนั้น

ตัวอย่าง

อินพุต: n = 3, k = 2

เอาต์พุต: 1

รอบแรก: เด็ก 2 ได้บอลลูน ออก วงกลมเหลือ [0,1] รอบที่สอง: เด็ก 0 ได้บอลลูน ออก เหลือ [1]

ขั้นตอนการแก้ปัญหา

จำลองกระบวนการโดยตรง (Josephus problem variant):

1. arr = list(range(n))
2. init = 0
3. วนลูป while len(arr) > 1:
   • remove = (init + k) % len(arr)
   • del arr[remove]
   • init = remove
4. คืนค่า arr[0]

การนำไปใช้ใน Python

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))

อินพุต

3, 2

เอาต์พุต

1