C++で五胞体数（ペンタトープ数）を求める方法

五胞体数とは？

五胞体数（ペンタトープ数）は、パスカルの三角形の第5の対角線上に現れる数列として知られています。この数列を定義するには、パスカルの三角形に少なくとも5つの数が必要となるため、数列の最初の数はパスカルの三角形の第4行である 1 4 6 4 1 から始まります。

本チュートリアルでは、n番目の五胞体数を求める方法を解説します。まずは具体的な例を見てみましょう。

入力 : 1
出力 : 1

入力 : 4
出力 : 35

以下の図から出力を確認できます。

この問題は数列に関するものなので、解法ではまず数列のパターンを見つけることから始めます。

解法のアプローチ

このプログラムでは、数列のすべての数が従う一般式（一般項）を導出します。その後、求めたい値を公式に代入するだけで、出力を得ることができます。

実装例

上記アプローチのC++コード

#include<bits/stdc++.h>
using namespace std;
int answer(int n){ // n番目の五胞体数を求める関数
    return (n * (n+1) * (n+2) * (n+3))/ 24; // 導出した公式
}
int main(){
    int n = 6; // 求めたい五胞体数
    cout << answer(n) << "\n";
    n = 4;
    cout << answer(n) << "\n";
    return 0;
}

出力

126
35

上記コード全体の計算量は O(1) です。つまり、定数時間で動作します。処理時間が入力サイズに依存しないため、どのような入力に対しても同じ時間で答えを計算できます。これは達成可能な最良の時間計算量です。

コードの解説

上記のアプローチでは、数列のパターンを見つけ、そこから一般式を導出することを目指しました。最終的に導き出した公式は (n * (n + 1) * (n + 2) * (n + 3)) / 24 です。ここで n は求めたい項の番号を表します。

なお、この公式はパスカルの三角形の第5対角線に対応する二項係数 C(n+3, 4) と一致するため、数学的にも正しいことが確認できます。

まとめ

本チュートリアルでは、公式を導出することでn番目の五胞体数を求める問題を解きました。この問題に対するC++プログラムと、解決までの完全なアプローチについても学びました。同じプログラムは、C、Java、Pythonなど他の言語でも同様に実装できます。このチュートリアルが皆様のお役に立てば幸いです。