ลำดับ Tribonacci ใน JavaScript

ลำดับ Tribonacci

ลำดับ Tribonacci เป็นการขยายของลำดับ Fibonacci โดยแต่ละพจน์เป็นผลรวมของ 3 พจน์ก่อนหน้า

ตัวอย่างพจน์แรกๆ: 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149

ตัวอย่างโค้ด

const tribonacci = (num = 1) => {
  if (num === 0 || num === 1 || num === 2) {
    return 0;
  }
  if (num === 3) {
    return 1;
  } else {
    return tribonacci(num - 1) +
           tribonacci(num - 2) +
           tribonacci(num - 3);
  }
};

const trib = num => {
  const res = [];
  for (let i = 1; i <= num; i++) {
    res.push(tribonacci(i));
  }
  return res;
};

console.log(trib(15));

ผลลัพธ์

[ 2, 1, 4, 3, 6, 5 ]

คำอธิบายและแก้ไข

หมายเหตุ: โค้ดต้นฉบับมีปัญหาใน base case และผลลัพธ์ไม่ตรงกับนิยาม Tribonacci มาตรฐาน

Tribonacci มาตรฐาน: T(0)=0, T(1)=1, T(2)=1, T(n)=T(n-1)+T(n-2)+T(n-3)

โค้ดที่แก้ไขแล้ว:

const tribonacci = (n) => {
  if (n === 0) return 0;
  if (n === 1 || n === 2) return 1;
  return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
};

const trib = (num) => {
  const res = [];
  for (let i = 0; i < num; i++) {
    res.push(tribonacci(i));
  }
  return res;
};

console.log(trib(10)); // [0, 1, 1, 2, 4, 7, 13, 24, 44, 81]

แนะนำ: ใช้ Dynamic Programming เพื่อประสิทธิภาพ

const tribDP = (num) => {
  if (num === 0) return [];
  if (num === 1) return [0];
  if (num === 2) return [0, 1];
  const res = [0, 1, 1];
  for (let i = 3; i < num; i++) {
    res.push(res[i-1] + res[i-2] + res[i-3]);
  }
  return res;
};