目录
1 问题描述
问题描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）
每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）
输入格式
两个整数，表示m和n
输出格式
一个整数，表示队伍的排法的方案数。
样例输入
3 2
样例输出
5
数据规模和约定
m,n∈［0,18］
问题分析
问题分析
2 解决方案
2.1 递归法
共有m个人还鞋，n个人借鞋，记最终排列数为f(m, n)。
现在求m和n的排队情况，具体理解如下：
起始，要去一人还鞋(PS:此时，m = m - 1)，还完后，可以选一人还鞋(PS：m = m - 1)或者一人借鞋(PS:n = n - 1)。
那么，f(m , n) = f(m - 1, n) + f(m, n - 1)。这就是求取f(m, n)的递推公式，那么轻易可知当m < n时，f(m, n) = 0；当n = 0时，f(m, 0) = 1。
具体代码如下：
package com.liuzhen.systemExe; import java.util.Scanner; public class Main{ //m代表还鞋的人数，n代表借鞋的人数 public int getArrange(int m, int n) { if(m < n) return 0; if(n == 0) return 1; return getArrange(m - 1, n) + getArrange(m, n - 1); } public static void main(String[] args){ Main test = new Main(); Scanner in = new Scanner(System.in); // System.out.println("请分别输入还鞋人数m和和借鞋人数n："); int m = in.nextInt(); int n = in.nextInt(); System.out.println(test.getArrange(m, n)); } }
运行结果：
请分别输入还鞋人数m和和借鞋人数n： 3 2 5 请分别输入还鞋人数m和和借鞋人数n： 12 7 23256
2.2 递推法
具体代码如下：
package com.liuzhen.systemExe; import java.util.Scanner; public class Main{ //m代表还鞋的人数，n代表借鞋的人数 public int getArrange1(int m, int n) { int[][] result = new int[m + 1][n + 1]; //初始化元素全为0 for(int i = 1;i <= m;i++) { result[i][0] = 1; //当借鞋的人数为0时，排列只有一种情况 for(int j = 1;j <= n;j++) { if(i >= j) //当i小于j时，排列总数为0 result[i][j] = result[i - 1][j] + result[i][j - 1]; } } return result[m][n]; } public static void main(String[] args){ Main test = new Main(); Scanner in = new Scanner(System.in); // System.out.println("请分别输入还鞋人数m和和借鞋人数n："); int m = in.nextInt(); int n = in.nextInt(); System.out.println(test.getArrange1(m, n)); } }
运行结果：
请分别输入还鞋人数m和和借鞋人数n： 12 7 23256 请分别输入还鞋人数m和和借鞋人数n： 4 3 14
参考资料：
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
