สี่เหลี่ยมขนาดสูงสุดที่กำหนดที่สามารถตัดออกจากกระดาษหนึ่งแผ่นใน C

เราได้รับขนาดของแผ่นกระดาษ มันคือความยาว 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.

• ส่งคืนค่าสูงสุดตามผลลัพธ์ที่ได้รับในสองขั้นตอนข้างต้น 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