数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在C++中，以O(Log n)时间和O(1)空间复杂度计算给定区间内的斐波那契数个数
给定一个起始数字和结束数字构成的区间，任务是在O(Log n)时间和O(1)空间内计算该区间内斐波那契数的总数。
什么是斐波那契数？
斐波那契数是一个数列，称为斐波那契数列，其中每个新数都是其前两个数的和。
其中，f(0) = 0，f(1) = 1，即f(0)和f(1)在数列中位置固定，计算从第三个数开始。
用于计算数列的公式为：
Fn = Fn-1 + Fn-2
其中：
F0 = 0, F1 = 1
例如
Input − start = 6 and last = 100 Output − Number of fibonacci Numbers in the series are 6
说明 - 6到100之间的斐波那契数是8, 13, 21, 34, 55, 89，总数为6。
Input − start = 0 and last = 8 Output − 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小于或等于结束数字时。
在循环内，检查fib1是否大于或等于起始数字，如果是，则将res加1。
设置fib1为fib2，fib2为fib3，fib3为fib1 + fib2。
返回res。
打印结果。
示例
#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
更新于：2020年5月15日
529 次查看
广告