【C言語】1枚の紙から切り出せる指定サイズの長方形の最大数を求める方法

ここでは、紙の寸法(長さL、幅B)と、そこから切り出したい小さな長方形の寸法(長さl、幅b)が与えられたとき、1枚の紙から切り出すことができる長方形の最大数を求める問題を解説します。

この問題は、以下の手順で解くことができます。

• まず水平方向の配置を考えます。紙の長さLに対して長方形の長さl、紙の幅Bに対して長方形の幅bを対応させて並べ、切り出せる長方形の数を数えます。

• 次に垂直方向の配置(長方形を90度回転させた場合)でも同様に計算し、数を数えます。

• 最後に、2つの配置パターンで得られた数のうち、大きい方の値を答えとして返します。

具体例で確認してみましょう。

入力

紙: L=18, B=6 / 長方形: l=4, b=3

出力

Maximum rectangles: 8

説明

水平方向: 18/4=4、6/3=2 → 4×2=8個 切り出し可能
垂直方向: 18/3=6、6/4=1 → 6×1=6個 切り出し可能
最大数は 8 個

入力

紙: L=10, B=6 / 長方形: l=4, b=2

出力

Maximum rectangles: 6

説明

水平方向: 10/4=2、6/2=3 → 2×3=6個 切り出し可能
垂直方向: 10/2=5、6/4=1 → 5×1=5個 切り出し可能
最大数は 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 を計算します。

• 上記2つの計算結果 numh と numv のうち、大きい方を結果として返します。

実装例(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;
   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

このように、水平方向と垂直方向の2つの配置パターンを比較するだけで、効率的に最大切り出し数を求めることができます。計算量は O(1) と非常にシンプルであり、整数除算による切り捨てが余りの部分を自動的に無視してくれる点もポイントです。