階剩演算法

『壹』 Google:有100階樓梯，從底往上爬，每次爬1階或2階，編演算法說明共有多少走法

設 f(x) = 上x層樓的方法數，那麼，顯然

f(1) = 1
f(2) = 2

因為只有1層樓的話，只有一種方法可以走完，那就是直接走一階；
只有2層樓的話，可以走兩步一階，或者走一步2階，共兩種走法；

考慮一般的 x (x >= 3)：
假如你現在面對 x 層樓梯，你只有兩種選擇：

1. 要麼走一階，變成還剩 x-1 層，這種情況下剩下的樓層共有 f(x-1) 種走法。
2. 要麼走兩階，變成 x-2 層，這種情況下剩下的樓層共有 f(x-2) 種走法。

所以對於一般的 x 層樓梯，你實際上有 f(x-1) + f(x-2) 種走法。

於是就得到了一個遞推公式：

f(1) = 1
f(2) = 2
f(x) = f(x-1) + f(x-2) (x >= 3)

『貳』 求演算法高手解釋一下

因為{ [(3*k+6)!] % (3*k+7) + 1 } / (3*k+7) = m;
而[(3*k+6)!] % (3*k+7)的取值范圍是[0,3*k+6];
所以m的取值只有兩種可能：
當[(3*k+6)!] % (3*k+7) < 3*k+6 時，m = 0;
當[(3*k+6)!] % (3*k+7) = 3*k+6 時，m = 1;
根據費馬小定理：
若一個數是素數P，令 W = (1*2*3***P-1)，則 W≡W(mod p） 注釋：≡是同餘符號。
所以當(3*k+7)為素數的時候，[(3*k+6)!] % (3*k+7) = 3*k+6， m = 1; 此時n可取1。
同理當(3*k+7)不是素數的時候n可取0。
費馬小定理網上有很多知識，你可以自己去搜搜看。
下面我給你貼上網路裡面的解釋：

一、准備知識：
引理1．剩餘系定理2
若a,b,c為任意3個整數，m為正整數，且（m,c)=1，則當ac≡bc(mod m）時，有a≡b(mod m)
證明：ac≡bc(mod m）可得ac–bc≡0(mod m）可得（a-b)c≡0(mod m）因為（m,c)=1即m,c互質，c可以約去，a–b≡0(mod m）可得a≡b(mod m)
引理2．剩餘系定理5
若m為整數且m>1,a[1],a[2],a[3],a[4]，…a[m]為m個整數，若在這m個數中任取2個整數對m不同餘，則這m個整數對m構成完全剩餘系。
證明：構造m的完全剩餘系（0,1,2，…m-1），所有的整數必然這些整數中的1個對模m同餘。取r[1]=0,r[2]=1,r[3]=2,r[4]=3，…r[i]=i-1,1<i<=m。令（1）：a[1]≡r[1](mod m),a[2]≡r[2](mod m),a≡r(mod m）（順序可以不同），因為只有在這種情況下才能保證集合{a1,a2,a3,a4，…am}中的任意2個數不同餘，否則必然有2個數同餘。由式（1）自然得到集合{a1,a2,a3,a4，…am}對m構成完全剩餘系。
引理3．剩餘系定理7
設m是一個整數，且m>1，b是一個整數且（m,b)=1。如果a1,a2,a3,a4，…am是模m的一個完全剩餘系，則ba[1],ba[2],ba[3],ba[4]，…ba[m]也構成模m的一個完全剩餘系。
證明：若存在2個整數ba和ba[j]同餘即ba≡ba[j](mod m），根據引理1則有a≡a[j](mod m）。根據完全剩餘系的定義和引理4（完全剩餘系中任意2個數之間不同餘，易證明）可知這是不可能的，因此不存在2個整數ba和ba[j]同餘。由引理5可知ba[1],ba[2],ba[3],ba[4]，…ba[m]構成模m的一個完全剩餘系。
引理4．同餘定理6
如果a,b,c,d是四個整數，且a≡b(mod m),c≡d(mod m），則有ac≡bd(mod m)
證明：由題設得ac≡bc(mod m),bc≡bd(mod m），由模運算的傳遞性可得ac≡bd(mod m)
二、證明過程：
構造素數p的完全剩餘系P={1,2,3,4…（p-1)}，因為（a,p)=1，由引理3可得A={a,2a,3a,4a，…（p-1)a}也是p的一個完全剩餘系。令W=1*2*3*4…*(p-1），顯然W≡W(mod p）。令Y=a*2a*3a*4a*…（p-1)a，因為{a,2a,3a,4a，…（p-1)a}是p的完全剩餘系，由引理2以及引理4可得a*2a*3a*…（p-1)a≡1*2*3*…（p-1)(mod p）即W*a^(p-1）≡W(modp）。易知（W,p)=1，由引理1可知a^(p-1）≡1(modp）

『叄』 關於愛因斯坦的階梯問題答案不懂如題 謝謝了

因為只有每步上7階，最後一階也不剩,所以台階總數一定是7的倍數, 這應該是個計算機演算法吧, X=X+7意思就是在原來的數上加7, 也就是用7的1. 2 . 3 ... 倍數去試, 直到有一個數符合題中的全部條件

『肆』 誰知道1×2×3×4×5×6×7×8×9的簡便演算法 簡便演算法

這是一個高中的階剩問題,是沒有簡便的,靠記.
它可寫成9!=363880

『伍』 排序演算法概述

十大排序演算法：冒泡排序，選擇排序，插入排序，歸並排序，堆排序，快速排序、希爾排序、計數排序，基數排序，桶排序

穩定 ：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；
不穩定 ：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；
排序演算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，前一個鍵排序的結果可以為後一個鍵排序所用。

演算法的復雜度往往取決於數據的規模大小和數據本身分布性質。
時間復雜度 ： 一個演算法執行所耗費的時間。
空間復雜度 ：對一個演算法在運行過程中臨時佔用存儲空間大小的量度。
常見復雜度由小到大 ：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

在各種不同演算法中，若演算法中語句執行次數(佔用空間)為一個常數，則復雜度為O(1)；
當一個演算法的復雜度與以2為底的n的對數成正比時，可表示為O(log n)；
當一個演算法的復雜度與n成線性比例關系時，可表示為O (n)，依次類推。

冒泡、選擇、插入排序需要兩個for循環，每次只關注一個元素，平均時間復雜度為
（一遍找元素O(n)，一遍找位置O(n)）
快速、歸並、堆基於分治思想，log以2為底，平均時間復雜度往往和O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）相關
而希爾排序依賴於所取增量序列的性質，但是到目前為止還沒有一個最好的增量序列 。例如希爾增量序列時間復雜度為O(n²)，而Hibbard增量序列的希爾排序的時間復雜度為 ， 有人在大量的實驗後得出結論;當n在某個特定的范圍後希爾排序的最小時間復雜度大約為n^1.3。

從平均時間來看，快速排序是效率最高的：
快速排序中平均時間復雜度O(nlog n)，這個公式中隱含的常數因子很小，比歸並排序的O(nlog n)中的要小很多，所以大多數情況下，快速排序總是優於合並排序的。

而堆排序的平均時間復雜度也是O(nlog n)，但是堆排序存在著重建堆的過程，它把根節點移除後，把最後的葉子結點拿上來後需要重建堆，但是，拿上的值是要比它的兩個葉子結點要差很多的，一般要比較很多次，才能回到合適的位置。堆排序就會有很多的時間耗在堆調整上。

雖然快速排序的最壞情況為排序規模（n）的平方關系，但是這種最壞情況取決於每次選擇的基準， 對於這種情況，已經提出了很多優化的方法，比如三取樣劃分和Dual-Pivot快排。
同時，當排序規模較小時，劃分的平衡性容易被打破，而且頻繁的方法調用超過了O(nlog n)為
省出的時間，所以一般排序規模較小時，會改用插入排序或者其他排序演算法。

一種簡單的排序演算法。它反復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。這個工作重復地進行直到沒有元素再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為元素會經由交換慢慢「浮」到數列的頂端。
1.從數組頭開始，比較相鄰的元素。如果第一個比第二個大(小)，就交換它們兩個；
2.對每一對相鄰元素作同樣的工作，從開始第一對到尾部的最後一對，這樣在最後的元素應該會是最大(小)的數；
3.重復步驟1~2，重復次數等於數組的長度，直到排序完成。

首先，找到數組中最大（小）的那個元素；
其次，將它和數組的第一個元素交換位置（如果第一個元素就是最大（小）元素那麼它就和自己交換）；
再次，在剩下的元素中找到最大（小）的元素，將它與數組的第二個元素交換位置。如此往復，直到將整個數組排序。
這種方法叫做選擇排序，因為它在不斷地選擇剩餘元素之中的最大（小）者。

對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。
為了給要插入的元素騰出空間，我們需要將插入位置之後的已排序元素在都向後移動一位。
插入排序所需的時間取決於輸入中元素的初始順序。例如，對一個很大且其中的元素已經有序（或接近有序）的數組進行排序將會比對隨機順序的數組或是逆序數組進行排序要快得多。
總的來說，插入排序對於部分有序的數組十分高效，也很適合小規模數組。

一種基於插入排序的快速的排序演算法。簡單插入排序對於大規模亂序數組很慢，因為元素只能一點一點地從數組的一端移動到另一端。例如，如果主鍵最小的元素正好在數組的盡頭，要將它挪到正確的位置就需要N-1 次移動。
希爾排序為了加快速度簡單地改進了插入排序，也稱為縮小增量排序，同時該演算法是突破O(n^2）的第一批演算法之一。
希爾排序是把待排序數組按一定數量的分組，對每組使用直接插入排序演算法排序；然後縮小數量繼續分組排序，隨著數量逐漸減少，每組包含的元素越來越多，當數量減至 1 時，整個數組恰被分成一組，排序便完成了。這個不斷縮小的數量，就構成了一個增量序列。

在先前較大的增量下每個子序列的規模都不大,用直接插入排序效率都較高，盡管在隨後的增量遞減分組中子序列越來越大,由於整個序列的有序性也越來越明顯,則排序效率依然較高。
從理論上說，只要一個數組是遞減的，並且最後一個值是1，都可以作為增量序列使用。有沒有一個步長序列,使得排序過程中所需的比較和移動次數相對較少,並且無論待排序列記錄數有多少,演算法的時間復雜度都能漸近最佳呢？但是目前從數學上來說，無法證明某個序列是「最好的」。
常用的增量序列
希爾增量序列 ：{N/2, (N / 2)/2, ..., 1}，其中N為原始數組的長度，這是最常用的序列，但卻不是最好的
Hibbard序列：{2^k-1, ..., 3,1}
Sedgewick序列：{... , 109 , 41 , 19 , 5，1} 表達式為

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法的一個非常典型的應用。
對於給定的一組數據，利用遞歸與分治技術將數據序列劃分成為越來越小的半子表，在對半子表排序後，再用遞歸方法將排好序的半子表合並成為越來越大的有序序列。
為了提升性能，有時我們在半子表的個數小於某個數（比如15）的情況下，對半子表的排序採用其他排序演算法，比如插入排序。
若將兩個有序表合並成一個有序表，稱為2-路歸並，與之對應的還有多路歸並。

快速排序（Quicksort）是對冒泡排序的一種改進，也是採用分治法的一個典型的應用。
首先任意選取一個數據（比如數組的第一個數）作為關鍵數據，我們稱為基準數(Pivot)，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序，也稱為分區（partition）操作。
通過一趟快速排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數組變成有序序列。
為了提升性能，有時我們在分割後獨立的兩部分的個數小於某個數（比如15）的情況下，會採用其他排序演算法，比如插入排序。

基準的選取：最優的情況是基準值剛好取在無序區數值的中位數，這樣能夠最大效率地讓兩邊排序，同時最大地減少遞歸劃分的次數，但是一般很難做到最優。基準的選取一般有三種方式，選取數組的第一個元素，選取數組的最後一個元素，以及選取第一個、最後一個以及中間的元素的中位數（如4 5 6 7, 第一個4, 最後一個7, 中間的為5, 這三個數的中位數為5, 所以選擇5作為基準）。
Dual-Pivot快排：雙基準快速排序演算法，其實就是用兩個基準數, 把整個數組分成三份來進行快速排序，在這種新的演算法下面，比經典快排從實驗來看節省了10%的時間。

許多應用程序都需要處理有序的元素，但不一定要求他們全部有序，或者不一定要一次就將他們排序，很多時候，我們每次只需要操作數據中的最大元素（最小元素），那麼有一種基於二叉堆的數據結構可以提供支持。
所謂二叉堆，是一個完全二叉樹的結構，同時滿足堆的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。在一個二叉堆中，根節點總是最大（或者最小）節點。
堆排序演算法就是抓住了這一特點，每次都取堆頂的元素，然後將剩餘的元素重新調整為最大（最小）堆，依次類推，最終得到排序的序列。

推論1：對於位置為K的結點 左子結點=2 k+1 右子結點=2 (k+1)
驗證：C:2 2 2+1=5 2 (2+1)=6
推論2：最後一個非葉節點的位置為 (N/2)-1，N為數組長度。
驗證：數組長度為6，(6/2)-1=2

計數排序對一定范圍內的整數排序時候的速度非常快，一般快於其他排序演算法。但計數排序局限性比較大，只限於對整數進行排序，而且待排序元素值分布較連續、跨度小的情況。
計數排序是一個排序時不比較元素大小的排序演算法。
如果一個數組里所有元素都是整數，而且都在0-K以內。對於數組里每個元素來說，如果能知道數組里有多少項小於或等於該元素，就能准確地給出該元素在排序後的數組的位置。

桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，利用某種函數的映射關系將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序）。
桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當於快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然後只需要對桶中的少量數據做排序即可。

常見的數據元素一般是由若干位組成的，比如字元串由若干字元組成，整數由若干位0~9數字組成。基數排序按照從右往左的順序，依次將每一位都當做一次關鍵字，然後按照該關鍵字對數組排序，同時每一輪排序都基於上輪排序後的結果；當我們將所有的位排序後，整個數組就達到有序狀態。基數排序不是基於比較的演算法。
基數是什麼意思？對於十進制整數，每一位都只可能是0~9中的某一個，總共10種可能。那10就是它的基，同理二進制數字的基為2；對於字元串，如果它使用的是8位的擴展ASCII字元集，那麼它的基就是256。

基數排序 vs 計數排序 vs 桶排序

基數排序有兩種方法：
MSD 從高位開始進行排序
LSD 從低位開始進行排序
這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數排序：根據鍵值的每位數字來分配桶
計數排序：每個桶只存儲單一鍵值
桶排序：每個桶存儲一定范圍的數值

有時，待排序的文件很大，計算機內存不能容納整個文件，這時候對文件就不能使用內部排序了（我們一般的排序都是在內存中做的，所以稱之為內部排序，而外部排序是指待排序的內容不能在內存中一下子完成，它需要做內外存的內容交換），外部排序常採用的排序方法也是歸並排序，這種歸並方法由兩個不同的階段組成：
採用適當的內部排序方法對輸入文件的每個片段進行排序，將排好序的片段（成為歸並段）寫到外部存儲器中（通常由一個可用的磁碟作為臨時緩沖區），這樣臨時緩沖區中的每個歸並段的內容是有序的。
利用歸並演算法，歸並第一階段生成的歸並段，直到只剩下一個歸並段為止。

例如要對外存中4500個記錄進行歸並，而內存大小隻能容納750個記錄，在第一階段，我們可以每次讀取750個記錄進行排序，這樣可以分六次讀取，進行排序，可以得到六個有序的歸並段
每個歸並段的大小是750個記錄，並將這些歸並段全部寫到臨時緩沖區（由一個可用的磁碟充當）內了，這是第一步的排序結果。
完成第二步該怎麼做呢？這時候歸並演算法就有用處了。

『陸』 求助C語言 「愛因斯坦數學」問題

愛因斯坦的數學題
愛因斯坦出了一道這樣的數學題：有一條長階梯，若每步跨2階，則最最後剩一階，若每步跨3
階，則最後剩2階，若每步跨5階，則最後剩4階，若每步跨6階則最後剩5階。只有每次跨7階，最後才正好一階不剩。請問這條階梯共有多少階？
*題目分析與演算法設計
根據題意，階梯數滿足下面一組同餘式：
x≡1
(mod2)
x≡2
(mod3)
x≡4
(mod5)
x≡5
(mod6)
x≡0
(mod7)
*程序說明與注釋
#include<stdio.h>
void
main()
{
int
i=1;
/*i為所設的階梯數*/
while(!((i%2==1)&&(i%3==2)&&(i%5==4)&&(i%6==5)&&(i%7==0)))
++i;
/*滿足一組同餘式的判別*/
printf("Staris_number=%d\n",i);
}
*運行結果
Staris_number=119
*問題的進一步討論
此題演算法還可考慮求1、2、4、5的最小公倍數n，然後判t(t為n-1)≡0(mod7)是否成立，若不成立則t=t+n,再進行判別，直至選出滿足條件的t值。

『柒』 時間復雜度

演算法復雜度分為時間復雜度和空間復雜度，一個好的演算法應該具體執行時間短，所需空間少的特點。

隨著計算機硬體和軟體的提升，一個演算法的執行時間是算不太精確的。只能依據統計方法對演算法進行估算。

我們拋開硬體和軟體的因素，演算法的好壞直接影響程序的運行時間。

我們看一下小例子：

     int value = 0;                         // 執行了1次

     for (int i = 0; i < n; i++) {       // 執行了n次

          value += i;

     }

     這個演算法執行了 1 + n 次，如果n無限大，我們可以把前邊的1忽略，也就是說這個演算法執行了n次

     時間復雜度常用大O符號表示，這個演算法的時間復雜度就是O(n).

     概念： 一般情況下，演算法的基本操作重復執行的次數是模塊n的某一函數f(n),因此，演算法的時間復雜度記做 T(n) = O(f(n))。 隨著模塊n的增大，演算法執行的時間增長率f(n)的增長率成正比，所以f(n)越小，演算法 的時間復雜度越低，演算法的效率越高。

計算時間復雜度

     1.去掉運行時間中的所有加法常數。

     2.只保留最高階項。

     3.如果最高階項存在且不是1，去掉與這個最高階相乘的常數得到時間復雜度

我們看一個例子

     for (int i = 0; i < n; i++) {

          for (int j = i; j < n; j++) {

               // do .....

          }

     }

當 i = 0 時 裡面的fo循環執行了n次，當i等待1時裡面的for循環執行了n -  1次，當i 等於2里裡面的fro執行了n - 2次........所以執行的次數是

根據我們上邊的時間復雜度演算法

1.去掉運行時間中的所有加法常數： 沒有加法常數不用考慮

2.只保留最高階項:只保留

3. 去掉與這個最高階相乘的常數:  去掉

只剩下

最終這個演算法的時間復雜度為

再看一個線性的

      for ( int i = 0; i < n; i++) {

          // do .....

     }

     因為循環要執行n次所以時間復雜度為O(n)

其它的我也就不一個一個算了，下面給出了常用的時間復雜度

『捌』 常見演算法1——遞歸演算法

遞歸演算法就是通過自身不斷反復調用自身以解決問題，其中最經典的也就是漢諾達和斐波納契數列的問題了。
1.漢諾塔問題
在印度，有這么一個古老的傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片，一次只移動一片，不管在哪根針上，小片必在大片上面。當所有的金片都從梵天穿好的那根針上移到另外一概針上時，世界就將在一聲霹靂中消滅，梵塔、廟宇和眾生都將同歸於盡。

分析：挪到C的金片也是從下到上由大到小的順序排列，那麼A之剩下最下面的金片移動到C的時候，C上面是不可以有金片的，這個時候A上面只有第n個金片，B上面有n-1個金片，C上面沒有金片，然後這個情況就和剛開始情況相同了，只不過A和B顛倒了位置而已。
（1）n-1個金片從A通過C移動到B，n-1個金片從A通過C移動到B也是不斷調用自身逐步縮小范圍。通過遞歸調用後，就完成了A上面僅剩下最大的金片，C上面沒有金片，B上面有n-1個金片。
（2）最大的那個金片從A移動到C
（3）調用自身重復剛開始的情況，只不過現在有金片的是B，即B通過A把金片移動到C。

2.斐波納契數列
2.1生兔子問題
古典問題：3個月起每個月都生一對兔子，小兔子長到第三個月後每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？下面先從小到大分析下這個情況
分析：假設將兔子分為小中大三種，兔子從出生後從第三個月開始每個月就會生出一對兔子，也就是一旦兔子變為大兔子那麼他就生了一對兔子
分析情況圖如下

很明顯這個是一個為斐波那契數列，即如果用f(n)表示第n個月的兔子的對數，那麼f(n)=f(n-1)+f(n-2)

2.2走台階問題
一個台階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，並分析演算法的時間復雜度。
分析：假設我們現在還有最後一步要走，可能的情況有哪些？
（1）我們站在第9級上，一步1級後到達頂端；
（2）我們站在第8級上，一步2級後到達頂端；
所以，最後一步可以走1級或者2級，不外乎兩種情況。
再假設，已知從0級到9級的走法有M種，從0級到8級的走法有N種，那麼從0到10級的走法和M、N有什麼關系呢？從0到10級的走法一共是多少種呢？答案是M+N。
所以逐步遞歸，說白了，這還是個Fibnacci數列。即f(n)=f(n-1)+f(n-2)，事件復雜度是2^n

台階問題的變種:
一個台階總共有n級，如果一次可以跳1級，也可以跳2級.....也可以跳n級。求總共有多少總跳法

分析：用Fib(n)表示跳上n階台階的跳法數。如果按照定義，Fib(0)肯定需要為0，否則沒有意義。但是我們設定Fib(0) = 1；n = 0是特殊情況，通過下面的分析就會知道，強制令Fib(0) = 1很有好處。因為Fib(0)等於幾都不影響我們解題，但是會影響我們下面的分析理解。

當n = 1 時， 只有一種跳法，即1階跳：Fib(1) = 1;

當n = 2 時， 有兩種跳的方式，一階跳和二階跳：Fib(2) = 2;

到這里為止，和普通跳台階是一樣的。

當n = 3 時，有三種跳的方式，第一次跳出一階後，對應Fib(3-1)種跳法； 第一次跳出二階後，對應Fib(3-2)種跳法；第一次跳出三階後，只有這一種跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;

當n = 4時，有四種方式：第一次跳出一階，對應Fib(4-1)種跳法；第一次跳出二階，對應Fib(4-2)種跳法；第一次跳出三階，對應Fib(4-3)種跳法；第一次跳出四階，只有這一種跳法。所以，Fib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4) 種跳法。

當n = n 時，共有n種跳的方式，第一次跳出一階後，後面還有Fib(n-1)中跳法； 第一次跳出二階後，後面還有Fib(n-2)中跳法..........................第一次跳出n階後，後面還有 Fib(n-n)中跳法。Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)。

通過上述分析，我們就得到了通項公式：

因此，有 Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)

兩式相減得：Fib(n)-Fib(n-1) = Fib(n-1) =====》 Fib(n) = 2*Fib(n-1) n >= 3

這就是我們需要的遞推公式：Fib(n) = 2*Fib(n-1) n >= 3

『玖』 矩陣乘法如何計算詳細步驟!

回答：

此題2行2列矩陣乘以2行3列矩陣。

所得的矩陣是：2行3列矩陣

最後結果為： |1 3 5|

|0 4 6|

拓展資料

1、確認矩陣是否可以相乘。只有第一個矩陣的列的個數等於第二個矩陣的行的個數，這樣的兩個矩陣才能相乘。

圖示的兩個矩陣可以相乘，因為第一個矩陣，矩陣A有3列，而第二個矩陣，矩陣B有3行。

6、檢查相應的數字是否出現在正確的位置。19在左下角，-34在右下角，-2在左上角，-12在右上角。