Help us understand the problem. What is going on with this article?

Rubyでトリボナッチ数列の問題を解いてみた(制限時間10分)

はじめに

低学歴の筆者がトリボナッチ数列の問題を10分以内で解決しなければならない状況に陥り、トリボナッチという言葉を忘れてしまった状態(記憶喪失状態)から10分以内でrubyで解決した体験記でございます。
数学に自信がある人・ない人も力試しに10分以内で実施してみてはどうでしょうか?

問題

問1
1,3,7,11,21,39...
50番個目にある数字は何ですか?

という問題を解決しなければいけない状況になりました...

...(;゚д゚)ゴクリ

10秒くらい意識を失いましたが、とりあえず現状を理解せねば!!と気合を入れ直しました。

トリボナッチ数列について

トリボナッチ数列とは、項の数字がその前の3つの項の数字の合計となっている数列である...らしいです
中学入試で勉強するらしいが、昨日何食べたっけ?レベルのメモリーしかない私の記憶喪失は治りませんでした(...現在30歳)

検索した結果...

トリボナッチ数とは、
...中略
a[0]=a[1]=0
a[2]=1
a[n]=a[n-1]+a[n-2]+a[n-3]
と定義された数列
この数列の一般項を求める。
f(z)=Σ[n=0→∞]a[n]zⁿ
=a[0]+a[1]z+Σ[n=2→∞]a[n]zⁿ
=Σ[n=2→∞]a[n]zⁿ
=a[2]z²+Σ[n=3→∞]a[n]zⁿ
=z²+Σ[n=3→∞]{a[n-1]+a[n-2]+a[n-3]}zⁿ
=z²+Σ[n=3→∞]{a[n-1]}zⁿ+Σ[n=3→∞]{a[n-2]}zⁿ+Σ[n=3→∞]{a[n-3]}zⁿ
=z²+zΣ[n=3→∞]{a[n-1]}z^(n-1)+z²Σ[n=3→∞]{a[n-2]}z^(n-2)+z³Σ[n=3→∞]{a[n-3]}z^(n-3)
=z²+zΣ[n=2→∞]a[n]zⁿ+z²Σ[n=1→∞]a[n]zⁿ+z³Σ[n=0→∞]a[n]zⁿ...以下略

いや10分じゃ理解できねーよ!!
理解することは諦めて、筆者的解釈のもとrubyで表現しました。

筆者的解釈

1個目 + 2個目 + 3個目 = 4個目
2個目 + 3個目 + 4個目 = 5個目の繰り返し
ところてん方式的なやつか ← 全然違う

1個目をaとし、2個目をb、3個目をcと表現し合計である4個目をdと表現
足した後、bがaになりcがb、dがcになると考えそれぞれを代入し、それを47回繰り返す!!
※ 47としているのは最初に3個の値を代入しているため50から3を引いた47としています。

tribonacci.rb
a = 1
b = 3
c = 7
n = 0
while n < 47
  d = a + b + c
  a = b
  b = c
  c = d
  n += 1
end

puts c

最後のcが47個目の数字になる!!

これだ!!

この考えをもう少し丁寧に表現して...

tribonacci.rb
puts "求めたい数字を入力して下さい"
puts "1つ目の数字"
a = gets.to_i
puts "2つ目の数字"
b = gets.to_i
puts "3つ目の数字"
c = gets.to_i
puts "何番目の数字を求めますか?"
t = gets.to_i

n = 0
while n < (t - 3)
  d = a + b + c
  a = b
  b = c
  c = d
  n += 1
end

puts "#{t}番目の数は#{c}です"

これで50個目の数字17079382868243を求めることができました!!
正確な時間は測ってませんが、なんとか10分以内で実装しました。

おわりに

もっと良い計算方法があると思いますが、低学歴の私には10分以内で表現するのはこれぐらいが限界でした。
皆様はどうでしたか?10分以内って結構焦りますよね?
Wikipediaで5行くらいで書いてるコードもあったのでもっと簡単にかけるはずですが、時間制限にテンパってしまってこんなコードになってしまいました...
エンジニアになるためには、コードを書くだけでなく数学の勉強もしなければならないと今回の件で痛感しました。

keisuke_s_nack
エラーに躓き気分転換(現実逃避...)で走るようにしていたら、フルマラソン3時間36分で走れました。 体育会系エンジニアを目指し日々奮闘しております!!
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away