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、然后我根据实例进行了验证。有五种方式,如下:
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表示你实际爬台阶的行动。
- 先不总结了…做的题比较少的原因吧,总结不出来个啥。也许等做多了就会有所感悟…我会再来写的!