"गेम को खत्म करने" के लिए एक कुशल एल्गोरिथ्म का निर्माण

Question

मैं इस एलिमिनेशन गेम की समस्या को हल कर रहा था ।

पहले, मैंने पाशविक बल द्वारा कोशिश की;

• दूरी के साथ शुरू से संख्या को समाप्त कर दिया $2$ (यानी अगले एक के बाद तत्व)
• सूची को उलट दिया
• दूरी के साथ शुरू से संख्या को समाप्त कर दिया $2$
• सूची को उलट दिया गया ...

अंत में, अंतिम शेष तत्व वापस कर दिया। हालांकि, आश्चर्यजनक रूप से, यह "टाइम लिमिट एक्साइटेड" नहीं हुआ।

यहाँ इसके लिए पायथन कोड दिया गया है:

def lastRemaining(n: int) -> int:
        nums = [i for i in range(1, n + 1)]
        l = len(nums)
        while l != 1:
            for i in range(0, len(nums), 1):
                if i < len(nums): 
                    nums.remove(nums[i])
                    l -= 1
            nums.reverse()
        return nums[0]

फिर, मैंने एक बेहतर समाधान खोजा और निम्नलिखित पाया:

def lastRemaining(n: int) -> int:
        if n == 1: return 1
        return (n//2 - lastRemaining(n//2) + 1) * 2

और यह काम करता है। यह गणितीय रूप में लिखा गया है$$ f(n) = \begin{cases} 1, \text{ if } n=1, \\ 2\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor - f\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor\right) + 1\right), \text{ otherwise } \end{cases} $$ मैंने इसे कुछ मानों के लिए सत्यापित किया है $n$। बहरहाल, मुझे यह साबित करने में मदद चाहिए कि यह एल्गोरिथ्म हर मामले के लिए काम करता है।

किसी भी मदद की सराहना की है।

Answer 1

पहला मामला $n=1$ज़ाहिर है। दूसरे मामले के लिए, ध्यान दें कि आप जो कर रहे हैं वह मूल रूप से पहला चलना है और शेष पर समस्या को हल करना है (जो है)$2, 4, 6, ... 2⌊n/2⌋$) - हां तकरीबन। आप इसे रिवर्स ऑर्डर में करते हैं, यही वजह है कि आपके पास है$⌊n/2⌋-f(⌊n/2⌋)+1$ की बजाय $f(⌊n/2⌋)$यहां, ध्यान दें कि आप वास्तव में "अंतिम संख्या" के आदेश को वापस कर रहे हैं और इसके मूल्य को नहीं, जो मूल समस्या में समतुल्य होगा। इसलिए हम गुणा करते हैं$2$ अंत में "अंतिम संख्या" का मूल्य प्राप्त करने के लिए जिसे हम आदेश जानते हैं।