【C++】長方形に含まれる正方形の総数を求めるアルゴリズムと実装

縦の長さL、横の幅B(L≥B)の長方形が与えられたとします。この記事では、L×Bの長方形の中にいくつの正方形が含まれているかを効率的に求める方法を解説します。

上の図は3×2の長方形の例です。この長方形には、2×2の正方形が2個、1×1の正方形が6個含まれています。

合計:6+2=8個

規則性を見つける

まず、正方形だけで構成されたB×Bの図形について考えてみましょう。

• サイズL×Bの長方形には、必ずL×B個の1×1の正方形が含まれます。
• 含まれる最大の正方形のサイズはB×Bです。
• L=B=1の場合:正方形の数=1
• L=B=2の場合:正方形の数=1+4=5(2×2が1個、1×1が4個)
• L=B=3の場合:正方形の数=1+4+9=14(3×3が1個、2×2が4個、1×1が9個)
• L=B=4の場合:正方形の数=1+4+9+16=30(4×4が1個、3×3が4個、2×2が9個、1×1が16個)

つまり、B×Bの正方形に含まれる正方形の総数は、次のようにして求められます。

for (i = 1 から B まで)
    正方形の数 += i*i;

この級数(1+4+9+…+B²)は、よく知られた公式 B(B+1)(2B+1)/6 を使えば、ループなしで一瞬にして計算することも可能です。

L>B の場合の扱い方

長方形の幅がBを超える場合(L>B)、余分な列のぶんだけ正方形が増えていきます。1列追加されるごとに新たに含まれる正方形の数は、1+2+…+B = B(B+1)/2 個です。

したがって、余分な(L−B)列によって追加される正方形の数は次の式で表せます。

(L−B) × B(B+1)/2

以上より、L×Bの長方形に含まれる正方形の総数は、次の公式で求められます。

総数 = B(B+1)(2B+1)/6 + (L−B) × B(B+1)/2

計算例

入力: L=4、B=2

出力: 長方形に含まれる正方形の数 − 11

説明: 1×1の正方形が8個、2×2の正方形が3個の合計11個です。

公式で検証すると、B(B+1)(2B+1)/6 = 2×3×5/6 = 5、(L−B)×B(B+1)/2 = 2×2×3/2 = 6 となり、5+6=11で一致します。

入力: L=3、B=3

出力: 長方形に含まれる正方形の数 − 14

説明: 1×1の正方形が9個、2×2の正方形が4個、3×3の正方形が1個の合計14個です。

プログラムのアプローチ

• 長方形の寸法として整数lengthとbreadthを受け取ります。
• 関数numofSquares(int l, int b)が寸法を受け取り、l×bの長方形に含まれる正方形の数を返します。
• 最大の正方形b×bについては、forループで1からbまで繰り返し、各i*iを合計に加算します。
• l>bの場合、新たに追加される正方形の数(l−b)×b×(b+1)/2を合計に加算します。
• 合計値を結果として返します。

注意: 常にlength ≥ breadthとなるように引数を渡してください。

C++実装例

#include<iostream>
using namespace std;
int numofSquares(int l, int b){
    int squares = 0;
    for(int i = 1; i <= b; i++) // 幅×幅の最大正方形の内部にある正方形を数える
        squares += i*i;
    squares += (l-b) * b * (b+1) / 2; // 余分な列ぶんの正方形を加算
    return squares;
}
int main(){
    int length = 5, breadth = 4; // 常にlength >= breadth となるようにする
    cout << "Count of squares is :" << numofSquares(length, breadth);
}

出力

上記のコードを実行すると、次のような出力が得られます。

Count of squares is :40

この結果は、4×4の正方形部分に含まれる30個(1+4+9+16)と、余分な1列ぶんの10個を合わせた合計40個という計算结果と一致しており、公式の正しさが確認できます。