C++で長さと幅の差が最小になる長方形の辺を求める方法

長方形の面積が入力として与えられたとき、長さと幅の差が最小になるような長方形の辺(縦と横)を見つけるのが本記事の目的です。

長方形の面積 = 長さ × 幅

例

入力 − 面積 = 100

出力 − 差が最小の長方形の辺:

長さ = 10、幅 = 10

説明 − 面積が100になる辺の組み合わせは「2×50」「4×25」「5×20」「10×10」です。この中で差が最小なのは「10×10」で、その差は0です。正方形とはすべての辺の長さが等しい長方形のことなので、この結果は自然ですね。

入力 − 面積 = 254

出力 − 差が最小の長方形の辺:

長さ = 127、幅 = 2

説明 − 254 = 2 × 127 であり、これ以外に約数の組み合わせが存在しないため、面積254の長方形を作れる最小差の辺は「127」と「2」のみです。

プログラムで用いるアプローチ

ここでは、まず面積の平方根を求め、そこから1に向かって降順に探索していきます。平方根に近い約数のペアほど長さと幅の差が小さくなるため、条件を満たす約数が見つかった時点でそれが答えとなります。

• 整数変数 Area として面積を入力として受け取ります。

• 関数 rectangleSides(int area1) は area1 を受け取り、長さと幅の差が最小になる長方形の辺を出力します。

• 整数型の length、breadth、tmp1 を宣言します。

• tmp1 = ceil(sqrt(area1)) を設定します。

• forループ(int i = tmp1; i > 0; i--)で探索を行います。

• (area1 % i == 0)が成立した場合、length = area / i、breadth = i を設定します。

• break文でループを終了します。

• length と breadth の値を出力します。

コード例

#include <bits/stdc++.h>
using namespace std;
void rectangleSides(int area1){
    int length, breadth;
    int tmp1 = ceil(sqrt(area1));
    for (int i = tmp1; i > 0; i--) {
       if (area1 % i == 0) {

           length = ceil(area1 / i);
           breadth = i;
           break;
       }
   }
   cout<<"Sides of Rectangle with minimum difference :"<<endl;
   cout << "Length = " << length << ", Breadth = "    << breadth << endl;
}
int main(){
   int Area = 140;
   rectangleSides(Area);
   return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Sides of Rectangle with minimum difference :
Length = 14, Breadth = 10