โปรแกรม C++ แสดงลำดับฟีโบนัชชี (Fibonacci Series)

ลำดับฟีโบนัชชี (Fibonacci Series) คือ ลำดับที่แต่ละพจน์เป็นผลรวมของสองพจน์ก่อนหน้า

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

ความสัมพันธ์แบบเวียนเกิด: F(n) = F(n-1) + F(n-2) โดย F(0)=0, F(1)=1

วิธีที่ 1: Dynamic Programming (Bottom-up)

#include <iostream>
using namespace std;

void fib(int n) {
    int f[n];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i < n; i++)
        f[i] = f[i-1] + f[i-2];
    for (int i = 0; i < n; i++)
        cout << f[i] << " ";
}

int main() {
    int n = 10;
    fib(n);
    return 0;
}

ผลลัพธ์

0 1 1 2 3 5 8 13 21 34

ใช้ array เก็บค่าพจน์ต่างๆ คำนวณทีละขั้นจากฐานขึ้นมา (O(n) time, O(n) space)

วิธีที่ 2: Recursive (Top-down)

#include <iostream>
using namespace std;

int fib(int n) {
    if (n <= 1)
        return n;
    return fib(n-1) + fib(n-2);
}

int main() {
    int n = 10;
    for (int i = 0; i < n; i++)
        cout << fib(i) << " ";
    return 0;
}

ผลลัพธ์

0 1 1 2 3 5 8 13 21 34

วิธีนี้เรียกฟังก์ชันซ้ำ (recursive) สร้าง overhead มาก มีเวลารัน O(2^n) เหมาะสำหรับ n เล็กเท่านั้น