35
31

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Posted at

はじめに

低学歴の筆者がトリボナッチ数列の問題を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行くらいで書いてるコードもあったのでもっと簡単にかけるはずですが、時間制限にテンパってしまってこんなコードになってしまいました...
エンジニアになるためには、コードを書くだけでなく数学の勉強もしなければならないと今回の件で痛感しました。

35
31
20

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
35
31

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?