はじめに
フィボナッチ数列の記事ってフィボナッチ数列100番目より遅いところですが、勉強中のもっとプログラマ脳を鍛える数学パズル アルゴリズムが脳にしみ込む70問 のアウトプットということでお許しください。
Ruby
rubymemo.rb
@memo = {0 => 1, 1 => 1}
def f(n)
return @memo[n] if @memo[n]
@memo[n] = f(n - 1) + f(n - 2)
end
puts f(10) # => 89
rubyarray.rb
N = 10
f = Array.new()
f[0] = f[1] = 1
2.upto(N) do |i|
f[i] = f[i - 1] + f[i - 2]
end
puts f[N] # => 89
javascript の様にハッシュではなく配列でも実装可能と思われます。
Perl
perlmemo.pl
my %memo = (0 => 1, 1 => 1);
sub f {
my $n = shift;
return $memo{$n} if defined $memo{$n};
$memo{$n} = f($n - 1) + f($n - 2);
}
print f(10), "\n"; # => 89
perlarray.pl
my $n = 10;
my @f;
$f[0] = $f[1] = 1;
for my $i (2..$n) {
$f[$i] = $f[$i - 1] + $f[$i -2];
}
print $f[$n], "\n"; # => 89
ruby_perl.pl
return @memo[n] if @memo[n] # ruby
return $memo{$n} if defined $memo{$n}; # perl
return $memo{$n} if exists $memo{$n}; # perl
ruby と異なり、defined関数もしくは exists関数を使用する必要があります。
JavaScript
javascriptmemo.js
var memo = [];
memo[0] = memo[1] = 1;
function f(n) {
if (memo[n]) return memo[n];
return memo[n] = f(n - 1) + f(n - 2);
}
console.log(f(10)); // => 89
javascriptarray.js
N = 10;
var f = [];
f[0] = f[1] = 1;
for (var i = 2; i <= N; i++) {
f[i] = f[i - 1] + f[i - 2];
}
console.log(f[N]); // => 89
javascript に詳しくないので、ハッシュ未使用で実装しています。
まとめ
- フィボナッチ数列を実装した
- それぞれの言語に違いがあって面白かった
参照したサイト
フィボナッチ数列
メモ化から学ぶ早期リターン
javascriptのハッシュライブラリを比較する
exists関数 - ハッシュのキーの存在確認