Tribonacci and X-Bonacci Sequence implementation

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 ).

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;
}

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!

mascIT

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.

Codewars Profile

Tribonacci sequence, can you do it?

Leave a Reply Cancel reply