[Ruby] I tried solving the problem of Tribonacci sequence with Ruby (time limit 10 minutes)

2 minute read

Introduction

It is an experience note that I was able to solve the problem of Tribonacci sequence within 10 minutes by a writer with a low educational background and forget the word Tribonacci (memory loss state) within 10 minutes with ruby. I will. For those who are confident in mathematics or not, why don’t you try it in less than 10 minutes as a strength test?

Problem

Question 1 1,3,7,11,21,39… What is the 50th number?

Now we have to solve the problem…

…(;゚Д゚)

I lost consciousness for about 10 seconds, but I have to understand the current situation for the time being! !! I changed my mind.

About Tribonacci sequence

A Tribonacci sequence is a sequence in which the number of a term is the sum of the numbers of the three terms before it… It seems that you will study at the junior high school entrance exam, but what did you eat yesterday? My amnesia with only level memory didn’t go away (…currently 30 years old)

Search results…

What is the Tribonacci number? … omitted a[0]=a[1]=0 a[2]=1 a[n]=a[n-1]+a[n-2]+a[n-3] Sequence defined as Find the general terms of this sequence. 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ⁿ…

~~ No, I can’t understand it in 10 minutes! !! ~~ I gave up on understanding and expressed it in ruby based on my own interpretation.

My interpretation

1st + 2nd + 3rd = 4th 2nd + 3rd + 4th = 5th repeat Tokoroden-style method ← completely different

The first is a, the second is b, the third is c, and the total fourth is d. After adding, we think that b becomes a, c becomes b, and d becomes c, and we substitute each one and repeat it 47 times! !! *47 is the value obtained by subtracting 3 from 50 because 47 values are assigned first.

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

The last c becomes the 47th number! !!

This is it! !!
Express this idea a little more carefully…

tribonacci.rb


puts "Please enter the desired number"
puts "first number"
a = gets.to_i
puts "second number"
b = gets.to_i
puts "third number"
c = gets.to_i
puts "What number do you want?"
t = gets.to_i

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

puts "The #{t} number is #{c}"

Now you can find the fiftieth number 17079382868243! !! I haven’t measured the exact time, but I managed to implement it within 10 minutes.

in conclusion

I think there is a better calculation method, but for me with low educational background, this was the limit to express within 10 minutes. How was everyone? You’re pretty rushed within 10 minutes, right? I had some code on Wikipedia that I wrote in about 5 lines, so it should be easier to write, but I was tempted by the time limit and ended up with this code… In this case, I realized that in order to become an engineer, I had to study not only the code but also the math.

Tags:

Updated: