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

एक संख्या बनाने के लिए जोड़े गए पूर्ण वर्गों की संख्या गिनने का प्रोग्राम C++ में


मान लीजिए हमारे पास एक धनात्मक संख्या n है, हमें उन पूर्ण वर्ग संख्याओं की न्यूनतम संख्या ढूंढनी है जिनका योग n के समान हो। इसलिए यदि संख्या 10 है, तो आउटपुट 2 है, क्योंकि संख्याएं 10 = 9 + 1 हैं।

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

  • डायनामिक प्रोग्रामिंग के लिए एक टेबल बनाएं, लंबाई n + 1 की, और इसे अनंत से भरें
  • dp[0] := 0
  • i := 1 के लिए, जब i*i <= n
    • x = i * i
    • j := x से n तक
      • dp[j] := dp[j] और 1 + dp[j - x] का न्यूनतम
  • dp[n] लौटाएं

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

उदाहरण

#include<bits/stdc++.h> using namespace std; #define INF 1e9 class Solution { public:    int solve(int n) {       vector < int > dp(n+1,INF);       dp[0] = 0;       for(int i =1;i*i<=n;i++){          int x = i*i;          for(int j = x;j<=n;j++){             dp[j] = min(dp[j],1+dp[j-x]);          }       }       return dp[n];    } }; main(){    Solution ob;    cout << ob.solve(10); }

इनपुट

10

आउटपुट

2

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

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

  1. C++ में आयत में वर्गों की संख्या गिनना C++ में आयत में वर्गों की संख्या गिनना

    =B। लक्ष्य LxB आकार के आयत में समायोजित किए जा सकने वाले वर्गों की संख्या ढूंढना है। उपरोक्त आकृति 3x2 आकार के एक आयत को दर्शाती है। इसमें 2, 2x2 वर्ग और 6, 1x1 वर्ग हैं। कुल वर्ग = 6+2=8। LxB आकार के हर आयत में L*B संख्या के 1x1 वर्ग होते हैं। सबसे बड़े वर्ग BxB आकार के होते हैं। L=B=1 के लिए, वर

  1. - C++ में ऑलमोस्ट परफेक्ट नंबर

    ऑलमोस्ट परफेक्ट नंबर को कम से कम कमी वाली संख्या या थोड़ी दोषपूर्ण संख्या के रूप में भी जाना जाता है, यह एक संख्या है जिसमें सभी भाजकों का योग (1 और संख्या को स्वयं जोड़कर) 2n-1 के बराबर होना चाहिए। इस समस्या में, हम एक एल्गोरिदम परिभाषित करेंगे कि क्या कोई संख्या ऑलमोस्ट परफेक्ट नंबर है या नहीं। आइ