コインを三角形（ピラミッド状）に配置したときの最大の高さを求めるC/C++プログラム

コインを三角形（ピラミッド状）に積んだときの最大の高さ

この記事では、少し頭を使う興味深い問題を紹介します。N枚のコインが与えられたとき、それらをピラミッド状に並べた場合に作れる最大の高さを求めるという問題です。この配置方法では、1段目に1枚、2段目に2枚、3段目に3枚というように、段が下がるごとにコインを1枚ずつ増やしながら積み上げていきます。

図の例を見てみましょう。高さ3のピラミッドを作るには、最低でも6枚のコインが必要です。同様に、高さ4のピラミッドには10枚のコインが必要になります。つまり、コインが13枚あれば高さ4までは作れますが、高さ5に必要な15枚には届かないため、最大の高さは4となります。

最大の高さを求める公式

高さhのピラミッドに必要なコインの総数は、1 + 2 + 3 + … + h = h(h+1)/2 と表せます。したがって、n ≥ h(h+1)/2 を満たす最大のhを求めればよいことになります。この式をhについて解くと、次の公式が得られます。

height = (−1 + √(1 + 8n)) / 2

C/C++による実装例

この公式を使えば、平方根を1回計算するだけで最大の高さをO(1)の計算量で求められます。以下がその実装例です。

#include<iostream>
#include<cmath>
using namespace std;
int getMaxHeight(int n) {
    int height = (-1 + sqrt(1 + 8 * n)) / 2;
    return height;
}
main() {
    int N;
    cout << "Enter number of coins: ";
    cin >> N;
    cout << "Height of pyramid: " << getMaxHeight(N);
}

実行結果

Enter number of coins: 13
Height of pyramid: 4

この例では、13枚のコインを入力すると「4」と出力されます。13枚あれば高さ4（10枚使用）までは作れますが、高さ5に必要な15枚には足りないためです。