计算O（Log n）时间中给定范围内的斐波那契数和C ++中O(1)空间中的斐波那契数
给定具有开始和结束编号的范围，任务是计算在O（Logn）时间和O(1)空间中给定范围之间可用的斐波那契数的总数。
什么是斐波那契数
斐波那契数是称为斐波那契数列的数字序列，其中每个新数字都是前两个数之和。
其中，f=0和f(1)=1，即f和f(1)在序列中具有固定位置，并且计算将从第三个数字开始。
用于计算序列的公式是-
Fn=Fn-1+Fn-2
哪里，
F0=0，F1=l
例如
Input − start = 6 and last = 100Output − Number of fibonacci Numbers in the series are 6
说明-6到100之间的斐波那契数是8、13、21、34、55、89，即总数为6
Input − start = 0 and last = 8Output − Number of fibonacci Numbers in the series are 7
说明-0和8之间的斐波那契数是0、1、1、2、3、5、8，即总数为7
以下程序中使用的方法如下
输入开始和结束编号以创建范围
声明并初始化fib1到0，fib2到1，fib3到1
声明一个临时变量res并将其初始化为0
当fib1小于或等于end时，开始循环
在循环内部，检查fib1是否大于或等于起点，然后将res增加1
将fib1设置为fib2，将fib2设置为fib3，将fib3设置为fib1+fib2
返回资源
打印结果
示例
#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;
}输出结果
如果我们运行上面的代码，它将生成以下输出-
Number of fibonacci Numbers in the series are 6