#はじめに
はじめまして、某WEBCAMPの生徒です。
初投稿なので至らない部分が多いと思いますが、疑問点や間違っている部分がありましたら教えていただけると嬉しいです。
現在就活中ですが、どうやら面接の前にプログラミングスキルを測る企業があるらしく、そこではトリボナッチ数列に関する問題が出るみたいです。
そのため本記事では、Rubyを使ってトリボナッチ数列を出したいと思います。
#トリボナッチ数列とは
トリボナッチ数列は[0, 0, 1]から始まり、その後の項が前3つを足したものになる数列です。
例：[ 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81]
81 = 13 + 24 + 44
#トリボナッチ数列で数字を取り出す！
今回は、「ｎ項目」のnに値を入力するとその項の数字が出るようにしていきます。
初項の n は 1 から始めます。つまり、1を入力すると
例：[ 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81]の
一番左の0が出力されるようにします。
また、コードを書くにあたって
https://yu8mada.com/2018/06/23/how-to-calculate-fibonacci-numbers-in-ruby/#content-1-4
のフィボナッチ数列のコードを参考にさせていただきました。
まず、今回のトリボナッチ数列についてですが、
スタンダードに[ 0, 0, 1]から始めるものとしたいと思います。（[ 1, 1, 2]から始まることもあるみたい)
def tribonacci(n)
return if n < 1
a, b, c = 0, 0, 1
(n - 1).times { a, b, c = b, c, a + b + c }
a
end
puts "数を出したいのは何項目ですか？"
n = gets.to_i
# -> 11を入力
puts "#{n}項目の数字は#{tribonacci(n)}"
# -> 11項目の数字は81
今回は11を入力したので、
例：[ 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81]
の11項目の81が返ってきました。
2行目
return if n < 1
今回は、0または負の数を入力した場合は何も返さないようになっています。
3行目
a, b, c = 0, 0, 1
で最初の３つの項[0 , 0 , 1]を決定しています。
（ [1 , 1 , 2]で始めたい場合などはここのa,b,cの値を変更します。）
4行目
(n - 1).times { a, b, c = b, c, a + b + c }
ここでは入力されたnで、n-1回の足し算を繰り返し(times)で行っています。
ここでいう足し算とは、求める数の1つ前と2つ前と3つ前を足すことです。
例えば、トリボナッチ数列：[ 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81]で、
81という数字は13と24と44を足した数になっています。
{a, b, c = b, c, a + b + c} というのは
a = b
b = c
c = a + b + c
の３つの式をまとめて書いたもので、
（これを順番に実行すると新しいa,bでa + b + cが計算されてしまうという指摘がありました。@scivolaさん ありがとうございます）
の３つの式を多重代入（同時に代入）したもので、
これによってn-1回、a, b, cの項を右にずらすというイメージです。
最後に5行目のaでn項目の数字を出力します。
#追記１：ベンチマークと他の方法
user system total real
tribonacci 10000 0.013257 0.000048 0.013305 ( 0.015514)
tribonacci 100000 0.329343 0.036156 0.365499 ( 0.378116)
tribonacci 1000000 27.161322 4.053936 31.215258 ( 31.997343)
今回のコードでは、
項(n)が6桁までならば30秒かからず計算ができます。
###方法２（毎回メソッドを呼び出して計算する方法）
def tribonacci2(n)
return if n < 1
return 0 if n < 3
return 1 if n < 5
tribonacci2(n - 1) + tribonacci2(n - 2) + tribonacci2(n - 3)
end
puts "数を出したいのは何項目ですか？"
n = gets.to_i
puts "#{n}項目の数字は#{tribonacci2(n)}"
user system total real
tribonacci2 10 0.000054 0.000003 0.000057 ( 0.000404)
tribonacci2 20 0.002148 0.000000 0.002148 ( 0.002359)
tribonacci2 30 0.834248 0.000189 0.834437 ( 0.835145)
tribonacci2 35 17.689164 0.004301 17.693465 ( 17.741626)
こちらは毎回メソッドを呼び出して、計算を行うコードです。
コード自体はシンプルですが、項(n)が35以上になると非常に処理に時間がかかるようになり、今回紹介している方法に比べると圧倒的に計算可能な桁が少ないです。
#追記２：初項からn項目までを配列にして出す
def tribonacci(n)
result = []
return if n < 1
a, b, c = 0, 0 ,1
(n).times { a, b, c = b, c, a + b + c, result << a }
result
end
puts "数列を何項目まで表示しますか？"
n = gets.to_i
# -> 11を入力
puts "#{tribonacci(n)}"
# -> [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81]
こちらでは、a, b, c = b, c, a + b + cを行うと同時にresult = []という空の配列の中にaを入れていくことで、初項からn項目までを配列として出しています。
#おわりに
コードや記事で、わかりにくい部分や間違いがある場合はぜひ教えていただけると助かります。
ところで、記事を書いている間に猫が布団にトイレをしてたので今から洗わなければいけません。
なんてこったい