Tribonacci sequence, can you do it?
In this episode of Codewars explained I’m going to show you another cool kata.
It asks you to implement the popular Fibonacci, but with a different signature.
In particular it wants the so called Tribonacci, in the sense that the signature is made of 3 digits and performs 3 sums instead of the classical 2.
Let me explain better.
Assume that we want to perform Tribonacci( { 1, 1, 1 }, 6 )
- The initial signature is { 1, 1, 1 }
- We have to stop at the sixth number, then return the array.
We already have the first 3 ( it’s the signature itself ), let’s calculate the others:
4th : 1 + 1 + 1 = 3, now the array is { 1, 1, 1, 3 }
5th : 3 + 1 + 1 = 5, now the array is { 1, 1, 1, 3, 5 }
6th: 5 + 3 + 1 = 9, now the array is { 1, 1, 1, 3, 5, 9 }
At this point we have the required six numbers of the sequence and we can return it.
This is my personal implementation, written in C++, write yours in every kind of language you want.
If you missed: Splitting a “true” rectangle into squares, a simple C++ algorithm
Be careful, this solution is a more general one, since it can solve a X-Bonacci series, in the sense that it loops according to the signature size, and not according to a pre-determined number. ( Like 3 for Tribonacci ).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | std::vector<int> tribonacci(std::vector<int> signature, int n) { std::vector<int> result; // First add the signature to the result array, splitting it if necessary for ( auto i : signature ){if (result.size() < n) result.push_back(i); else return result;}; for ( int i = 0; i < n - signature.size() ; i++ ) { int sum = 0; // Sum, up to signature.size() numbers, going backwards for ( int k = 0; k < signature.size();k++) sum += result[result.size() - k - 1]; result.push_back(sum); } return result; } |
Study it and optimize it however you want!
See you to the next kata!
I’m from Italy, currently studying CS in Bari. Hobbiest Android programmer and writer, I’m a tech lover and I write here, on mascIT, every kind of guide, HOW TO and article related to the world of technology.