2024.10.01
【勉強】ミドルウェア・アプリケーションのEOL・EOSLについて学んでみた
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つでも当てはまる方は是非、詳細ページへ!Qangaroo(カンガルー)
【テクノデジタルのインフラサービス】
当社では、多数のサービスの開発実績を活かし、
アプリケーションのパフォーマンスを最大限に引き出すインフラ設計・構築を行います。
AWSなどへのクラウド移行、既存インフラの監視・運用保守も承りますので、ぜひご相談ください。
詳細は下記ページをご覧ください。
最近の記事
タグ検索