Python में सीढ़ियों का उपयोग करके अगली मंजिल तक पहुंचने के तरीकों की संख्या खोजने का प्रोग्राम

मान लीजिए N चरणों वाली एक सीढ़ी है। कोई या तो चरण दर चरण जा सकता है, या प्रत्येक चरण पर, कोई अधिकतम N चरणों की छलांग लगा सकता है। हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम शीर्ष मंजिल तक जा सकते हैं। N मान बड़ा हो सकता है हम केवल तरीकों की संख्या के पहले और अंतिम K अंकों में रुचि रखते हैं।

तो, यदि इनपुट N = 10, k = 2 है, तो आउटपुट 63 होगा क्योंकि 10 चरण हैं, यदि S शीर्ष तक जाने के तरीकों की संख्या है, तो S को wxyz के रूप में मानें। तो, wx + yz का योग 63 है।

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

N := N - 1
c := 2 * ceiling of (k + log(N);base10)
e := N, b := 2, s := 1
जब e > 0, करें
- यदि e विषम है, तो
  - s := (s*b) के पहले p-c अंक जहां p, s*b में अंकों की संख्या है
- e := floor of e/2
- b := (b*b) के पहले p-c अंक जहां p, b*b में अंकों की संख्या है
s := s के पहले p - k अंक, जहां p, s में अंकों की संख्या है
r := s + (2^N) mod 10^k
r वापस करें

उदाहरण

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

from math import log10,ceil def solve(N,k): N -= 1 c = 2*ceil(k + log10(N)) e = N b = 2 s = 1 while e > 0: if e % 2 == 1: s = int(str(s*b)[:c]) e //=2 b = int(str(b*b)[:c]) s = str(s)[:k] r = int(s) + pow(2, N, 10**k) return r N = 10 k = 2 print(solve(N,k))

इनपुट

10, 2