पायथन में भारतीय संप्रदायों का उपयोग करके n R.s प्राप्त करने के कई तरीकों को खोजने के लिए कार्यक्रम

मान लीजिए कि हमारे पास सीमित मूल्यवर्ग के सिक्के हैं (₹1, ₹2, ₹5 और ₹10)। हमें यह पता लगाना है कि आप उन्हें कितने तरीकों से कुल ₹n तक जोड़ सकते हैं? हमारे पास आकार 4 की एक सरणी संख्या है, जहां गिनती [0] ₹1 के सिक्कों को इंगित करती है, गिनती [1] ₹2 के सिक्कों को इंगित करती है और इसी तरह।

इसलिए, यदि इनपुट n =25 काउंट =[7,3,2,2] जैसा है, तो आउटपुट 9 होगा।

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

• संप्रदाय :=[1,2,5,10]
• A :=आकार की एक सरणी (n + 1) और 0 से भरें
• B :=A से एक नई सूची
• मैं के लिए 0 से (न्यूनतम गिनती [0] और n) की सीमा में, करते हैं
  • ए[i] :=1
• 1 से 3 के बीच के लिए, करें
  • जे के लिए रेंज 0 से गिनने के लिए[i], करें
    • के लिए 0 से n + 1 - j *denom[i] की श्रेणी में, do
      • B[k + j * denom[i]] :=B[k + j * denom[i]] + A[k]
  • जे के लिए 0 से n की सीमा में, करें
    • ए[जे]:=बी[जे]
    • बी[जे] :=0
• वापसी A[n]

उदाहरण

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

denom = [1,2,5,10]
def solve(n, count):
   A = [0] * (n + 1)
   B = list(A)
   for i in range(min(count[0], n) + 1):
      A[i] = 1
   for i in range(1, 4):
      for j in range(0, count[i] + 1):
         for k in range(n + 1 - j *denom[i]):
            B[k + j * denom[i]] += A[k]
      for j in range(0, n + 1):
         A[j] = B[j]
         B[j] = 0
   return A[n]

n = 25
count = [7,3,2,2]
print(solve(n, count))

इनपुट

25, [7,3,2,2]

आउटपुट

9