C में शीट से काटे जा सकने वाले अधिकतम आयतों की संख्या

समस्या

एक कागज की शीट दी गई है जिसकी लंबाई L और चौड़ाई B है। एक छोटे आयत की लंबाई l और चौड़ाई b है। शीट से काटे जा सकने वाले छोटे आयतों की अधिकतम संख्या ढूंढें।

दृष्टिकोण

1. क्षैतिज संरेखण: शीट की लंबाई L को आयत की लंबाई l से, चौड़ाई B को आयत की चौड़ाई b से संरेखित करें। आयतों की गिनती करें।
2. लंबवत संरेखण: शीट की लंबाई L को आयत की चौड़ाई b से, चौड़ाई B को आयत की लंबाई l से संरेखित करें। आयतों की गिनती करें।
3. दोनों में से **अधिकतम** मान लौटाएं।

उदाहरण 1

शीट: L=18, B=6
आयत: l=4, b=3

क्षैतिज: 18/4=4, 6/3=2 → 4×2=8 आयत
लंबवत: 18/3=6, 6/4=1 → 6×1=6 आयत
अधिकतम: 8

उदाहरण 2

शीट: L=10, B=6
आयत: l=4, b=2

क्षैतिज: 10/4=2, 6/2=3 → 2×3=6 आयत
लंबवत: 10/2=5, 6/4=1 → 5×1=5 आयत
अधिकतम: 6

C प्रोग्राम

#include <stdio.h>

int maxRectangles(int L, int B, int l, int b) {
    int numh = 0, numv = 0;
    
    // क्षैतिज कटिंग
    if(l <= L && b <= B) {
        int cols = B / b;
        int rows = L / l;
        numh = rows * cols;
    }
    
    // लंबवत कटिंग
    if(l <= B && b <= L) {
        int cols = L / b;
        int rows = B / l;
        numv = rows * cols;
    }
    
    return (numh > numv) ? numh : numv;
}

int main() {
    int Length = 18, Breadth = 6;
    int len = 4, bre = 3;
    
    printf("अधिकतम आयत: %d\n", maxRectangles(Length, Breadth, len, bre));
    return 0;
}

आउटपुट

अधिकतम आयत: 8

किनारे के मामले

• यदि आयत शीट से बड़ा है: 0 लौटाता है
• यदि आयत शीट के बराबर है: 1 लौटाता है
• पूर्णांक विभाजन स्वचालित रूप से फर्श (floor) करता है

सामान्यीकरण

यदि रोटेशन की अनुमति है (90°), तो उपरोक्त दोनों ओरिएंटेशन कवर करता है। यदि मनमाना रोटेशन अनुमत है, तो समस्या बहुत अधिक जटिल हो जाती है (पैकिंग समस्या)।

जटिलता

• समय: O(1)
• स्थान: O(1)