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

सिक्कों का भुगतान करके n तक पहुंचने के लिए आवश्यक ऑपरेशनों की संख्या गिनने के लिए C++ प्रोग्राम


मान लीजिए हमारे पास पांच संख्याएं N, A, B, C, D हैं। हम संख्या 0 से शुरू करते हैं और N पर समाप्त करते हैं। हम निम्नलिखित ऑपरेशनों द्वारा एक संख्या को कुछ सिक्कों का भुगतान करके बदल सकते हैं:

  • संख्या को 2 से गुणा करें, A सिक्कों का भुगतान करके
  • संख्या को 3 से गुणा करें, B सिक्कों का भुगतान करके
  • संख्या को 5 से गुणा करें, C सिक्कों का भुगतान करके
  • संख्या को 1 से बढ़ाएं या घटाएं, D सिक्कों का भुगतान करके।

हम इन ऑपरेशनों को किसी भी क्रम में कितनी भी बार कर सकते हैं। हमें N तक पहुंचने के लिए आवश्यक न्यूनतम सिक्कों की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट N = 11; A = 1; B = 2; C = 2; D = 8 है, तो आउटपुट 19 होगा, क्योंकि प्रारंभ में x = 0 है।

8 सिक्कों से x को 1 से बढ़ाएं (x=1)।

1 सिक्के से x को 2 से गुणा करें (x=2)।

2 सिक्कों से x को 5 से गुणा करें (x=10)।

8 सिक्कों से इसे 1 से बढ़ाएं (x=11)।

चरण

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

पूर्णांक कुंजी और मान के लिए एक मैप f परिभाषित करें पूर्णांक कुंजी और बूलियन मान के लिए एक मैप vis परिभाषित करें एक फ़ंक्शन calc परिभाषित करें, जो n लेता है यदि n शून्य है, तो: 0 वापस करें यदि n vis में है, तो: f[n] वापस करें vis[n] := 1 res := calc(n / 2) + n mod 2 * d + a यदि n mod 2 शून्येतर है, तो: res := res और calc((n / 2 + 1) + (2 - n mod 2)) * d + a का न्यूनतम res := res और calc(n / 3) + n mod 3 * d + b का न्यूनतम यदि n mod 3 शून्येतर है, तो: res := res और calc((n / 3 + 1) + (3 - n mod 3)) * d + b का न्यूनतम res := res और calc(n / 5) + n mod 5 * d + c का न्यूनतम यदि n mod 5 शून्येतर है, तो: res := res और calc((n / 5 + 1) + (5 - n mod 5)) का न्यूनतम यदि (res - 1) / n + 1 > d, तो: res := n * d f[n] = res वापस करें मुख्य विधि से, a, b, c और d सेट करें, और calc(n) कॉल करें

उदाहरण

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

#include <bits/stdc++.h> using namespace std; int a, b, c, d; map<long, long> f; map<long, bool> vis; long calc(long n){    if (!n)       return 0;    if (vis.find(n) != vis.end())       return f[n];    vis[n] = 1;    long res = calc(n / 2) + n % 2 * d + a;    if (n % 2)       res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a);    res = min(res, calc(n / 3) + n % 3 * d + b);    if (n % 3)       res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b);    res = min(res, calc(n / 5) + n % 5 * d + c);    if (n % 5)       res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c);    if ((res - 1) / n + 1 > d)       res = n * d;    return f[n] = res; } int solve(int N, int A, int B, int C, int D){    a = A;    b = B;    c = C;    d = D;    return calc(N); } int main(){    int N = 11;    int A = 1;    int B = 2;    int C = 2;    int D = 8;    cout << solve(N, A, B, C, D) << endl; }

इनपुट

11, 1, 2, 2, 8

आउटपुट

19

  1. आकार d के डोडेकागन बनाने के तरीकों की संख्या गिनने के लिए C++ प्रोग्राम आकार d के डोडेकागन बनाने के तरीकों की संख्या गिनने के लिए C++ प्रोग्राम

    मान लीजिए हमारे पास एक संख्या d है। मान लें कि भुजा लंबाई 1 के अनंत वर्गाकार टाइल्स और नियमित त्रिकोणीय टाइल्स हैं। हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम इन टाइल्स का उपयोग करके भुजा d के साथ नियमित डोडेकागन (12-भुज बहुभुज) बना सकते हैं। यदि उत्तर बहुत बड़ा है, तो परिणाम को 998244353 मॉड्यूलो

  1. C++ में बाइनरी मैट्रिक्स को शून्य मैट्रिक्स में बदलने के लिए ऑपरेशनों की गिनती करने का प्रोग्राम C++ में बाइनरी मैट्रिक्स को शून्य मैट्रिक्स में बदलने के लिए ऑपरेशनों की गिनती करने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। अब एक ऑपरेशन पर विचार करें जहां हम एक सेल लेते हैं और उसे और उसके सभी पड़ोसी सेल्स (ऊपर, नीचे, बाएं, दाएं) को फ्लिप करते हैं। हमें ऑपरेशनों की न्यूनतम संख्या ढूंढनी है जैसे कि मैट्रिक्स में केवल 0 हों। यदि कोई समाधान नहीं है, तो -1 वापस करें। तो, यदि इनप

  1. - C++ में दी गई संख्या को कम करने के लिए आवश्यक ऑपरेशन्स की संख्या गिनना

    हमें एक धनात्मक पूर्णांक K और एक सरणी Ops[] दी गई है जिसमें पूर्णांक हैं। लक्ष्य K को कम करने के लिए आवश्यक ऑपरेशन्स की संख्या ढूंढना है ताकि यह 0 से कम हो जाए। ऑपरेशन्स हैं - पहला ऑपरेशन K + Ops[0] है, पहला तत्व K में जोड़ा जाता है। इसके बाद Ops[i] को K में तब तक जोड़ते हैं जब तक K < 0 न हो जाए। ज