ตัวเลขฟีโบนักชีเป็นตัวเลขที่ทุกตัวเลขในอนุกรมหลังจากสองตัวแรกเป็นผลรวมของสองตัวก่อนหน้า ชุดเริ่มต้นด้วย 1, 1 ตัวอย่าง −
1, 1, 2, 3, 5, 8, 13, 21, 34, ….
เราสามารถเขียนโปรแกรมเพื่อสร้าง nth ได้ดังนี้ −
functionfibNaive(n) {
if (n<= 1) return n;
returnfibNaive(n - 1) + fibNaive(n - 2);
} คุณสามารถทดสอบได้โดยใช้ −
console.log(fibNaive(7)); console.log(fibNaive(8)); console.log(fibNaive(9)); console.log(fibNaive(4));
สิ่งนี้จะให้ผลลัพธ์ -
13 21 34 3
ให้เราดูว่าการเรียกใช้ฟังก์ชันเหล่านี้เกิดขึ้นจริงได้อย่างไร -
/** * f(5) * / \ * f(4) f(3) * / \ / \ * f(3) f(2) f(2) f(1) * / \ .......... * f(2) f(1).......... */
เมื่อเราโทรไปที่ f(5) เราจะโทรหา f(2) เกือบ 4 ครั้ง และจะเรียกใช้รหัสเดิมซ้ำแล้วซ้ำอีก 4 ครั้ง นี่เป็นกรณีของปัญหาย่อยที่ทับซ้อนกัน ลองใช้ฟังก์ชันนั้นในราคา 500 คุณจะค้างอยู่เพราะการโทรทั้งหมดจะใช้เวลามาก
เมื่อเราต้องการเลขฟีโบนักชีที่ 5 เราแค่ต้องการตัวเลขฟีโบนักชีที่ต่ำกว่าหนึ่งครั้ง แต่เราคำนวณหลายครั้งมากกว่านั้น เราสามารถลดการคำนวณที่ซ้ำซ้อนนี้ได้ หากเราเก็บค่าที่คำนวณไว้ไว้ที่ใดที่หนึ่งแทน นี่คือหัวใจสำคัญของการเขียนโปรแกรมแบบไดนามิก
คำนวณเพียงครั้งเดียวและนำมาใช้ใหม่ในภายหลัง
มาดูการใช้งานฟังก์ชัน fib ที่บันทึกไว้
letfibStore = {};
functionfibDP(n) {
if (n<= 1) return n;
if (fibStore[n]) {
returnfibStore[n];
}
fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
returnfibStore[n];
} ตอนนี้เราใช้ร้านค้า fibStore เพื่อติดตามค่าที่เราได้คำนวณไปแล้ว ซึ่งจะช่วยลดการคำนวณซ้ำซ้อนที่มากเกินไปและทำให้ฟังก์ชันทำงานได้อย่างมีประสิทธิภาพ
คุณสามารถทดสอบได้โดยใช้ −
console.log(fibDP(7)); console.log(fibDP(8)); console.log(fibDP(9)); console.log(fibDP(4));
สิ่งนี้จะให้ผลลัพธ์ -
13 21 34 3
คุณยังสามารถทดสอบสิ่งนี้เพื่อหาค่ามหาศาลได้อีกด้วย
