20251119-ITSA-第 6 題

前言

#

這次我把使用者名稱命名為「Ciallo～(∠・ω< )⌒☆」，就寫出了 5 題（一共 7 題），看來這是某種東方島國的神祕力量，下次也這麼叫好了。

題目

#

題目如下 :

問題描述:

#

在太空訓練中心，一名宇航員正在進行艙梯爬升訓練。 艙梯共有 n 個踏階，宇航員每次可以踩上一個踏階，或一口氣跨過一個踏階（即一次 跨兩階）。他想知道，自己從最底層出發，能有多少種不同的方式爬到最上層。 請你幫他計算共有多少種上升方法。

輸入說明:

#

輸入一個整數 n，代表艙梯的總踏階數（3 ≤ n ≤ 20）。

輸出說明:

#

輸出從底部到頂端的所有不同爬升方法總數。 最後要有換行符號。

範例

#

怎解 ?

#

基本上有能力用程式寫出費波那契數列就有辦法解出這一題，是的，這題其實只是在問費波那契數列😂

• 階梯數 = 0 ，甚麼都不做也是一種解法
• 階梯數 = 1 ，只有走 1 階這種解法，走 2 階就掉到地圖邊界外
• 階梯數 = 2 ，可以先走 1 階再走 1 階，或是直接走 2 階，所以共 2 種解法
• 階梯數 = 3 ，來到了階梯數 = 3 ，我們當然可以把所有走法窮舉出來，但有更聰明的做法 :
  • 想一下走到第 n 階是甚麼意思 ? 當你走到第 n 階只會有 2 種情況
    1. 從 n-1 階走 1 步到第 n 階
    2. 從 n-2 階走 2 步到第 n 階
  • 所以事實上第 n 階的走法只要把 「n-1 階的走法」 + 「n-2 階的走法」加起來就行了😋表示成數學公式長這樣 : $$f(n)=f(n-1)+f(n-2)$$
  • 你會發現，這其實是遞迴程式入門常常出現的費波那契數列，所以階梯數 = 3 的走法會是 1 + 2 =3 !
• 階梯數 = 4，2 + 3 = 5 種
• 階梯數 = 5，5 + 3 = 8 種
• 以此類推…

程式

#

#include<iostream>
#include<vector>
using namespace std;
int main(){
	vector<int>yy(30); //題目有提到艙梯的總踏階數（3 ≤ n ≤ 20），這裡保險一點設 30
	yy[0] = 1; // 0 階和 1 階有 1 種方法
	yy[1] = 1;
	
	for(int i = 2 ; i <30 ; ++i){
	    yy[i] = yy[i-1] + yy[i-2]; //費式數列
	}
	
	int n;
	while(cin>>n){
	    cout<<yy[n]<<endl; //輸出對應階數
	}
}