コインを三角形に配置したときの最大の高さを求めるPythonプログラム

本記事では、N枚のコインを三角形の形に配置したときに達成できる最大の高さを求めるPythonプログラムについて詳しく解説します。

問題文

N枚のコインが与えられ、それらを三角形の形に並べることを考えます。具体的には、1段目に1枚、2段目に2枚、3段目に3枚というようにコインを積み上げていきます。このとき、N枚のコインで作ることができる三角形の最大の高さ(段数)を求めて表示する必要があります。

解法のアプローチ

高さhの三角形を作るために必要なコインの総数は、等差数列の和の公式より次のように表されます。

1 + 2 + 3 + … + h = h(h+1)/2 ≤ N

これを整理すると二次不等式 h² + h − 2N ≤ 0 が得られ、解の公式を適用することで最大の高さは以下の式で求められます。

h = (−1 + √(1 + 8N)) / 2

この式で得られた値の小数点以下を切り捨てた整数部分が答えとなります。なお、平方根の計算には、ニュートン法(バビロニア法)による反復近似を実装しています。

実装例

# 平方根の近似計算(ニュートン法)
def squareRoot(n):
    # 初期近似値
    x = n
    y = 1
    e = 0.000001  # 許容誤差
    while (x - y > e):
        x = (x + y) / 2
        y = n / x
    return x

# 最大の高さを求める関数
def find(N):
    # 判別式に相当する値を計算
    n = 1 + 8 * N
    maxH = (-1 + squareRoot(n)) / 2
    return int(maxH)

# メイン処理
N = 17
print("Maximum height is :", find(N))

出力

Maximum height is : 5

すべての変数はローカルスコープ内で宣言されており、それぞれの参照関係は上図のようになっています。

コードの解説

squareRoot関数は、バビロニア法と呼ばれる反復計算によって平方根の近似値を求めます。xとyの差が許容誤差e(0.000001)以下になるまで、「x = (x + y) / 2」と「y = n / x」の更新を繰り返すことで、精度の高い平方根の値を得られます。

find関数では、判別式に相当する「1 + 8N」を計算し、その平方根から1を引いて2で割ることで最大の高さを算出します。最後にint型へ変換することで、小数点以下を切り捨てた整数値として結果を返します。

例えばN = 17の場合を見てみましょう。「1 + 8 × 17 = 137」となり、√137 ≒ 11.70 であるため、maxH = (−1 + 11.70) / 2 ≒ 5.35 となり、切り捨てて高さは5段と求まります。実際、1+2+3+4+5 = 15枚で5段の三角形が完成し、残りの2枚では6枚必要な6段目を作れないため、この結果が正しいことが確認できます。

まとめ

本記事では、N枚のコインを三角形に配置したときの最大の高さを求めるPythonプログラムについて学びました。等差数列の和の公式と二次方程式の解の公式を組み合わせることで、ループで全パターンを試すことなく、効率的に答えを導き出せる点がポイントです。