資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告