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

C++ में परफेक्ट स्क्वेयर्स


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

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

  • डायनामिक प्रोग्रामिंग के लिए एक टेबल बनाएं, लंबाई 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 numSquares(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.numSquares(147)); }

इनपुट

147

आउटपुट

3

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

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

  1. - C++ में ग्रिड में मैजिक स्क्वेयर की गणना करें

    हमें संख्याओं का एक मैट्रिक्स दिया गया है। लक्ष्य दिए गए मैट्रिक्स के अंदर मौजूद मैजिक स्क्वेयर की संख्या ढूंढना है। एक मैजिक स्क्वेयर, यदि मैट्रिक्स के रूप में लिया जाए, तो एक 3x3 मैट्रिक्स है जिसमें 1 से 9 तक के तत्व होते हैं जैसे सुडोकु में ग्रिड। गुण हैं: सभी संख्याएं ठीक एक बार होती हैं। मैट्र

  1. C++ में बोर्ड को वर्गों में काटने की न्यूनतम लागत C++ में बोर्ड को वर्गों में काटने की न्यूनतम लागत

    अवधारणा मान लीजिए लंबाई p और चौड़ाई q का एक बोर्ड दिया गया है, हमें इस बोर्ड को p*q वर्गों में तोड़ना है ताकि तोड़ने की लागत न्यूनतम हो। इस बोर्ड के लिए, प्रत्येक किनारे के लिए काटने की लागत दी जाएगी। संक्षेप में, हमें काटने का ऐसा क्रम चुनना है जिससे लागत न्यूनतम हो। उदाहरण उपरोक्त बोर्ड को वर्गो