今のうちに
今日を逃すと当分無理っぽいので今日のうちにさらっと紹介しておこう。
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2007/06/27
- メディア: 単行本
- 購入: 58人 クリック: 1,055回
- この商品を含むブログ (967件) を見る
めっちゃ面白かったです。の和を求めるところが個人的に一番感動しましたね。
前半で取り上げられてる事柄は知ってたことが多いのですが、それでも新しい視点*1が得られて楽しかったです。
前の章で出てきた事柄が後に前提として、あるいは応用的に使われていて、良く考えられているなぁ、と思いました。
読み物としても面白いですよ。興味があれば是非。
この本の最後のほうに載ってた問題ですが、
nを異なる自然数の和であらわす方法が通りあるとする。
ただし、足す順番が異なるだけのものは一つと数える。
たとえば、なので、である。
このとき、
(1)を求めよ。
(2)は成立するか。
原題はかなり表現が違いますが、まぁいいでしょう。
この問題の(2)に対して、フィボナッチで評価する方法*2、しらみづぶしに数える方法、そして母関数を用いて評価する方法が紹介されています。
実際にはらしいので、この問題の条件はゆるゆるですねぇ。
まぁそれだけ解法に幅があるってことですかね。
実際にこの問題が試験に出たらどう対処するのがいいんでしょうかね?
しらみつぶしなら10分ほどで終わるでしょうから、そうするのが一番いいように思えてきます。
かといってしらみつぶしでは、nを大きくして出題するとかないません。たとえば、を数えるのは現実的ではありませんね。
とすると、nが小さければ*3しらみつぶしで、大きくなってきたら頑張って評価するのが良いのだろうと思います。
私の考えた解法も書こうと思ったんですが、疲れてかけないんでパス。
またそのうち書きます。