การหาพจน์ที่ n ของลำดับปาดอวาน (Padovan Sequence) ใน JavaScript

ลำดับปาดอวาน (Padovan Sequence)

ลำดับปาดอวานคือลำดับจำนวนเต็ม P(n) ที่กำหนดโดยค่าเริ่มต้น:

P(0) = P(1) = P(2) = 1

และความสัมพันธ์ซ้ำ (recurrence relation):

P(n) = P(n-2) + P(n-3)

ค่าแรกๆ ของ P(n) คือ:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, …

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับตัวเลข n และคืนค่าพจน์ที่ n ของลำดับปาดอวาน

ตัวอย่าง

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

const num = 32;
const padovan = (num = 1) => {
  let secondPrev = 1, pPrev = 1, pCurr = 1, pNext = 1;
  for (let i = 3; i <= num; i++) {
    pNext = secondPrev + pPrev;
    secondPrev = pPrev;
    pPrev = pCurr;
    pCurr = pNext;
  }
  return pNext;
};
console.log(padovan(num));

ผลลัพธ์

5842

คำอธิบายเพิ่มเติม

ลำดับปาดอวานเกี่ยวข้องกับลำดับฟีบอนัชชีและมีการประยุกต์ใช้ในเรขาคณิตและสถาปัตยกรรม โค้ดใช้ Dynamic Programming แบบเก็บค่าแค่ 3 ตัวล่าสุด (O(1) space) ซึ่งมีประสิทธิภาพดี