パスカルの三角形を計算する

パスカルの三角形 - みずぴー日記 にインスパイヤされて、久しぶりに パスカルの三角形 でも解いてみます。

多分、高校の授業で習うと思われるパスカルの三角形ですが、実際に 4 次 (4 段目) 以降のものは見たことがないのです。

ここでは、前の段を再帰的に呼び出して、パスカルの三角形を求めます。 (awk の性質上、いわるる 0 段目 (1 だけのところ) を 1 段目と呼んでいます)

コードは以下のとおりです。

#! /usr/local/bin/nawk -f
# pascals_triangle.awk
# パスカルの三角形を計算する
# usage: nawk -f pascals_triangle.awk

BEGIN {

    # 1 段目から 10 段目までのパスカルの三角形を返す
    for (i = 1; i <= 10; i++) {
        print pascals_triangle(i);
    }
}

# pascals_triangle(): ある段数のパスカルの三角形の数を返す
#   in:     段数 num
#   out:    段数 num のパスカルの三角形の数
function pascals_triangle(num, \
                          num_pas, arr_pas, i, new_pas, pas_str) {

    # 1 段目は特別扱い、2 段目以降は再帰で呼び出す
    if (num == 1) {

        return 1;

    } else {

        num_pas = split(pascals_triangle(num - 1), arr_pas);

        for (i = 1; i <= num_pas - 1; i++) {
            new_pas[i] = arr_pas[i] + arr_pas[i + 1];
            pas_str = pas_str " " new_pas[i];
        }

        # 両端に 1 を足したものを返す
        return "1" pas_str " 1";

    }
}

再帰的に呼び出す場合には、関数のローカル変数をちゃんと定義しないと正しい値が求まらないことがありますので、注意してください。

では、実際に実行してみましょう。

$ nawk -f pascals_triangle.awk
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

このような形で求まります。

tag_nawk.png tag_nawk.png tag_nawk.png tag_nawk.png