Perlでフィボナッチ数列を求めてみる

CodeIQ眺めてたらこんなお題があったのでやってみました。

挑戦者求む！下3桁のみのフィボナッチ数列から、任意の項を素早く求めてください。 by CodeIQ運営事務局 アプリケーションエンジニアを募集する企業│CodeIQ

まず、さくっと素直にフィボナッチ数列を書いてみます。

#! /usr/bin/perl

use strict;

sub get_fibonacci{
        my $n = shift;

        if( $n == 0 ){
                return 0;
        }elsif( $n == 1){
                return 1;
        }elsif( $n > 1){
                return get_fibonacci( $n - 1 ) + get_fibonacci( $n - 2 );
        }
}

my $arg = shift;
print get_fibonacci( $arg );

書いてみて、これは再帰のテストだなと気づいたものの、 これだとオーダーがどんどん増えていくのでたまったものではないなあと。

なので、配列を使う方式で書き直してみました。

#! /usr/bin/perl

use strict;

my @fibonacci;
sub get_fibonacci{
        my $n = shift;

        if( $n == 0 ){
                $fibonacci[0] = 0;
        }elsif( $n == 1){
                $fibonacci[1] = 1;
        }elsif( $n > 1){
        return $fibonacci[$n] if defined $fibonacci[$n];
                $fibonacci[$n] = get_fibonacci( $n - 1 ) + get_fibonacci( $n - 2 );
        }
}

my $arg = shift;
print get_fibonacci( $arg );

それぞれ時間を測ってみた結果は以下の通りです。

MBP:fibo3d kirine$ time ./fibonacci_simple.pl 30
832040
real    0m2.446s
user    0m1.010s
sys 0m0.019s

MBP:fibo3d kirine$ time ./fibonacci_array.pl 30
832040
real    0m0.008s
user    0m0.003s
sys 0m0.003s

十分早くなったと思います。ここまでが一般的なフィボナッチの話。

上記を踏まえて、掲題の問題は下3桁のフィボナッチというやや変則的な問題になっていますが、これは単純に% 1000で余剰を返してやれば良いですね。

もう一つ、フィボナッチを求めるためのリストがランダムに並んでいるのでこれはソートした上で最大値を取ればフィボナッチのリストを作るのは一回で十分になります。

というところまで書いてスクリプトを回したところで気づきましたが、求められる項が234491556と非常に大きいので普通にぶん回してリストを求めてしまうとメモリが足りません。。。ちょっと工夫が必要です。

12/29追記

CodeIQのお題が回答を締め切ったので続きを公開しました。

「Perlでフィボナッチ数列を求めてみる」の続き 〜CodeIQ解答編〜 - HYLOGICS

数学ガール (数学ガールシリーズ 1)

初めてのPerl 第6版