C言語で直角二等辺三角形に収まる2×2正方形の最大個数を求める方法

問題の概要

本記事では、直角二等辺三角形を扱います。二等辺三角形とは、2つの辺が同じ長さを持つ三角形のことであり、直角三角形とは、高さ(図中の ag)と底辺(図中の dg)が互いに垂直に交わっている三角形のことです。ここでの目標は、一辺が2単位の正方形が、この直角二等辺三角形の中に最大でいくつ収まるのかを求めることです。底辺と高さ(両者は等しい値)を入力として受け取り、収まる正方形の個数を出力します。

まず、下の図を参考にして問題を理解しましょう。

幾何的な考察

高さ ag・底辺 gd を持つこの三角形には、一辺2の正方形が3個収まっています。注目すべきは、角の頂点「a」と「d」に接する三角形 aib および cde の部分です。この2つの領域には、どのように配置しても正方形を置くことができません。したがって、まず最初に角の部分のために2単位の余分な長さを確保しておく必要があります。そのうえで、残りの底辺 gd(または高さ ag)を2で割れば、正方形の個数を数えられます。高さ方向についてもまったく同じ考え方が適用できます。

この手順を擬似コードで表すと、次のようになります。

while(base > 2)
   squares += (base - 2) / 2
   base = base - 2
等差数列の和の公式 Ap = b * (b + 1) / 2 を利用 …(新しい b = b - 2)

具体例で確認しよう

入力 − 底辺: 12

出力 − 正方形の個数: 15

説明

base 12>2, squares 10/2=5, 新しい base 12-2=10
base 10>2, squares 8/2=4, 新しい base 10-2=8
base 8>2, squares 6/2=3, 新しい base 8-2=6
base 6>2, squares 4/2=2, 新しい base 6-2=4
base 4>2, squares 2/2=1, 新しい base 4-2=2
base 2>2 X 合計 = 5+4+3+2+1 = 15

入力 − 底辺: 5

出力 − 正方形の個数: 1

説明

base 5>2, squares 3/2=1, 新しい base 5-2=3
base 3>2, squares 1/2=0, 新しい base 3-2=1
base 1>2 X 合計 = 1

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

• 整数型変数 base に、三角形の底辺の長さを格納します。

• 関数 numofSquares(int b) は、底辺 b の三角形に収められる正方形の個数を計算します。

• まず b = b - 2 として、両端の角の部分に必要な余分な領域を差し引きます。

• 続いて b = floor(b / 2) とします。この新しい b に対して、一辺2の正方形は b × (b + 1) / 2 個だけ配置できます。

• 最後に、計算結果を正方形の個数として返します。

なぜ b × (b + 1) / 2 という式になるのかというと、三角形の内部では上の段から順に b 個、b−1 個、…、1 個と正方形が並んでいくため、その総和は初項1・末項 b の等差数列の和、すなわち b(b+1)/2 で表せるからです。

サンプルコード(C言語)

#include <stdio.h>
#include <math.h>
int numofSquares(int b){
   // 角の部分の余分な領域を取り除く
   // この処理は常に必要となります
   b = (b - 2);
   // 各正方形の底辺の長さは2であるため
   b = floor(b / 2);
   return b * (b + 1) / 2;
}
int main(){
   int base = 8;
   printf("収容できる正方形の最大数 : %d", numofSquares(base));
   return 0;
}

実行結果

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

収容できる正方形の最大数 : 6

このように、底辺から角の余白分の2を差し引き、2で割った値に対して等差数列の和の公式を適用するだけで、O(1) の定数時間で答えを求めることができます。ループで一つずつ数えていく方法よりも、はるかに効率的なアルゴリズムです。