【C++入門】n辺の凸多角形の対角線の数を求める方法

問題の概要

整数 n が与えられたとき、n 辺の凸多角形が持つ対角線の本数を求める問題を考えます。例えば n = 5（五角形）の場合、対角線の数は 5 本になります。

対角線の数を求める数式

n 辺の凸多角形では、各頂点から対角線を引ける相手は、自分自身と両隣の 2 つの頂点を除いた残りの頂点です。つまり、1 つの頂点あたり n − 3 本の対角線を引くことができます。

したがって、n 個の頂点全体では n × (n − 3) 本の対角線が数えられます。しかし、この数え方では各対角線を両端の頂点から 2 回ずつ重複して数えてしまいます。そこで 2 で割ることで、実際の対角線の総数が求められます。

対角線の総数 = n × (n − 3) / 2

例えば n = 5 の場合、5 × (5 − 3) / 2 = 5 となり、五角形の対角線が 5 本であることが確認できます。

C++での実装例

#include<iostream>
using namespace std;

int diagonalCount(int n) {
    return n * (n - 3) / 2;
}

int main() {
    int n = 8;
    cout << n << " sided convex polygon has " << diagonalCount(n) << " diagonals";
}

実行結果

8 sided convex polygon has 20 diagonals

この例では n = 8（八角形）を渡しており、8 × (8 − 3) / 2 = 20 より、対角線が 20 本であることが正しく出力されています。

まとめ

n 辺の凸多角形の対角線の数は、各頂点から引ける n − 3 本の対角線に頂点数 n を掛け、重複分を除くために 2 で割ることで求められます。計算量は O(1) と非常に効率的で、n が大きくなっても即座に答えを得られるのがポイントです。