C++で正三角形に内接する異なる長方形の数を求める方法

問題概要

一辺の長さが与えられた正三角形を考えます。この記事の目的は、水平な2辺が底辺と平行になるように三角形の内部へ配置できる「異なる長方形」の総数を数えることです。ただし、長方形の4つの頂点はすべて、図に示された点(格子点)に一致していなければなりません。

入出力例

入力 − sides=3

出力 − 正三角形に内接する異なる長方形の数:1

説明 − 上の図は条件を満たす長方形を示しています。

入力 − sides=10

出力 − 正三角形に内接する異なる長方形の数:200

アルゴリズムの考え方

図から分かるように、長方形の水平な辺は、一段おきのレベルにある点同士を結ぶ形になります。そのため、点の数はレベル0−1、レベル1−2、…、レベルn−(n+1)というように段階的に数えていくことができます。

• 辺の長さを整数変数として受け取り、計算処理を行う関数へ渡します。
• 一時変数として count(答え)、temp、check を用意します。
• sides が奇数の場合、i を sides−2 から始めて 1 になるまで減らしながらループします。
• ループ内で i が奇数(i & 1 が真)なら、temp を (sides − i) / 2、check を (i × (i + 1)) / 2 とし、count に check × temp を加算します。i が偶数なら、temp を ((sides − 1) − i) / 2、check を (i × (i + 1)) / 2 とし、同様に count へ加算します。
• sides が偶数の場合も同じ範囲でループしますが、temp の計算式が入れ替わり、i が奇数のときは ((sides − 1) − i) / 2、i が偶数のときは (sides − i) / 2 を使います(check の計算式は共通です)。
• 最終的な count を返し、結果を出力します。

C++での実装例

#include <iostream>
using namespace std;
int rec_inside_equi(int sides){
    int count = 0, temp, check;
    if(sides%2 != 0){
        for(int i = sides - 2; i >= 1; i--){
            if (i & 1){
                temp = (sides - i) / 2;
                check = (i * (i + 1)) / 2;
                count += check * temp;
            }
            else{
                temp = ((sides - 1) - i) / 2;
                check = (i * (i + 1)) / 2;
                count += check * temp;
            }
        }
    }
    else{
        for(int i = sides - 2; i >= 1; i--){
            if (i & 1){
                temp = ((sides - 1) - i) / 2;
                check = (i * (i + 1)) / 2;
                count += check * temp;
            }
            else{
                temp = (sides - i) / 2;
                check = (i * (i + 1)) / 2;
                count += check * temp;
            }
        }
    }
    return count;
}
int main(){
    int sides = 4;
    cout<<"正三角形に内接する異なる長方形の数: "<<rec_inside_equi(sides);
    return 0;
}

実行結果

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

正三角形に内接する異なる長方形の数: 4