C++で正N角形上の3人目の最適な位置を求める方法

このチュートリアルでは、正N角形上における3人目の人物の最適な位置を求める方法を解説します。

正N角形が与えられ、すでに2人の人物がそれぞれ異なる頂点に立っているものとします。ここでの課題は、既存の2人から3人目までの距離の合計が最小になるように、3人目を配置すべき頂点を見つけることです。

アルゴリズムの手順

問題を解くための手順は以下の通りです。

• Nと2つの頂点A、Bを初期化します。
• 3人目の位置を格納する変数と、最小合計値を初期化します。
• 1からNまで繰り返し処理を行います。
  • 現在の頂点がAまたはBの場合はスキップします。
  • 現在の頂点とA、Bとの差の絶対値の合計を計算します。
  • その合計を最小合計値と比較します。
  • 現在の合計が最小合計値より小さい場合は、位置と最小合計値を更新します。
• 3人目の位置を出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int findThirdPersonStandingVertex(int N, int A, int B) {
    int position = 0;
    int minimum_sum = INT_MAX, sum;
    for (int i = 1; i <= N; i++) {
        // 既に使用されている頂点はスキップ
        if (i == A || i == B) {
            continue;
        }
        else {
            // 現在の頂点からAおよびBまでの距離
            sum = abs(i - A) + abs(i - B);
            // 現在の合計がこれまでの最小値より小さいかチェック
            if (sum < minimum_sum) {
                // 最小合計値と頂点の位置を更新
                minimum_sum = sum;
                position = i;
            }
        }
    }
    return position;
}
int main() {
    int N = 7, A = 5, B = 7;
    cout << "Vertex: " << findThirdPersonStandingVertex(N, A, B) << endl;
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が出力されます。

Vertex: 6

まとめ

このアルゴリズムは、すべての頂点を一度ずつ確認する線形探索（計算量O(N)）で構成されており、シンプルかつ効率的に最適な頂点を見つけることができます。正多角形の頂点間の距離を「頂点番号の差の絶対値」として扱うことで、複雑な幾何学的計算を避けながら問題を解決できる点がポイントです。

このチュートリアルについてご質問がある場合は、コメント欄でお気軽にお知らせください。