ผลรวมกำลังสองของจำนวนฟีโบนัชชีใน C++

จำนวนฟีโบนัชชี (Fibonacci Numbers)

ลำดับที่เริ่มจาก 0, 1 และตัวถัดไป = ผลรวมของสองตัวก่อนหน้า

F0 = 0, F1 = 1
Fn = Fn-1 + Fn-2 (n ≥ 2)

ลำดับ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

ปัญหา

หาผลรวมของกำลังสองของจำนวนฟีโบนัชชี n ตัวแรก

สูตร: Σ(i=0 to n) Fi²

ตัวอย่าง n = 4: 0² + 1² + 1² + 2² + 3² = 0 + 1 + 1 + 4 + 9 = 15

คุณสมบัติทางคณิตศาสตร์

มีสูตรลัด: Σ(i=0 to n) Fi² = Fn × Fn+1

ตัวอย่าง: n=4, F4=3, F5=5 → 3×5=15 ✓

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

#include <iostream>
using namespace std;

int main() {
    int n = 4;
    int first = 0, second = 1, next;
    int sum = 0;
    
    for (int c = 0; c <= n; c++) {
        if (c <= 1)
            next = c;
        else {
            next = first + second;
            first = second;
            second = next;
        }
        sum += next * next;
    }
    
    cout << "Sum of squares of first " << n+1 << " Fibonacci numbers: " << sum;
    return 0;
}

ผลลัพธ์

Sum of squares of first 5 Fibonacci numbers: 15

โค้ดแบบใช้สูตรลัด (มีประสิทธิภาพมากกว่า)

long long fib(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n = 4;
    long long Fn = fib(n);
    long long Fn1 = fib(n + 1);
    cout << "Sum = " << Fn * Fn1; // 3 * 5 = 15
    return 0;
}