पायथन में भारतीय मूल्यवर्ग का उपयोग करके n रुपये प्राप्त करने के तरीकों की संख्या खोजने का प्रोग्राम

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

तो, यदि इनपुट n = 25, count = [7,3,2,2] है, तो आउटपुट 9 होगा।

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

• denom := [1,2,5,10]
• A := आकार (n + 1) की एक सरणी जिसे 0 से भरा गया है
• B := A से एक नई सूची
• i को 0 से (count[0] और n के न्यूनतम) तक की रेंज में, करें
  • A[i] := 1
• i को 1 से 3 तक की रेंज में, करें
  • j को 0 से count[i] तक की रेंज में, करें
    • k को 0 से n + 1 - j *denom[i] तक की रेंज में, करें
      • B[k + j * denom[i]] := B[k + j * denom[i]] + A[k]
  • j को 0 से n तक की रेंज में, करें
    • A[j] := B[j]
    • B[j] := 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