n枚のコインで作れるピラミッドの最大の高さを求めるC/C++プログラム

この記事では、n枚のコインを使って作れるピラミッドの最大の高さを求める方法と、そのC/C++による実装例を解説します。

問題の概要

n枚のコインが与えられ、それらを最大の高さになるようにピラミッド状に積み上げます。配置のルールは以下のとおりです。

• 1段目（最上段）には1枚目のコインを置く
• 2段目には2枚目・3枚目のコインを置く
• 以降も同様に、k段目にはk枚のコインを置く

たとえば次の図のように、6枚のコインで高さ3のピラミッドが完成します。高さ4にするためには合計10枚のコインが必要になります。

高さを求める公式

k段目までに必要なコインの総数は「三角数」と呼ばれ、次の式で表されます。

N = H × (H + 1) / 2

この式をHについて解くことで、コインの枚数Nからピラミッドの高さHを直接求められます。

H = { (-1 + √(1 + 8N)) / 2 }

入出力例

Input: n = 10
Output: Height of pyramid: 4

解説

上記の公式に n = 10 を代入すると、H = (-1 + √(1 + 80)) / 2 = (-1 + 9) / 2 = 4 となり、正しく高さ4が得られます。実際、1 + 2 + 3 + 4 = 10 枚でちょうど4段のピラミッドが完成します。

C++での実装例

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    int n = 10;
    int height = (-1 + sqrt(1 + 8 * n)) / 2;
    cout << "Height of pyramid: " << height;
}

実装のポイント

• sqrt関数を使用するため、<math.h>（または<cmath>）をインクルードします。
• 平方根の結果を整数型に代入することで、小数点以下が切り捨てられ、作成可能な最大の高さが求まります。
• 計算量はO(1)であり、コインの枚数に関わらず高速に答えを求められます。