计算O(Log n)时间中给定范围内的斐波那契数和C ++中O(1)空间中的斐波那契数

给定具有开始和结束编号的范围,任务是计算在O(Log n)时间和O(1)空间中给定范围之间可用的斐波那契数的总数。

什么是斐波那契数

斐波那契数是称为斐波那契数列的数字序列,其中每个新数字都是前两个数之和。

其中,f= 0和f(1)= 1,即f和f(1)在序列中具有固定位置,并且计算将从第三个数字开始。

用于计算序列的公式是-

F n = F n-1 + F n-2

哪里,

F 0 = 0,F 1 = 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

以上是 计算O(Log n)时间中给定范围内的斐波那契数和C ++中O(1)空间中的斐波那契数 的全部内容, 来源链接: utcz.com/z/349030.html

回到顶部