Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में अंतिम गुब्बारा प्राप्त करने वाले बच्चे का प्रारंभिक सूचकांक ढूंढने का प्रोग्राम

n बच्चे एक वृत्त में खड़े हैं (सूचकांक 0 से n-1)। वितरण k-वें बच्चे से शुरू होता है (पहला सूचकांक 0)। हर k-वें बच्चे को गुब्बारा मिलता है और वह वृत्त छोड़ देता है। अंतिम गुब्बारा पाने वाले बच्चे का प्रारंभिक सूचकांक ढूंढें।

उदाहरण

इनपुट: n = 3, k = 2

आउटपुट: 1

चरण: बच्चे [0,1,2]। सूचकांक 2 (k=2) हटता है → [0,1]। अगला सूचकांक 0 हटता है → [1]। अंतिम = 1।

एल्गोरिदम (सिमुलेशन)

  1. arr = list(range(n)) बनाएं।
  2. init = 0 (वर्तमान प्रारंभ सूचकांक)।
  3. जब तक len(arr) > 1:
    • remove = (init + k) % len(arr)
    • del arr[remove]
    • init = remove (अगली गिनती यहीं से शुरू होती है)।
  4. arr[0] वापस करें।

पायथन कार्यान्वयन

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

# परीक्षण
ob = Solution()
print(ob.solve(3, 2))   # 1
print(ob.solve(5, 3))   # 3
print(ob.solve(7, 3))   # 3

जोसेफस समस्या संबंध

यह क्लासिक जोसेफस समस्या का रूपांतर है। मानक जोसेफस में कदम k-1 होता है (0-आधारित)। यहां k कदम है। पुनरावृत्ति संबंध:


J(1, k) = 0
J(n, k) = (J(n-1, k) + k) % n

लेकिन यहां k के बजाय k+1 प्रभावी कदम है क्योंकि गिनती वर्तमान से शुरू होती है।

O(n) गणितीय समाधान


def josephus(n, k):
    res = 0
    for i in range(2, n + 1):
        res = (res + k) % i
    return res

इस समस्या के लिए k को k+1 से बदलें।

समय जटिलता

  • सिमुलेशन: O(n²) (सूची हटाने के कारण)।
  • गणितीय: O(n) समय, O(1) स्थान।
  1. Python प्रोग्राम में ऐरे का योग खोजना Python प्रोग्राम में ऐरे का योग खोजना

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक ऐरे दिया गया है, हमें ऐरे का योग निकालने की आवश्यकता है। पूरे ऐरे को पार करने और प्रत्येक इंडेक्स पर तत्व को जोड़कर योग प्राप्त करने का ब्रूट-फोर्स दृष्टिकोण नीचे चर्चा किया गया है। उदाहरण # sum फ़ंक्शन def

  1. पायथन प्रोग्राम: मैट्रिक्स का ट्रांसपोज़ ढूंढें पायथन प्रोग्राम: मैट्रिक्स का ट्रांसपोज़ ढूंढें

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट एक मैट्रिक्स दिए जाने पर, हमें ट्रांसपोज़ को उसी मैट्रिक्स में स्टोर करना होगा और इसे प्रदर्शित करना होगा। मैट्रिक्स का ट्रांसपोज़ पंक्तियों को कॉलम में और कॉलम को पंक्तियों में बदलकर

  1. पायथन प्रोग्राम: ऐरे का योग ढूंढें पायथन प्रोग्राम: ऐरे का योग ढूंढें

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट इनपुट के रूप में एक ऐरे दिए जाने पर, हमें दिए गए ऐरे का योग निकालने की आवश्यकता है। यहां हम ब्रूट-फोर्स दृष्टिकोण का पालन कर सकते हैं यानी एक लिस्ट को ट्रैवर्स करना और प्रत्येक एलिमें