ลำดับฟีบอนัชชี (Fibonacci Sequence)
ลำดับฟีบอนัชชีเป็นดังนี้
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...
ในลำดับนี้ พจน์ที่ n คือผลรวมของพจน์ที่ (n-1) และ (n-2)
เราสามารถสร้างได้โดยใช้วิธีเรียกซ้ำ (recursive approach) แต่ใน Dynamic Programming ขั้นตอนจะง่ายกว่า สามารถเก็บตัวเลขฟีบอนัชชีทั้งหมดในตาราง (table) โดยใช้ตารางนั้น สามารถสร้างพจน์ถัดไปในลำดับนี้ได้ง่าย
Input - รับหมายเลขพจน์เป็นอินพุต สมมติเป็น 10
Output - พจน์ฟีบอนัชชีที่ 10 คือ 55
อัลกอริทึม
genFiboSeries(n)
Input: จำนวนพจน์สูงสุด
Output: พจน์ฟีบอนัชชีที่ n
เริ่มต้น
ประกาศอาร์เรย์ชื่อ fibo ขนาด n+2
fibo[0] := 0
fibo[1] := 1
for i := 2 ถึง n
fibo[i] := fibo[i-1] + fibo[i-2]
คืนค่า fibo[n]
สิ้นสุด
โค้ดตัวอย่าง
#include <iostream>
using namespace std;
int genFibonacci(int n) {
int fibo[n+2];
fibo[0] = 0;
fibo[1] = 1;
for (int i = 2; i <= n; i++) {
fibo[i] = fibo[i-1] + fibo[i-2];
}
return fibo[n];
}
int main() {
int n;
cout << "Enter number of terms: ";
cin >> n;
cout << n << "th Fibonacci Terms: " << genFibonacci(n) << endl;
}
ผลลัพธ์ตัวอย่าง
Enter number of terms: 10 10th Fibonacci Terms: 55
