ALGO-122–未名湖边的烦恼
最后更新于：2022-04-01 09:41:39
又是递归题目,每次递归题目都有点饶人,但是一旦发现规律后就写起来简单了很多.
* * *
问题描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙，假设有还鞋的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;
}
}
}
~~~