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

C++ में माचिस की तीलियों से वर्ग बनाना


मान लीजिए एक छोटी माचिस वाली लड़की है। और हम ठीक से जानते हैं कि छोटी माचिस वाली लड़की के पास कौन सी माचिस की तीलियां हैं, हमें एक रास्ता ढूंढना है जिससे हम उन सभी माचिस की तीलियों का उपयोग करके एक वर्ग बना सकें। हमें किसी भी छड़ी को नहीं तोड़ना चाहिए, लेकिन हम उन्हें जोड़ सकते हैं, और प्रत्येक माचिस की तीली का उपयोग ठीक एक बार किया जाना चाहिए। हमारा इनपुट लड़की के पास मौजूद कई माचिस की तीलियां होंगी, जो उनकी छड़ी की लंबाई से दर्शाई गई हैं। हमारा आउटपुट या तो true या false होगा, यह दर्शाने के लिए कि क्या हम माचिस वाली लड़की की सभी माचिस की तीलियों का उपयोग करके एक वर्ग बना सकते हैं। इसलिए यदि इनपुट [1,1,2,2,2] है, तो उत्तर true होगा, क्योंकि हम लंबाई 2 का एक वर्ग बना सकते हैं, एक तरफ लंबाई 1 की दो छड़ें होंगी।

हल का दृष्टिकोण

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

  • solve() नामक एक पुनरावर्ती विधि परिभाषित करें। यह इंडेक्स, sums सरणी, target, और nums सरणी लेगी। यह निम्नानुसार काम करेगा:
    • यदि इंडेक्स >= nums आकार, तो:
      • यदि sums[0], sum[1] और sum[2] सभी target के समान हैं तो true लौटाएं
    • i = 0 से 3 तक:
      • यदि sums[i] + nums[इंडेक्स] > target, तो लूप के अगले भाग को छोड़ें
      • sums[i] := sums[i] + nums[इंडेक्स]
      • यदि solve(इंडेक्स+1, sums, target, nums) true है, तो true लौटाएं
      • sums[i] := sums[i] - nums[इंडेक्स]
    • false लौटाएं
  • मुख्य विधि से, निम्नलिखित करें:
    • यदि nums में कोई तत्व नहीं है, तो false लौटाएं
    • x := 0
    • i = 0 से nums का आकार तक, x को nums[i] से बढ़ाएं
    • यदि x, 4 से विभाज्य है, तो false लौटाएं
    • nums सरणी को क्रमबद्ध करें
    • आकार 4 की एक सरणी sums बनाएं
    • solve(0, sum, x/4, nums) लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    bool solve(int idx, vector<int>& sums, int target, vector<int>& nums){ 
        if(idx >= nums.size()){ 
            return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == target; 
        } 
        for(int i = 0; i < 4; i++){ 
            if(sums[i] + nums[idx] > target) continue; 
            sums[i] += nums[idx]; 
            if(solve(idx + 1, sums, target, nums)) return true; 
            sums[i] -= nums[idx]; 
        } 
        return false; 
    } 
    bool makesquare(vector<int>& nums) { 
        if(nums.size() == 0) return false; 
        int x = 0; 
        for(int i = 0; i < nums.size(); i++){ 
            x += nums[i]; 
        } 
        if(x % 4) return false; 
        sort(nums.rbegin(), nums.rend()); 
        vector<int> sum(4); 
        return solve(0, sum, x / 4, nums); 
    } 
}; 

int main(){ 
    vector<int> v = {1,1,2,2,2}; 
    Solution ob; 
    cout << (ob.makesquare(v)); 
}

इनपुट

[1,1,2,2,2]

आउटपुट

1

  1. C++ में वर्ग के परिवृत्त का क्षेत्रफल C++ में वर्ग के परिवृत्त का क्षेत्रफल

    इस समस्या में, हम वर्ग के परिवृत्त का क्षेत्रफल गणना करेंगे जब हमें वर्ग की भुजा दी गई हो। आगे बढ़ने से पहले आइए मूल परिभाषाओं को दोहराते हैं ताकि अवधारणाओं को बेहतर ढंग से समझा जा सके। वर्ग समान भुजाओं वाला एक चतुर्भुज है। परिवृत्त एक वृत्त है जो बहुभुज के सभी शीर्षों को छूता है। क्षेत्रफल किसी भी

  1. - C++ में NaN क्या है?

    NaN (Not a Number) की परिभाषा NaN Not a Number का संक्षिप्त रूप है। यह अपरिभाषित या गैर-प्रतिनिधित्व योग्य फ्लोटिंग-पॉइंट एलिमेंट्स को इंगित करता है। NaN का एक उदाहरण किसी ऋणात्मक संख्या का वर्गमूल है, या 0/0 का परिणाम। उदाहरण #include <iostream> #include <cmath> using namespace std; i

  1. - C++ में void फ़ंक्शन्स से रिटर्न

    void फ़ंक्शन्स को void कहा जाता है क्योंकि वे कुछ भी वापस नहीं करते हैं। एक void फ़ंक्शन कुछ भी वापस नहीं कर सकता यह कथन हमेशा सच नहीं है। एक void फ़ंक्शन से, हम कोई मान वापस नहीं कर सकते, लेकिन हम मान के अलावा कुछ वापस कर सकते हैं। उनमें से कुछ नीचे दिए गए हैं। एक void फ़ंक्शन रिटर्न कर सकता है एक