三角数かどうかを判定するC++プログラム

ある整数 n が与えられたとき、それが三角数であるかどうかを判定する方法を解説します。

三角数とは、n 個の点(または球)を層状に積み重ねて正三角形を形作ることができる数のことです。具体的には、1, 3, 6, 10, 15, 21 … のように、k 番目の三角数は公式 T(k) = k × (k + 1) / 2 で表されます。

例えば、入力が n = 10 の場合、10 は 4 番目の三角数(1 + 2 + 3 + 4 = 10)なので、出力は True になります。

アルゴリズムの手順

この問題を解くには、次の手順に従います。

• 1 から n まで順に各値 i について調べます。
• i × (i + 1) が 2 × n と等しい場合、n は三角数なので true を返します。
• すべての候補を調べても一致しなければ false を返します。

for initialize i := 1, when i <= n, update (increase i by 1), do:
   if i * (i + 1) is same as 2 * n, then:
      return true
return false

C++による実装例

以下に実際の実装例を示します。

#include <bits/stdc++.h>
using namespace std;
bool solve(int n){
   for (int i = 1; i <= n; i++){
      if (i * (i + 1) == 2 * n){
         return true;
      }
   }
   return false;
}
int main(){
   int n = 10;
   cout << solve(n) << endl;
}

入力

10

出力

1

補足：計算量について

この方法の時間計算量は O(n) です。より効率的にしたい場合は、判別式 D = 8n + 1 が完全平方数であるかどうかを確認する方法(O(√n) または O(1))も利用できます。これは、三角数の定義式 k(k+1)/2 = n を二次方程式として解くことで導き出せます。