資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式：查詢第N個偶數斐波那契數
在這個問題中，我們給定一個整數N。我們的任務是找到第N個偶數斐波那契數。
斐波那契數列透過將前兩個數相加來生成後續的數。斐波那契數列從兩個數開始 - F0 & F1。F0 & F1 的初始值可以分別取 0, 1 或 1, 1。
讓我們舉個例子來理解這個問題，
Input : N = 4 Output : 144
解決方案
解決這個問題的一個簡單方法是利用斐波那契數列中每三個數就有一個偶數，並且偶數序列也遵循遞迴公式這一事實。
偶數斐波那契數列的遞迴公式為 -
Ef(n)= 4Ef(n-1) + Ef(n-2) 其中 Ef(0)=0 且 Ef(1)=2
我們知道，每三個斐波那契數中就有一個是偶數，因此 f(n-3) 和 f(n-6) 都是偶數。所以，我們將 f(n) 視為第 k 個元素，並表示為 Ef(k)。如果 f(n) 是 Ef(k)，則 f(n-3) 是前一個偶數，表示為 Ef(k-1)，因此 f(n-6) 是 Ef(k-1) 的前一個，即 Ef(k-2)。
因此 f(n)=4f(n-3)+f(n-6)
或者，Ef(k)=4Ef(k-1) + Ef(k-2)。
示例
程式說明解決方案的工作原理，
#include<iostream>
using namespace std;
int findNthEvenFiboNum(int n){
if (n < 1)
return n;
if (n == 1)
return 2;
return ((4 * findNthEvenFiboNum(n-1)) + findNthEvenFiboNum(n- 2));
}
int main (){
int n = 5;
cout<<n<<"th even fibonacci number is "<<findNthEvenFiboNum(n);
return 0;
}輸出
5th even fibonacci number is 610
更新於: 2022年2月11日
534 次檢視
廣告