漸化式 --- n個の中からr個を選ぶ組合わせの数を求める

今日からアルゴリズムの勉強をしていきたいと思います。

アルゴリズムなんて新人のころチットやった程度です。

それでも、１０年以上プログラムを書いてきました。

まあ、ビジネスアプリなのでそんなに必要としなかったのかしら？

（※プログラマを目指している諸君、こんなプログラマもいますので勇気を持って進んでください）

ということで、「Visual Basicによる　はじめてのアルゴリズム入門」という本で

学んでいきたいと思います。

まず最初は、「漸化式」です。おっといきなりつまずいていまいました。

まずこの漢字なんて読むの？　→　ぜんかしき

意味は？　→　数列で隣り合う2項または3項の間に成り立つ一定の関係を式で表したものだそうですが、なんじゃらほい。まあ、無視してプログラムを書いてみましょう。

あ、そうそう、この本では、言語はVisual Basicになってますが、

このブログではPythonでやっていきます。

（実は、javaってどうよとなって、Pythonを注目中なのです）

【問題】

n個の中からr個を選ぶ組合わせの数を求めるプログラムを書きなさい。

たとえば、a, b, cという３個の中から２個を選ぶ組み合わせはab, ac, bcの３通りである。

【答え】

def combi(n, r):

  p = 1

  for i in xrange(1, r+1):

    p = p * (n - i + 1) / i

    return p

for n in range(6):

  for r in range(n+1):

    print n, "C", r, "=", combi(n, r)

【実行結果】

0 C 0 = 1
1 C 0 = 1
1 C 1 = 1
2 C 0 = 1
2 C 1 = 2
2 C 2 = 1
3 C 0 = 1
3 C 1 = 3
3 C 2 = 3
3 C 3 = 1
4 C 0 = 1
4 C 1 = 4
4 C 2 = 6
4 C 3 = 4
4 C 4 = 1
5 C 0 = 1
5 C 1 = 5
5 C 2 = 10
5 C 3 = 10
5 C 4 = 5
5 C 5 = 1

漸化式なんて言われると、？？？ですが、プログラムはいたって簡単です。

なんか、公式があるみたいで、それをプログラムがオーバーフローしないように

変形した式で計算しているところがミソのようです。

まあ、別に覚えなくても理屈だけ分かっていたらいいと思います。

ところでiTuneのビジュアルエフェクト（球体が火花みないなものを吹き出すやつ）

ってすごいですね。どういうアルゴリズムでやってるんだろう？