C++で直角二等辺三角形に収まる正方形の最大数を求める方法

この記事では、底辺の長さが「s」である直角二等辺三角形の中に、一辺「a」の正方形を最大でいくつ収めることができるかを求める問題を解説します。二等辺三角形とは、少なくとも2つの等しい辺を持つ三角形のことです。

まず、具体例を使って何をすべきかを理解しましょう。

入力例

s=5, a=1

出力

10

説明 − 底辺に並べられる正方形の数は、「s を a で割って 1 を引く」ことで求められます。つまり、底辺の正方形の数 = 5/1 − 1 = 4 個です。

同様に、最下段に4つの正方形を配置すると、その上に底辺が (s−a) の新しい二等辺三角形ができます。同じ手順を繰り返すと3個、さらにその上に2個と続き、最終的に頂点に1個の正方形が置かれるまで続きます。

入力例

s=7, a=2

出力

3

プログラムのアプローチ

• 正方形の最大数を求めるには、三角形の底辺から順に各段の正方形の数を数えていきます。

• ある段に並ぶ正方形の数は、底辺 s を正方形の一辺 a で割り、1 を引いた値、すなわち s/a − 1 となります。

• その上には、底辺が (s − a) の別の二等辺三角形が残ります。この段には前の段より1つ少ない正方形が収まります。これは次のように計算できます −

次の段の正方形の数 = (s − a)/a − 1 = (s/a − a/a) − 1 = s/a − 1 − 1 = s/a − 2 = 前の段より1つ少ない。

• 正方形の数は1に達するまで段ごとに減少していきます。したがって、底辺の段の正方形の数 n を求めれば、自然数の和の公式を使って全体の合計を一度に計算できます −

(n) * (n + 1) / 2

この場合、n = (s / a) − 1 となるため、公式は次のようになります − ((s / a) − 1) * (s / a) / 2

コード例

#include<bits/stdc++.h>
using namespace std;
int Max(int s, int a){
   // 最大正方形数を計算する公式
   return ((s / a) - 1) * (s / a) / 2;
}
// メイン関数
int main(){
   int s = 5, a = 1;
   cout <<"Maximum squares possible are: "<<Max(s,a);
   return 0;
}

出力

10