นับจำนวนฟีโบนัชชีในช่วงที่กำหนด O(Log n) และ O(1) space ใน C++

เราได้รับช่วง start และ end งานคือการนับจำนวนฟีโบนัชชีในช่วงนั้น โดยใช้เวลา O(log n) และพื้นที่ O(1)

ลำดับฟีโบนัชชี

F₀=0, F₁=1, Fₙ=Fₙ₋₁+Fₙ₋₂ ลำดับ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

ตัวอย่าง

Input − start = 6, last = 100 Output − 6

คำอธิบาย − ฟีโบนัชชีในช่วง: 8, 13, 21, 34, 55, 89

Input − start = 0, last = 8 Output − 7

คำอธิบาย − 0, 1, 1, 2, 3, 5, 8 รวม 7 ตัว

แนวทางการแก้ปัญหา

• สร้างลำดับฟีโบนัชชีแบบ iterative: fib1=0, fib2=1, fib3=1
• วนลูป while fib1 <= last
• ถ้า fib1 >= start เพิ่มตัวนับ
• อัปเดต: fib1=fib2, fib2=fib3, fib3=fib1+fib2
• ใช้พื้นที่คงที่ O(1) และเวลา O(log φ(max)) ≈ O(log n)

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

#include <bits/stdc++.h>
using namespace std;

int countFibonacci(int start, int last) {
    int fib1 = 0, fib2 = 1, fib3 = 1;
    int count = 0;
    
    while (fib1 <= last) {
        if (fib1 >= start) count++;
        fib1 = fib2;
        fib2 = fib3;
        fib3 = fib1 + fib2;
    }
    return count;
}

int main() {
    int start = 6, last = 100;
    cout << "Fibonacci count: " << countFibonacci(start, last);
    return 0;
}

ผลลัพธ์

Fibonacci count: 6