メニューを閉じる

テクノデジタルグループ

メニューを開く

2018.02.13

プログラミング

フィボナッチ数のいろいろな対応方法

Canadian Devです。僕はプログラミングが楽しいのは、謎のような問題をプログラミングで解くことです。カナダでウェブ開発学校を通ったとき、先生達がCoffee and Codeという時間を与えてくれました。朝にコーヒーを飲みながらみんなと一緒にペアプログラミングして問題と取り組みました。とても楽しくて、日本でもコーヒーを飲みながらプログラミングする時間を楽しんでいます。こういうときに、面白いドリルに出会うので、今回の記事はRubyとJavaScriptを使ってそのドリルの例について書きます。

ドリルの内容:フィボナッチ数

フィボナッチ数とは1, 1, 2, 3, 5, 8, 13…という数列です。一つ前の数字と二つ前の数字を足したものが永遠に続いていく数列です。つまり、1+1=2, 1+2=3, 2+3=5, 5+8=13. フィボナッチ数列で5番目の数字が5 (1, 1, 2, 3, 5)。数列のnのところにある数字を計算する。

ドリルの参考はこちらです。(JavaScriptの回答)

配列とループのフィボナッチ

このドリルで一つの問題にはいくつかの解決法があることに気づきました。初めてフィボナッチ数を見たとき、これは「配列で解決できるんだ!」と思って、配列とループで対応してみました。

def fibonacci(n)
  fib_array = [0, 1]
  n.times { fib_array << fib_array[-1] + fib_array[-2] }
  fib_array[n]
end

fibonacci(10) #=> 55

上記のメソッドだと、最後から1番目と2番目のエレメントを足した数字をfib_arrayに入れる処理をn回数で繰り返して、n番目にある数字を返します。

反復メソッドのフィボナッチ

しかし、フィボナッチはよく知られている反復な問題です。

def fibonacci(n)
  return n if n == 0 || n == 1
  fibonacci(n-2) + fibonacci(n-1)
end

fibonacci(10) #=> 55

上記のメソッドだとnが0か1に達成するまで再帰処理を行います。fibonacci(3)(fibonacci(2)+fibonacci(1))を呼び出して、fibonacci(2)(fibonacci(1)+fibonacci(0))を呼び出して、fibonacci(1)1を返します。再帰処理の結果でフィボナッチ数を見つけ出すのです。再帰処理のメソッドなので、必ず条件を指定しないと永遠に再帰処理が続きます。

反復キーバリューのフィボナッチ

でも、メソッドを使う必要はありますか?こういう回答もあります。

fibonacci = Hash.new {|hash, key| hash[key] = key < 2 ? key : hash[key-1] + hash[key-2] }

fibonacci[10] #=> 55
fibonacci #=> {0=>0, 1=>1, 2=>1, 3=>2, 4=>3, 5=>5, 6=>8, 7=>13, 8=>21, 9=>34, 10=>55}

上記の例だと、fibonacciはメソッドじゃなくてハッシュです。反復でキーが1か0になるまでキーバリューをどんどん作っていきます。そのハッシュを調べると、求めたキーまでのキーバリューが入っています。

一つの問題にいくつかの解決法

一つの問題に解決法がいっぱいあります。この記事で同じフィボナッチ問題に配列、反復とハッシュという対応方法がありました。他のプログラミングのドリルもそうです。ペアプログラミングをして相手のプログラミングの考え方がわかります。

さらに難しい問題

上の参考リンクでかなり大きな整数を入力してみましたか?1,000,000を入力してみるとどうなりますか? Infinityが返ってきますね。上記のRubyメソッドでも1,000,000を引数で入れると、StackLevelTooDeepというエラーになります。1,000,000が受け入れられるメソッドはどう対応すればいいですか?もっと難しい問題ですね。コーヒーがたくさん必要かも!

That’s all, folks!


【記事への感想募集中!】

記事への感想・ご意見がありましたら、ぜひフォームからご投稿ください!
  • こんな記事が読んでみたい、こんなことが知りたい、調べてほしい!という意見も募集中!
  • いただいた感想は今後の記事に活かしたいと思います!

感想フォームはこちら


【テクノデジタルではエンジニア/デザイナーを積極採用中です!】

下記項目に1つでも当てはまる方は是非、詳細ページへ!
  • 自分でアプリを作ってみたい
  • ITで世の中にワクワクを生み出したい
  • 使いやすさ、デザインにこだわったWebサイトを開発したい

採用情報の詳細はこちら


Qangaroo(カンガルー)

  • 徹底した見やすさと優れた操作性で、テストの「見える化」を実現。
  • テストの進捗が見える。開発がスマートに進む。
  • クラウド型テスト管理ツール『Qangaroo(カンガルー)』

【テクノデジタルのインフラサービス】

当社では、多数のサービスの開発実績を活かし、
アプリケーションのパフォーマンスを最大限に引き出すインフラ設計・構築を行います。
AWSなどへのクラウド移行、既存インフラの監視・運用保守も承りますので、ぜひご相談ください。
詳細は下記ページをご覧ください。

https://www.tcdigital.jp/infrastructure/

最近の記事