欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++中實(shí)現(xiàn)fibonacci數(shù)列的幾種方法

 更新時(shí)間：2022年01月24日 11:32:42   作者：關(guān)關(guān)在干嘛  
本文主要介紹了C++中實(shí)現(xiàn)fibonacci數(shù)列的幾種方法，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

前言

fibonacci數(shù)列的實(shí)現(xiàn)主要有三種方法：遞歸、循環(huán)與矩陣。這里主要學(xué)習(xí)了如何在C++中實(shí)現(xiàn)這三種方法以及分析它們各自的時(shí)間復(fù)雜度。

本文參考文章如下：http://www.dbjr.com.cn/article/235674.htm

一、fibonacci數(shù)列是什么？

斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞推的方法定義：F(0)=0，F(xiàn)(1)=1，F(xiàn)(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

二、遞歸實(shí)現(xiàn)

1.遞歸的特點(diǎn)

  • 遞歸：函數(shù)自己調(diào)用自己
  • 遞歸的"缺陷"：遞歸到一定程度，會發(fā)生"棧溢出"
  • 遞歸的"時(shí)間復(fù)雜度"：遞歸總次數(shù)*每次遞歸的次數(shù)
  • 遞歸的"空間復(fù)雜度"：遞歸的深度*每次遞歸空間的大小（注意："每次遞歸空間的大小"是個(gè)常數(shù)，可以基本忽略不計(jì)）
  • 遞歸的"深度"：樹的高度（遞歸的過程是一個(gè)"二叉樹"）

2.C++實(shí)現(xiàn)

int main(){
? ? int n;
? ? long long sum; ?
? ??
? ? scanf("%d",&n);
? ? sum =fb(n); ?
? ? printf("%lld\n",sum);
? ??
? ? return 0;
}
?
long long fb(int n){
? ? if(n<1){
? ? ? ? return 0;
? ? ? ??
? ? }else if(n==1||n==2){
? ? ? ? return 1;
? ? }
? ? return (fb(n-1)+fb(n-2));
}

3.時(shí)間復(fù)雜度

二叉樹的高度是 n - 1，一個(gè)高度為k的二叉樹最多可以有 2^k - 1個(gè)葉子節(jié)點(diǎn)，也就是遞歸過程函數(shù)調(diào)用的次數(shù)，所以時(shí)間復(fù)雜度為 O(2^n)，而空間復(fù)雜度就是樹的高度 O(n)。

三、循環(huán)實(shí)現(xiàn)

1.C++實(shí)現(xiàn)

long long Fib(long long N)
{
? ? long long first = 1;
? ? long long second = 1;
? ? long long ret = 0;
? ? for (int i = 3; i <=N; ++i)
? ? {
? ? ? ? ret = first + second;
? ? ? ? first = second;
? ? ? ? second = ret;
? ? }
? ? return second;
}
int main()
{
? ? long long num = 0;
? ? num=Fib(10);
? ? printf("循環(huán)：%d\n", num);
? ? system("pause");
? ? return 0;
}

2.時(shí)間復(fù)雜度

  • 時(shí)間復(fù)雜度：O(N)
  • 空間復(fù)雜度：O(1)（創(chuàng)建了四個(gè)對象，是常數(shù)，所以可忽略不計(jì)）

四、矩陣實(shí)現(xiàn)

1.理論推導(dǎo)

斐波那契數(shù)列的遞推公式是：f(n)=f(n-1)+f(n-2);

 在線性代數(shù)中，類似于斐波那契數(shù)列這種遞推式稱為二階遞推式。我們可以用f(n)=af(n-1)+bf(n-2)將二階遞推式一般化。只要符合這種二階遞推式的算法，都可以將算法的時(shí)間復(fù)雜度降為O(logN)。當(dāng)然，三階，四階....都可以，只要得到遞推公式的n階矩陣即可。如下：

     f(n)=af(n-1)+bf(n-2)+......

     (f(n),f(n-1))=(f(n-1),f(n-2))*matrix;(matrix是一個(gè)矩陣，幾階遞推式就是幾階的矩陣，在這里是二階的矩陣，斐波那契數(shù)列屬于二階)

……………………①

………………②

于是只要求得即可。

而類似求還可以簡化（快速冪）

例如：

10^68，我們通常是10*10乘上68次，這樣時(shí)間效率為O(N),我們要用O(logN)方法算:

     68的二進(jìn)制序列為：1000100

     10^68=10^64*10^4，也就是取出68二進(jìn)制序列為1的位，其他忽略。這樣我們只算了7次（二進(jìn)制序列的長度）就可以算出10^68，效率就達(dá)到了O(logN)。（最優(yōu)化算法的關(guān)鍵所在）

所以時(shí)間復(fù)雜度可以達(dá)到最優(yōu)化O（logN）。

2.C++實(shí)現(xiàn)

struct Matrix2By2 {
? ? Matrix2By2(long long m00 = 0, long long m01 = 0, long long m10 = 0,?? ?long long m11 = 0)
? ? ? ? :m_00(m00), m_01(m01), m_10(m10), m_11(m11) {}
? ? long long m_00, m_01, m_10, m_11;
};
?
Matrix2By2 MatrixMultiply(const Matrix2By2& matrix1, const Matrix2By2& matrix2) {
? ? return Matrix2By2( ?matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
? ? ? ? ? ? ? ? ? ? ? ? matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
? ? ? ? ? ? ? ? ? ? ? ? matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
? ? ? ? ? ? ? ? ? ? ? ? matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11 ? ?);
}
?
Matrix2By2 MatrixPower(unsigned int n) {
? ? assert(n > 0);
? ? Matrix2By2 matrix;
? ? if (n == 1)
? ? ? ? matrix = Matrix2By2(1, 1, 1, 0);
? ? else if (n % 2 == 0) {?? ?// n是偶數(shù)
? ? ? ? matrix = MatrixPower(n / 2);
? ? ? ? matrix = MatrixMultiply(matrix, matrix);
? ? }
? ? else if (n % 2 == 1) {?? ?// n是奇數(shù)
? ? ? ? matrix = MatrixPower((n - 1) / 2);
? ? ? ? matrix = MatrixMultiply(matrix, matrix);
? ? ? ? matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
? ? }
? ? return matrix;
}
?
long long Fibonacci_Solution3(unsigned int n) {
? ? if (n <= 1) return n;
? ? Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
? ? return PowerNMinus2.m_00;
}

3.時(shí)間復(fù)雜度

O（logN）。

到此這篇關(guān)于C++中實(shí)現(xiàn)fibonacci數(shù)列的幾種方法的文章就介紹到這了,更多相關(guān)C++ fibonacci數(shù)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • C++超詳細(xì)講解拷貝構(gòu)造函數(shù)

    C++超詳細(xì)講解拷貝構(gòu)造函數(shù)

    我們經(jīng)常會用一個(gè)變量去初始化一個(gè)同類型的變量，那么對于自定義的類型也應(yīng)該有類似的操作，那么創(chuàng)建對象時(shí)如何使用一個(gè)已經(jīng)存在的對象去創(chuàng)建另一個(gè)與之相同的對象呢
    2022-06-06
  • C語言中#define預(yù)處理語法總結(jié)

    C語言中#define預(yù)處理語法總結(jié)

    C語言里可以用#define定義一個(gè)標(biāo)識符來表示一個(gè)常量。特點(diǎn)是：定義的標(biāo)識符不占內(nèi)存，只是一個(gè)臨時(shí)的符號，預(yù)編譯后這個(gè)符號就不存在了，也不做類型定義。預(yù)編譯又叫預(yù)處理
    2021-11-11
  • C語言中const,指針和引用的關(guān)系

    C語言中const,指針和引用的關(guān)系

    這篇文章主要為大家介紹了C語言的const,指針和引用，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2022-01-01
  • C++ Custom Control控件向父窗體發(fā)送對應(yīng)的消息

    C++ Custom Control控件向父窗體發(fā)送對應(yīng)的消息

    這篇文章主要介紹了C++ Custom Control控件向父窗體發(fā)送對應(yīng)的消息的相關(guān)資料,需要的朋友可以參考下
    2015-06-06
  • C語言冒泡排序法的實(shí)現(xiàn)（升序排序法）

    C語言冒泡排序法的實(shí)現(xiàn)（升序排序法）

    這篇文章主要介紹了C語言冒泡排序法的實(shí)現(xiàn)（升序排序法），文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-09-09
  • Qt正則表達(dá)式使用舉例

    Qt正則表達(dá)式使用舉例

    這篇文章主要給大家介紹了關(guān)于Qt正則表達(dá)式使用的相關(guān)資料,Qt中的正則表達(dá)式模式匹配功能由QRegExp類實(shí)現(xiàn),它完全支持Unicode,并可以應(yīng)用于字符串驗(yàn)證、搜索、查找替換和分割等場景,需要的朋友可以參考下
    2024-02-02
  • C/C++中獲取數(shù)組長度的方法示例

    C/C++中獲取數(shù)組長度的方法示例

    這篇文章主要介紹了C/C++中獲取數(shù)組長度的方法,很實(shí)用的一種方法,需要的朋友可以參考下
    2014-08-08
  • c語言中形參與實(shí)參的關(guān)系解讀

    c語言中形參與實(shí)參的關(guān)系解讀

    這篇文章主要介紹了c語言中形參與實(shí)參的關(guān)系，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
    2023-07-07
  • C++實(shí)現(xiàn)LeetCode(12.整數(shù)轉(zhuǎn)化成羅馬數(shù)字)

    C++實(shí)現(xiàn)LeetCode(12.整數(shù)轉(zhuǎn)化成羅馬數(shù)字)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(12.整數(shù)轉(zhuǎn)化成羅馬數(shù)字),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C++??STL?_?Vector使用及模擬實(shí)現(xiàn)

    C++??STL?_?Vector使用及模擬實(shí)現(xiàn)

    這篇文章主要介紹了C++ STL_Vector使用及模擬實(shí)現(xiàn)，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
    2022-08-08

最新評論