Cho khoảng [start, end], đếm số lượng số Fibonacci nằm trong khoảng đó với độ phức tạp O(log n) thời gian và O(1) không gian.
Số Fibonacci
Dãy: F₀=0, F₁=1, Fₙ=Fₙ₋₁+Fₙ₋₂. Dãy: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
Ví dụ
Input - start = 6, last = 100 Output - 6
Giải thích - Các số Fibonacci: 8, 13, 21, 34, 55, 89.
Input - start = 0, last = 8 Output - 7
Giải thích - 0, 1, 1, 2, 3, 5, 8.
Phương pháp tiếp cận
- Khởi tạo fib1=0, fib2=1, fib3=1
- While fib1 ≤ last:
- Nếu fib1 ≥ start: count++
- Cập nhật: fib1=fib2, fib2=fib3, fib3=fib1+fib2
- Chỉ dùng 3 biến, không dùng mảng/đệ quy → O(1) space
Ví dụ code C++
#include <bits/stdc++.h>
using namespace std;
int count_fibonacci(int start, int last) {
int fib1 = 0, fib2 = 1, fib3 = 1;
int res = 0;
while (fib1 <= last) {
if (fib1 >= start) res++;
fib1 = fib2;
fib2 = fib3;
fib3 = fib1 + fib2;
}
return res;
}
int main() {
int start = 6, last = 100;
cout << "Number of fibonacci Numbers in the series are " << count_fibonacci(start, last);
return 0;
}
Kết quả
Number of fibonacci Numbers in the series are 6