又是遞歸題目,每次遞歸題目都有點饒人,但是一旦發現規律后就寫起來簡單了很多.
* * *
問題描述?
每年冬天，北大未名湖上都是滑冰的好地方。北大體育組準備了許多冰鞋，可是人太多了，每天下午收工后，常常一雙冰鞋都不剩。?
每天早上，租鞋窗口都會排起長龍，假設有還鞋的m個，有需要租鞋的n個。現在的問題是，這些人有多少種排法，可以避免出現體育組沒有冰鞋可租的尷尬場面。（兩個同樣需求的人（比如都是租鞋或都是還鞋）交換位置是同一種排法）?
輸入格式?
兩個整數，表示m和n?
輸出格式?
一個整數，表示隊伍的排法的方案數。?
樣例輸入?
3 2?
樣例輸出?
5?
數據規模和約定?
m,n∈［0,18］?
問題分析?
* * *
就四種情況,?抽象一下,m是還鞋的,n是租鞋的,?
1.m小于么是肯定不夠租的,所以次數是0?
2.m大于等于n,這個時候開始排隊,第一個肯定排m還鞋的人,此時第二個任意,要么排m,要么排n.如果第二個排n那么第三個肯定是m,就這樣一直排下去即可?
代碼:
~~~
import java.util.Scanner;
public class Main {
static int m,n;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
m = input.nextInt();
n = input.nextInt();
if (m<n){
System.out.println(0);
}else {
System.out.println(fun(m,n));
}
}
private static int fun(int x,int y){
if (x ==0 ||y ==0){
return 1;
}//排隊人數中還鞋的等于租謝的
else if (m-x == n-y){
return fun(x-1,y);
}//排隊人數中還鞋的大于租謝的
else if (m-x>n-y){
return fun(x-1,y)+fun(x,y-1);
}else {
return 0;
}
}
}
~~~
