「「scheme入門」読む」記事へのコメント

許せる範囲と許せない範囲

[parsley (5772)]

計算速度って話だけだったら、フィボナッチに√５を導入というのもありだと思います。

でも原理原則って話しになると別問題ですね。速い別解はなんにしてもありがたい。

--
Copyright (c) 2001-2014 Parsley, All rights reserved.

Re:許せる範囲と許せない範囲

[gm300 (14617)]

O(1)クラスの解ですね。効率をいうならそこまで考えないといけませんね。
でも 単なる負け惜しみで書くのですが、以下の点で x2-x-1 の解を使う方法はいやです。

1. 見た目上 答えが整数にならない。
2. fb(1)=1 fb(2)=4 みたいな変則的な問題の時にどうするか考えるが面倒。
3. tr(n) = tr(n-1)+tr(n-2)+tr(n-3) みたいになるともっと面倒。

いずれにせよ、O(2**n)はちょっと。top downでも途中結果を保存＆参照できればそれで O(n)になるので、そこらをスマートに書ければかっこいいです。

Re:許せる範囲と許せない範囲

[parsley (5772)]

１．２．３．程度の問題には即答しちゃうのが、数学を専門にしている人のタイプだと聞きました。

わかなんなくなった私としては「境界ではどうなっているんでしょうか？」と言うしかない。

--
Copyright (c) 2001-2014 Parsley, All rights reserved.