আমাদের কাগজের শিটের ডাইমেনশন দেওয়া আছে, এর দৈর্ঘ্য 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
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি
Length এবং Breadth ভেরিয়েবল শিটের ডাইমেনশন সংরক্ষণ করে।
len এবং bre ভেরিয়েবল রেক্ট্যাঙ্গেলের ডাইমেনশন সংরক্ষণ করে।
ফাংশন 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।
উপরের দুটি ধাপ থেকে প্রাপ্ত সর্বোচ্চ মান ফলাফল হিসেবে রিটার্ন করুন।
উদাহরণ
#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
