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

पायथन में अजॉब अनुक्रम से अनुक्रम चुनने के तरीकों की संख्या खोजने का प्रोग्राम


मान लीजिए एक अजीब भाषा है जिसे अजॉब भाषा कहते हैं। इसमें अनंत संख्या में अक्षर हैं। हम इस भाषा में n शब्द जानते हैं। पहला शब्द एक अक्षर लंबा है, दूसरा दो अक्षर लंबा है और इसी तरह। और एक शब्द के सभी अक्षर अद्वितीय हैं। यदि हम n शब्दों में से किसी एक को चुनते हैं और उससे एक सबसीक्वेंस बनाते हैं। सबसीक्वेंस की लंबाई मूल शब्द की लंबाई से k कम होनी चाहिए। उदाहरण के लिए, यदि चुने गए शब्द की लंबाई L है, तो सबसीक्वेंस की लंबाई (L - k) होनी चाहिए। यदि k से छोटी लंबाई वाला कोई शब्द है, तो आपको वह शब्द नहीं चुनना चाहिए। और दो सबसीक्वेंस एक-दूसरे से भिन्न होते हैं जब उनकी लंबाई भिन्न होती है या उनमें समान स्थिति पर अलग-अलग वर्ण होते हैं। हमें परिणाम मॉड्यूलो p खोजना है, और p एक अभाज्य संख्या है।

तो, यदि इनपुट n = 6, k = 5, p = 11 है, तो आउटपुट 7 होगा।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

  • एक खाली डिक्शनरी memo बनाएं
  • n := n + 1, k := k + 1
  • fact := एक तत्व 1 वाली सूची
  • i को 1 से p - 1 तक की रेंज में, करें
    • (fact के अंतिम तत्व * i mod p) को fact के अंत में डालें
  • यदि p, memo में मौजूद है, तो
    • inv_fact := memo[p]
  • अन्यथा,
    • inv := दो तत्वों 0 और 1 वाली सूची
    • i को 2 से p - 1 तक की रेंज में, करें
      • (p - p/i के फ्लोर * inv[p mod i] mod p) को inv के अंत में डालें
    • inv_fact := एक तत्व 1 वाली सूची
    • i को 1 से p - 1 तक की रेंज में, करें
      • (inv_fact के अंतिम तत्व * inv[i] mod p) को inv_fact के अंत में डालें
    • memo[p] := inv_fact
  • ret := 1
  • जब तक n > 0, करें
    • n1 := n mod p
    • k1 := k mod p
    • यदि k1 > n1, तो
      • 0 लौटाएं
    • ret := ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] mod p
    • n := n/p का फ्लोर
    • k := k/p का फ्लोर
  • ret लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

memo = {} def solve(n, k, p): n += 1 k += 1 fact = [1] for i in range(1, p): fact.append(fact[-1] * i % p) if p in memo: inv_fact = memo[p] else: inv = [0, 1] for i in range(2, p): inv.append(p - p // i * inv[p % i] % p) inv_fact = [1] for i in range(1, p): inv_fact.append(inv_fact[-1] * inv[i] % p) memo[p] = inv_fact ret = 1 while n > 0: n1 = n % p k1 = k % p if k1 > n1: return 0 ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p n //= p k //= p return ret n = 6 k = 5 p = 11 print(solve(n, k, p))

इनपुट

6, 5, 11 

आउटपुट

7

  1. - पायथन में संदेश को डिकोड करने के तरीकों की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास a = 1, b = 2, ... z = 26 जैसा मैपिंग है, और हमारे पास एक एन्कोडेड संदेश message स्ट्रिंग है, हमें उन तरीकों की संख्या गिननी है जिनसे इसे डिकोड किया जा सकता है। उदाहरण के लिए, यदि इनपुट message = 222 है, तो आउटपुट 3 होगा, क्योंकि इसे 3 तरीकों से डिकोड किया जा सकता है: bbb, bv, और

  1. - पायथन में अधिकतम सिक्के एकत्र करने का प्रोग्राम

    मान लीजिए हमारे पास एक 2D मैट्रिक्स है जहां प्रत्येक सेल कुछ सिक्के संग्रहीत करता है। यदि हम [0,0] से शुरू करते हैं, और केवल दाएं या नीचे जा सकते हैं, तो हमें नीचे-दाएं कोने तक पहुंचने तक एकत्र किए जा सकने वाले अधिकतम सिक्कों की संख्या ढूंढनी है। उदाहरण के लिए, यदि इनपुट है: 1422 6005 तो आउटपुट

  1. - पायथन में सीढ़ियां चढ़ने के तरीकों की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास n चरणों वाली एक सीढ़ी है, और हम एक बार में 1 या 2 चरण चढ़ सकते हैं। हमें एक फ़ंक्शन परिभाषित करना है जो सीढ़ी चढ़ने के अद्वितीय तरीकों की संख्या लौटाता है। चरणों का क्रम नहीं बदला जाना चाहिए, इसलिए चरणों का प्रत्येक अलग क्रम एक तरीका गिना जाता है। यदि उत्तर बहुत बड़ा है तो परिणा