Tribonacci Sequence, CodeWars Kata

https://www.codewars.com/kata/556deca17c58da83c00002db/

Well met with Fibonacci bigger brother, AKA Tribonacci.

As the name may already reveal, it works basically like a Fibonacci, but summing the last 3 (instead of 2) numbers of the sequence to generate the next. And, worse part of it, regrettably I won't get to hear non-native Italian speakers trying to pronounce it :(

So, if we are to start our Tribonacci sequence with [1, 1, 1] as a starting input (AKA signature), we have this sequence:

[1, 1 ,1, 3, 5, 9, 17, 31, ...]

But what if we started with [0, 0, 1] as a signature? As starting with [0, 1] instead of [1, 1] basically shifts the common Fibonacci sequence by once place, you may be tempted to think that we would get the same sequence shifted by 2 places, but that is not the case and we would get:

[0, 0, 1, 1, 2, 4, 7, 13, 24, ...]

Well, you may have guessed it by now, but to be clear: you need to create a fibonacci function that given a signature array/list, returns the first n elements - signature included of the so seeded sequence.

Signature will always contain 3 numbers; n will always be a non-negative number; if n == 0, then return an empty array (except in C return NULL) and be ready for anything else which is not clearly specified ;)

If you enjoyed this kata more advanced and generalized version of it can be found in the Xbonacci kata

[Personal thanks to Professor Jim Fowler on Coursera for his awesome classes that I really recommend to any math enthusiast and for showing me this mathematical curiosity too with his usual contagious passion :)]

 

피보나치수열은 이전 두 개의 요소 합으로 진행된다면, 트리보나치는 이전 세 개의 요소의 합으로 진행됩니다. 첫 번째 예제처럼 [1, 1, 1]이 주어진다면 다음 진행은 [1, 1, 1, (1+1+1 = 3)]이 되겠지요.

인풋은 다음과 같습니다.

1) 트리보나치의 시그니처 배열: 0 또는 양의 정수 3개

2) 출력 배열(트리보나치 수열)의 크기

 

My Solution

피보나치 수열을 구하는 메커니즘과 거의 유사하기 때문에 금방 풀었습니다. 출력 배열의 크기만큼 미리 배열을 늘려두고 루프를 통해 처리했습니다. for문에서 시작을 4번째 배열로 잡았습니다. 이전 배열의 합으로 진행되는 첫 번째 구간이기 때문입니다. 그러면 별도의 escape 없이 ArrayIndexOutOfBoundsException을 피할 수 있습니다.

솔루션 코드

테스트 코드

package com.codewars;

import java.util.Arrays;

public class TribonacciSequence {
    public double[] tribonacci(double[] s, int n) {
        double[] result = Arrays.copyOf(s, n);
        for (int i = 3; i < n; i++) {
            result[i] = result[i - 1] + result[i - 2] + result[i - 3];
        }
        return result;
    }
}

 

Best Practice

제가 작성한 솔루션이 BP와 동일합니다.

 

728x90
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기

댓글을 달아 주세요

">