1、未名湖畔的烦恼

题目描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）

输入格式　
两个整数m、n

输出格式　　
一个整数。该整数表示队伍排法的方案数。

样例
输入3 2，输出5

数据规模和约定　　
m,n∈［0,18］

#include <iostream>
#include <stdlib.h>
using namespace std;
int fun(int m, int n)
{
	if (m < n)
		return 0;
	if (n == 0)
		return 1;
	return fun(m - 1, n) + fun(m, n - 1);
}
int main()
{
	int returnNum, rentNum;
	cout << "还鞋人数returnNum(0~18)：";
	cin >> returnNum;
	cout << "租鞋人数rentNum(0~18)：";
	cin >> rentNum;
	cout << "方案数：" << fun(returnNum, rentNum) << endl;
	system("pause");
	return 0;
}

【碎碎念】
刚开始刷算法题，这是第一道遇见的有难度的题，靠我自己的水平是想不到答案的。我花费了一个半小时在找每个输出之间的规律，比如当m = 5, n = 1,2,3,4,5时各个方案数的联系，事实是这是徒劳的，没有规律可循。即便写出了几个符合的算法，也还是有例外。很明显，我这种思想体现了我的算法水平是如何的低…于是乎我搜索了答案。在看了多个别人的理解后，我有了自己的理解，目前来说，我只是能看懂，能否做到举一反三？
【理解】
1、首先要明确的：根据一个大神的讲解，我知道了该递归算法的排列是倒着来的，也就是说，先看队伍的第五个人是换鞋还是借鞋…原因是若不这样做，我们无法做到让算法在先对第一个人进行排列时保证他是来还鞋的。而先看队伍的第五个人是换鞋还是借鞋，最后再根据判断n是否为0来确保队伍上的第一个人是还鞋的。这样，就保证了第一个人是还鞋的。
2、然后我根据实例进行了验证。有五种方式，如下：
1、未名湖畔的烦恼
3、开始分析意义。第⑤条路径最短最好分析！会有很惊奇的发现！从下往上分析，这是肯定的呐。

（3,0）表示还有3个要还鞋的人还没排呢。但是不用排了呀。因为算法排出的结果为BBAAA，但实际排队效果为AAABB！所以！到这里你会发现…m - 1表示我这一步把某个还鞋的人安排了，n - 1表示我这一步把某个借鞋的人安排了！（Oh，当然，我比较愚钝，可能你早就发现了…）因此！各个路径从上到下下来的结果分别如下（实际效果与之相反）：
①ABAB(A)
②ABBA(A)
③BAAB(A)
④BABA(A)
⑤BBAA(A)

4、看懂整个算法后，进行总结。

每次走完整个流程，符合n = 0的话，就表示刚才走的路径符合要求，所以返回1，表示这是一种方式。
我不知道一个题要具备怎样的特征就要去想着应该用递归去做；更不知道如果需要写递归的话，这个递归应该是怎样的。
把m、n的减1看做对其进行了安排，也就想爬台阶那个题的减1、减2表示你实际爬台阶的行动。
先不总结了…做的题比较少的原因吧，总结不出来个啥。也许等做多了就会有所感悟…我会再来写的！

1、未名湖畔的烦恼

相关推荐