Chúng tôi được cung cấp phạm vi có số bắt đầu và số kết thúc và nhiệm vụ là tính tổng số Fibonacci có sẵn giữa phạm vi đã cho theo thời gian O (Log n) và không gian O (1).
Số Fibonacci là gì
Số Fibonacci là dãy số được gọi là dãy Fibonacci trong đó mọi số mới là tổng của hai số cuối cùng trước đó.
Trong đó, f (0) =0 và f (1) =1 tức là f (0) và f (1) có vị trí cố định trong dãy và phép tính sẽ bắt đầu từ số thứ ba.
Công thức được sử dụng để tính toán trình tự là -
F n =F n-1 + F n-2
Ở đâu,
F 0 =0, F 1 = l
Ví dụ
Input − start = 6 and last = 100 Output − Number of fibonacci Numbers in the series are 6
Giải thích - số fibonacci từ 6 đến 100 là 8, 13, 21, 34, 55, 89, tức là tổng số là 6
Input − start = 0 and last = 8 Output − Number of fibonacci Numbers in the series are 7
Giải thích - số fibonacci từ 0 đến 8 là 0, 1, 1, 2, 3, 5, 8 tức là tổng số là 7
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập số bắt đầu và số kết thúc để tạo một phạm vi
-
Khai báo và khởi tạo fib1 thành 0, fib2 thành 1, fib3 thành 1
-
Khai báo một biến tạm thời res và khởi tạo nó bằng 0
-
Bắt đầu một vòng lặp, trong khi fib1 nhỏ hơn hoặc bằng để kết thúc
-
Bên trong vòng lặp, hãy kiểm tra xem fib1 lớn hơn hoặc bằng với giá trị bắt đầu rồi tăng res lên 1
-
Đặt fib1 thành fib2, fib2 thành fib3 và fib3 thành fib1 + fib2
-
Trả lại res
-
In kết quả
Ví dụ
#include <bits/stdc++.h>
using namespace std;
// function to count fibonacci numbers in range
// from start to last
int count_fibonacci(int start, int last){
// First three Fibonacci Numbers
int fib1 = 0, fib2 = 1, fib3 = 1;
// res to count the number of fibonacci
int res = 0;
while (fib1 <= last){
if (fib1 >= start){
res++;
}
fib1 = fib2;
fib2 = fib3;
fib3 = fib1 + fib2;
}
return res;
}
// main function
int main(){
int start = 6, last = 100;
cout << "Number of fibonacci Numbers in the series are "
<< count_fibonacci(start, last);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Number of fibonacci Numbers in the series are 6