Pythonで数の三角形の行lにおける最初の偶数の位置を求めるプログラム

数の三角形とは

本記事で扱うのは、次のような規則で生成される「数の三角形」です。

      1
    1 1 1
  1 2 3 2 1
1 3 6 7 6 3 1

この三角形では、各行の要素はその真上にある3つの数を足し合わせることで生成されます。両端の要素については、真上に存在する数だけが加算されます。

問題の定義

行番号 l が与えられたとき、その行に最初に現れる偶数が何番目にあるかを求めます。位置は 1から始まる ものとします。

例えば、l = 5 の場合、答えは 2 になります。実際に5行目まで書き出すと次のようになります。

          1
       1  1  1
     1  2  3  2  1
   1  3  6  7  6  3  1
1  4  10 16 19 16 10 4  1

5行目は「1, 4, 10, 16, 19, 16, 10, 4, 1」と並んでおり、最初の偶数である 4 は 2番目 に位置しています。

解法のアプローチ

この問題は、行番号 l の偶奇性に着目することで、三角形を実際に構築しなくても定数時間で答えを求められます。偶数が現れる位置は l を 4 で割った余りによって周期的なパターンを持つためです。手順は以下の通りです。

• l が 1 または 2 の場合： 行全体が奇数だけで構成されているため、-1 を返します。
• l が偶数の場合：
  • l が 4 で割り切れるなら 3 を返します。
  • それ以外（l を 2 で割った商が奇数）なら 4 を返します。
• l が奇数（3 以上）の場合： 2 を返します。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def solve(l):
    if l == 1 or l == 2:
        return -1
    elif l % 2 == 0:
        if l % 4 == 0:
            return 3
        else:
            return 4
    else:
        return 2

l = 5
print(solve(l))

入力と出力

入力：

5

出力：

2

計算量について

この解法は条件分岐のみで構成されているため、時間計算量・空間計算量ともに O(1) です。三角形を行ごとに生成して走査する方法では O(l²) の計算が必要になりますが、本手法では行番号がどれほど大きくなっても即座に答えを導き出せる点が大きな利点です。