パスカルの三角形 アルゴリズム(Pascal's Triangle Algorithm for VB)

パスカルの三角形アルゴリズムの前に Shortest path problem 最短経路問題を紹介します。

Start から Goal までの最短経路でどれだけのパターンがあるかという問題です。下の図は、３５通りの最短経路があります。各辺を辿って、クロスした点に到着できたところで数値を付けています。この問題は３５通りの経路がありますが、数値を書き込まなくてもソースコードに書いているPascalC(8,4)-->"nCk"で求めることが出来ます。

次に、下の図は赤い丸のポイントが通れない場合、どういった方法で問題を解くかを説明しています。赤い丸の地点は通れないので経路のパターンは０となります。Goal近くにあるととても最短経路が少なくなります。

この方法は、ずい分以前に授業で発見した方法で、教科書に載っている方法とは違ってました。今の教科書にはどういった方法が記載されているか分かりませんが、面白い方法だと思いますので紹介しています。

下の図は、シェルピンスキーの三角形を表示したものです。公理=A ルール：(A → B−A−B), (B → A+B+A)奇数の場合は空白としたフラクタル図形です。これはパスカルの三角形の公式を利用して描かれたものです。

The image below is Sierpiński triangle. Rule is A = B−A−B, B = A+B+A that means In the case of odd number, the fractal figure made blank.

恐らく、これが最速でパスカルの三角形を書き出すアルゴリズムだと思います。もしこのアルゴリズムが他に見られないものであれば、他言語に移植して使って欲しいと思います。

Probably, this is the fastest algorithm which writes out Pascal's triangle. I think "L System" or game etc. can use it. Code is very simple and easy to understand.

When PascalTriangle(17) is called, result below will be written.

Call PascalTriangle(17) で実行すると、下記のように書き出されます。とても簡単なコードなので分かりやすいと思います。

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
1-10-45-120-210-252-210-120-45-10-1
1-11-55-165-330-462-462-330-165-55-11-1
1-12-66-220-495-792-924-792-495-220-66-12-1
1-13-78-286-715-1287-1716-1716-1287-715-286-78-13-1
1-14-91-364-1001-2002-3003-3432-3003-2002-1001-364-91-14-1
1-15-105-455-1365-3003-5005-6435-6435-5005-3003-1365-455-105-15-1
1-16-120-560-1820-4368-8008-11440-12870-11440-8008-4368-1820-560-120-16-1
1-17-136-680-2380-6188-12376-19448-24310-24310-19448-12376-6188-2380-680-136-17-1

最初に書いているコードはパスカルの三角形の数値を書き出すプロシージャです。次のコードは特定の位置の数値をかえすFunctionです。特定の位置は、PascalC(n,k)、 n上からの段、k は左から数えた位置です。