在c語言期末考試中，再次見到了“小明爬樓梯”問題，而第一次見到是在某次面試題中，由于當時還沒有學到遞歸部分，因此就僅僅把代碼看了一下，然而其中包含的思想卻沒有弄清楚，因此在考試時見到該題一頭霧水，因此總結一下，以絕后患。

先上題：

---

可愛的小明特別喜歡爬樓梯，他有的時候一次爬一個臺階，有的時候一次爬兩個臺階，有的時候一次爬三個臺階。如果這個樓梯有n個臺階，小明一共有多少種爬法呢？

---

該題為典型的遞歸問題，解決的思想當然就要不按常理出牌:
假設當前共有36階臺階，小明若想到達第36階臺階，只能選擇從第35階再上1階，或從第34階再上2階，或從第33階再上3階，因此要想到達第36階臺階，需要走的步數為到達之前3級臺階需要的步數之和，即f(n) = f(n-1) + f(n-2) + f(n-3).

示例代碼: #include <stdio.h>int f(int n){if(n == 1)return 1;if(n == 2)return 2;if(n == 3)return 4;return f(n-1) + f(n-2) + f(n-3);}int main (void){int n;printf("請輸入臺階數:\n");scanf("%d", &n);printf("所需步數為:%d\n", f(n));return 0;}

到這里就結束了嗎？沒有！！！雖然用遞歸做很直觀，但是遞歸卻造成了運行速度相對而言是極慢的，因此再附上一份稍微復雜那么一丟丟但是運行速度快的代碼:

#include<stdio.h> int f(int n){n++;int i;int table[n]; //存儲臺階數為n時爬樓梯的類別數for(i=0;i<n;i++)table[i]=0;table[1]=1;table[2]=2;table[3]=4;for(i=4;i<n;i++){table[i]=table[i-1]+table[i-2]+table[i-3];}return table[n-1]; }int main(){int n;printf("請輸入臺階數:\n");scanf("%d", &n);printf("%d\n",f(n));return 0; }

注：本題應考慮數字范圍的問題，由于考試時只有幾組簡單的測試數據，因此僅僅使用了int型數據，未使用long long型數據。

總結

以上是生活随笔為你收集整理的再见“小明爬楼梯”问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。