DAY 15
0

# 今日kata

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.
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, ...]
``````

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.

Tribonacci數列的規則是:

• 第四項是第一項+第二項+第三項之和，同理第五項是第二項+第三項+第四項之和
• 第四項開始，每一項是前三項之和

``````tribonacci([1,1,1],10) ----> [1,1,1,3,5,9,17,31,57,105]
tribonacci([0,0,1],10) ----> [0,0,1,1,2,4,7,13,24,44]
``````

## 構想&解法

``````function tribonacci(signature, n) {
if (n < 4) {
return signature.slice(0, n)
}
while (n > 3) {
let len = signature.length
signature.push(signature[len - 1] + signature[len - 2] + signature[len - 3])
n--
}
return signature
}
``````

``````signature= [0,  0,  1]
//          n0  n1  n2
//                      n3----->每次loop所要計算的
// n3= n0 + n1 + n2 = n2 + n1 + n0
// len= signature.length 陣列長度
//    = signature[len - 1] + signature[len - 2] + signature[len - 3]
``````

## 其他解法觀摩

``````function tribonacci(signature,n){
for (var i = 0; i < n-3; i++) { // iterate n times
signature.push(signature[i] + signature[i+1] + signature[i+2]); // add last 3 array items and push to trib
}
return signature.slice(0, n); //return trib - length of n
}
``````

## 整理用法

### 費氏數列

`遞迴`是把一個問題拆分成好幾個小的獨立問題。常見就是把`規律` `重複`執行的部分抽出來處理，而函式的遞迴指的就是自己呼叫自己。

``````// F(n)=F(n-1)+F(n-2)
// F0=0, F1=1
function fibonacci(n){
if(n<=1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
``````

• 第一層fibonacci(5)
• n>1，返回fibonacci(4)+fibonacci(3)
• 第二層fibonacci(4) + fibonacci(3)
• fibonacci(4)=fibonacci(3)+fibonacci(2)
• fibonacci(3)=fibonacci(2)+fibonacci(1)
• 第三層fibonacci(3)+fibonacci(2) & fibonacci(2)+fibonacci(1)
• fibonacci(3)=fibonacci(2)+fibonacci(1)
• fibonacci(2)=fibonacci(1)+fibonacci(0)
• fibonacci(1)=1