हमें कागज की शीट के आयाम दिए गए हैं, इसकी लंबाई L और चौड़ाई B है। साथ ही, हमें एक छोटे आयत के आयाम दिए गए हैं, इसकी लंबाई l और चौड़ाई b है। लक्ष्य कागज की एक शीट से काटे जा सकने वाले छोटे आयतों की अधिकतम संख्या ज्ञात करना है।
हम निम्नलिखित कदम उठाएंगे -
-
सबसे पहले, हम क्षैतिज संरेखण, लंबाई L और l शीट और आयत क्रमशः लेंगे। L को l से और B को b से संरेखित करना शुरू करें और आयतों को गिनें।
-
फिर लंबवत संरेखण में भी ऐसा ही करें। फिर से गिनें। गिनती का अधिकतम मान लौटाएं।
आइए एक उदाहरण से समझते हैं।
इनपुट
Sheet L=18, B=6 Rectangle l=4, b=3
आउटपुट
Maximum rectangles: 8
स्पष्टीकरण
Horizontal 18/4=4 6/3=2 2*4=8 rectangles possible Vertical 18/3=6 6/4=1 6*1=6 rectangles possible Maximum rectangles here is 8
इनपुट
Sheet L=10, B=6 Rectangle l=4, b=2
आउटपुट
Maximum rectangles: 6
स्पष्टीकरण
Horizontal 10/4=2 6/2=3 2*3=6 rectangles possible Vertical 10/2=5 6/4=1 5*1=5 rectangles possible Maximum rectangles here is 6
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
चर लंबाई और चौड़ाई का उपयोग शीट के आयामों को संग्रहीत करने के लिए किया जाता है।
-
आयत के आयामों को संग्रहीत करने के लिए चर लेन और ब्रे का उपयोग किया जाता है।
-
फ़ंक्शन maxRectangles (int L, int B, int l, int b) शीट और आयत के आयाम लेता है और संभव आयतों की अधिकतम संख्या देता है।
-
चर numh और numv का उपयोग आयतों की संख्या को संग्रहीत करने के लिए किया जाता है जिन्हें क्षैतिज और लंबवत रूप से काटा जा सकता है।
-
क्षैतिज रूप से, cols=L/l और Rows=B/b, संभव आयतों, numh=cols*rows को विभाजित करें।
-
लंबवत के लिए, cols=L/b और Rows=B/l, संभव आयतों, numv=cols*rows को विभाजित करें।
-
उपरोक्त दो चरणों numh या numv में प्राप्त परिणाम के रूप में अधिकतम मान लौटाएं।
उदाहरण
#include <stdio.h>
int maxRectangles (int L, int B, int l, int b){
int numh = 0, numv = 0;
// Cut rectangles horizontally if possible
if (l <= L && b <= B){
// One rectangle is a single cell
int cols = B / b;
int rows = L / l;
// Total rectangles = total cells
numh = rows * cols;
}
// Cut rectangles vertically if possible
if (l <= B && b <= L){
int cols = L / b;
int rows = B / l;
numv = rows * cols;
}
// Return the maximum possible rectangles
return numh>numv?numh:numv;
}
// Driver code
int main (){
int Length = 18;
int Breadth =6;
int len = 4, bre = 3;
printf("Maximum rectangles: %d",maxRectangles(Length,Breadth,len,bre));
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Maximum given sized rectangles that can be cut out of a sheet of paper: 8