C++で順列の推測に必要な移動回数を求めるアルゴリズム

整数 N が与えられたとき、順列（permutation）を最悪ケースで完全に推測し切るまでに必要な移動回数を求める問題を考えます。この移動回数は単純な階乗ではなく、「1 から N までの各 i に対して i × (N − i) を計算して合計し、最後に N を加える」ことで求められます。

具体例

入力

9

出力

129

N = 9 の場合、i = 1 のときは 1 × 8 = 8、i = 2 のときは 2 × 7 = 14、i = 3 のときは 3 × 6 = 18 … というように計算を進めていきます。これらをすべて合計すると 120 になり、さらに N の値である 9 を加えると、答えは 129 となります。

アルゴリズム

• 整数 n を受け取る。
• カウント用変数 count を 0 で初期化する。
• i を 1 から n までループさせる。
  • count に i × (n − i) を加算する。
• ループ終了後、count に n を加算する。
• count を結果として返す。

C++での実装

以下は、上記のアルゴリズムを C++ で実装した例です。

#include <bits/stdc++.h>
using namespace std;

int getNumberMoves(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        count += i * (n - i);
    }
    count += n;
    return count;
}

int main() {
    int n = 9;
    cout << getNumberMoves(n) << endl;
    return 0;
}

実行結果

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

129

計算量

このアルゴリズムは 1 から n までを一度だけ走査するため、時間計算量は O(n)、追加のメモリをほとんど使わず空間計算量は O(1) で動作します。大きな n に対しても効率的に処理できるのが特徴です。