フィボナッチ数列 Ruby Perl JavaScript

はじめに

フィボナッチ数列の記事ってフィボナッチ数列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関数 - ハッシュのキーの存在確認