魔方陣とアルゴリズム

折角なので(って何が折角なのかよくわからないけど)もう一つ紹介。文章が読みやすくて深いです。

オリーブの枝

アルゴリズムはプログラムを作る上で大切なもの。

1〜n(正の整数、例えば10)までの足し算の答え(和)を計算するプログラムをなんとなくPerlで作ってみよう。

1
2
3
4
5
6
my $n = 10;
my $sum = 0;
for (my $i = 1; $i <= $n; $i++) {
    $sum += $i;
}
print $sum;

はいできました。

…ループは便利なのだが、先のプログラムでは$n回の足し算を行うことになる。

さて、1〜nの和を求める公式があるので、それを使う。

1
2
3
my $n = 10;
my $sum = ($n + 1) * $n / 2;
print $sum;

式は少し複雑になったが計算は1回で終了。 さて、どっちが速いか?

$nが小さいうちはループのほうが速いかもしれない。 でも、$nが大きくなればなるほど公式を使うほうが圧倒的に速くなる。

プログラムはそのアルゴリズム(計算方法?)で性能が各段に変わる。

かなり昔、(小学校の3,4年くらい?)奇数マス四方の正方形の魔方陣(数字を一つずつ使って、たて、よこ、ななめの和が全て等しくなるように並べる)の作り方を父から教わった。(父は、特に算数に関しては良き先生だった。)

3×3の例

1
2
3
 2 7 6
 9 5 1
 4 3 8

奇数マス四方の作り方は、どれだけ大きくなってもちゃんと成立する。 しかし、偶数マス四方の作成方法は4×4では出来るのだが、6×6だと成立しない。というか、4×4にしても、どのような法則なのかいまいち釈然としなかった。

この時6×6の魔方陣も作れていたら、数に執着はしなかったかもしれない。 中学どころか高専の時も思い出しては図書館に行って本を読んだ。 6×6の魔方陣は本の中に存在している。しかし、どうやって作っているのか読み取れなかった。

最初にエクセルでプログラムが出来ることに気づいて作り始めたのは、魔方陣計算プログラムだった。 今思うと、最初の例のように「総当り」という工夫も何も無いプログラムで、とっても遅かった。

と、まあ、そんな昔の話を思い出した。 結局、4×4までは330MHz程度のパソコン上で動くエクセルでも、我慢できるほどで結果が出てくるようにはなった。 しかし、突破口が無いのでずっと放置したままだ。

プログラムのアルゴリズムはともかく、魔方陣そのもののアルゴリズムについてのページを見つけた。

すごい。

comments powered by Disqus
Hugo で構築されています。
テーマ StackJimmy によって設計されています。