問(wèn)題描述
每年冬天，北大未名湖上都是滑冰的好地方穷娱。北大體育組準(zhǔn)備了許多冰鞋绑蔫，可是人太多了，每天下午收工后泵额，常常一雙冰鞋都不剩配深。
每天早上，租鞋窗口都會(huì)排起長(zhǎng)龍嫁盲，假設(shè)有還鞋的m個(gè)凉馆，有需要租鞋的n個(gè)。現(xiàn)在的問(wèn)題是亡资，這些人有多少種排法，可以避免出現(xiàn)體育組沒有冰鞋可租的尷尬場(chǎng)面向叉。（兩個(gè)同樣需求的人（比如都是租鞋或都是還鞋）交換位置是同一種排法）
輸入格式
兩個(gè)整數(shù)锥腻，表示m和n
輸出格式
一個(gè)整數(shù)，表示隊(duì)伍的排法的方案數(shù)母谎。
樣例輸入
3 2
樣例輸出
5
數(shù)據(jù)規(guī)模和約定
m,n∈［0,18］
問(wèn)題分析
題目標(biāo)簽給的是遞歸 遞推瘦黑，我們來(lái)從遞歸角度來(lái)分析這個(gè)問(wèn)題：
- 第一天全租出去后，剩余鞋為0，假設(shè)第二天我們有一隊(duì)還鞋和借鞋的人(人數(shù)分別記為s,b)待處理
- 在不會(huì)出現(xiàn)尷尬局面的情況下幸斥，管理員處理到s或b的人數(shù)為零的情況下就得到了一種分配方案匹摇，因此這個(gè)條件可以作為遞歸基
- 如果不要出現(xiàn)沒有冰鞋可租的情況，那么來(lái)的第一個(gè)人一定是還鞋的甲葬，后面緊接著的就既可以是還鞋的也可以是借鞋的廊勃，以此類推，情況分類:
- 前面剩余的s只要一小于b经窖，那么剩下來(lái)的一個(gè)就必須是還鞋的
2.如果s剩>=b剩坡垫，那剩下來(lái)的就和第一個(gè)情況一樣，既可以是還鞋的也可以是借鞋的
那么遞歸條件也有了画侣，下面是代碼:
#include <iostream>
using namespace std;
int n,m; //第二天待處理的借還人數(shù)
int bs_shoes(int s,int b); //表示要借和還的還剩多少個(gè)
int main(){
cin>>n>>m;
if(n<m)
cout<<0<<endl;
else{
cout<<bs_shoes(n,m)<<endl;
}
return 0;
}
int bs_shoes(int s,int b){
if(s==0 || b==0)
return 1;
if(n-s == m-b){
return bs_shoes(s-1,b);
}else if(n-s > m-b){ /*借完之后還剩的 待還人數(shù)如果大于待借人數(shù)冰悠，那么情況隨意*/
return bs_shoes(s-1,b) + bs_shoes(s,b-1);
}
return 0;
}
