先日やってみたFibFrogの問題は、自分の中での興味が大きくなりました。フィボナッチ数がどうのこうのというより、問題のルールにあったフィボナッチ数を条件にして次が進める、とか当てはまる、とかいうことが場合に、その組み合わせを探り当てるというのは結構有用なのかもしれない、みたいに考えました。
先日のCodilityでやってた中で再帰アルゴリズムのほうで不完全なものをuploadしたときでもラージテストを通ってくれる場合もありました。不完全という意味は、自分のローカルテストの中で偶然ベスト解を出せてないことが乱数使った自分のテストケースで偶然発見できたことで、実はuploadしたものがスコアよりもは不完全だった、みたいな意味です。Codility Lessonsのテストケースも厳しいレアケースもいくらか入っていると思うのですが、組み合わせの多様性は20,30くらいのテストケースでは網羅できないと改めて思い知らされます。
フィボナッチ数を求める実装
ここを見ていたのですが、Method 5の再帰が最初みていまいちわからなかったです。Method4のoptimizedということでトリッキー度が増しているんでしょうけどもpower関数の処理の大部分multipy以降を呼ばすに自分を呼び出しているのが奇異にみえました。
/* Optimized version of power() in method 4 */
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
} これの呼び出しを追ってみると、たしかにうまいこといってます。再帰を変数nの数列作成とそのスタックのために使っているように理解しました。
再帰を使わずループにしても効率とか読みやすさとか変わらないと最初思ったのですが、このループでできる数列を関数的に作るのが意外に難しいと感じました*1。若番から数列を作ろうとしても同じ数字から分岐が必要なのでアルゴリズムをすぐには思いつきません。int型の2で割ったとき(ビットシフトしたとき)の切り捨て仕様にフィットして、スタック領域を数列のそれに当てはめて先入れ先出しの動作でmultipyの呼び出しにつなげています。むーん。
| 入力n | multipyで呼ばれるときのn |
| 3 | 2 |
| 4 | 3 |
| 5 | 2,4 |
| 6 | 2,5 |
| 7 | 3,6 |
| 8 | 3,7 |
| 9 | 2,4,8 |
| 10 | 2,5,9 |
| 11 | 2,5,10 |
| 12 | 2,5,11 |
| 13 | 3,6,12 |
| 14 | 3,6,13 |
| 15 | 3,7,14 |
| 16 | 3,7,15 |
にしても、フィボナッチ数列は0始まりか1始まりかどちらがより説明においていいのかはよくわかりません。0からだと次の数値との比がでないので1のほうが語りやすい気がします。
*1:なんかよく知られた数字シーケンスなのかもしれませんが存じ上げません
