第五屆藍橋杯決賽B組C/C++——出棧次序

标題：出棧次序

X星球特别講究秩序，所有道路都是單行線。一個甲殼蟲車隊，共16輛車，按照編号先後發車，夾在其它車流中，緩緩前行。路邊有個死胡同，隻能容一輛車通過，是臨時的檢查站，如圖【p1.png】所示

圖1

X星球太死闆，要求每輛路過的車必須進入檢查站，也可能不檢查就放行，也可能仔細檢查。如果車輛進入檢查站和離開的次序可以任意交錯。那麼，該車隊再次上路後，可能的次序有多少種？為了友善起見，假設檢查站可容納任意數量的汽車。顯然，如果車隊隻有1輛車，可能次序1種；2輛車可能次序2種；3輛車可能次序5種。

現在足足有16輛車啊，親！需要你計算出可能次序的數目

答案：35357670

最簡單的辦法就是遞歸，遞歸分三種情況考慮就行了

1. 當車道左邊沒車，不管這時檢查站裡面有沒有車，都隻有一種次序 return 1
2. 當左邊有車，檢查站裡面沒車，按照題目要求，每輛車都必須要進檢查站，是以左邊車的數量-1，檢查站内車的數量+1 return f(n-1,1)
3. 如果檢查站裡面有車，這種情況下的方案數是兩個遞歸的和，這兩個遞歸分别對應的情況是：左邊再來一輛車進站和從檢查站出去一輛車 return f(n - 1,m + 1) + f(n,m - 1)

#include <bits/stdc++.h>
using namespace std;
int f(int n,int m)//左邊車的數量，檢查站的中的數量 
{
	int a;
	if(n == 0)//如果左邊沒車 
		return 1;
	if(m == 0)//如果檢查站沒車，就要入站 
		return f(n - 1,1);
	if(m > 0)//如果檢查站有車 
	//分兩種情況：1.左邊再來一輛車進站 2.檢查站出去一輛車 
		return f(n - 1,m + 1) + f(n,m - 1); 
} 
int main()
{
	cout<<f(16,0);
	return 0;
}           

複制