问题描述
- 蓝桥杯 未名湖的烦恼 fun(m-1,n)+fun(m,n-1)这句代码详细解释
-
#include "iostream"using namespace std;
int fun(int m,int n)
{
if(m
{
return 0;
}
else if (n==0)
{
return 1;
}
else return fun(m-1,n)+fun(m,n-1);
}
int main()
{
int m,n;
cout
cin>>m>>n;cout<<"有"<<fun(m,n)<<"排序方法"<<endl;
return 0;
}
解决方案
fun（m,n）表示的是在还鞋的有m个，借鞋子的有n个的情况下，排队合法的情况的个数。也就是对m+n个人进行排队，且保证按照正确规则排列的队伍的数量。
fun(m-1,n)+fun(m,n-1)拆成fun(m-1,n)，fun(m,n-1)：
fun(m-1,n)表示当前最前面的一个位置，作为还鞋子的位置，那么剩下的人进行排队，能具有的合法的队伍的数量（合法指的是满足条件的队伍）。
fun(m,n-1)表示当前最前面的一个位置，作为借鞋子的位置，那么剩下的人进行排队，能具有的合法的队伍的数量。
整理一下思路：
队伍长度为m+n,那么最前面的一个位置是换鞋子或者是借鞋子的话对后面的情况都是有影响的，如果最前面的位置是还鞋子的话，那么剩下的队伍长度为（m-1）+n，其中还鞋子的为m-1个，借鞋子的为n个，继续递归求这种情况的队伍合法数量
；如果最前面的位置是借鞋子的话，那么剩下的队伍长度为m+（n-1），其中还鞋子的为m个，借鞋子的为n-1个，继续递归求这种情况的队伍合法数量。
解决方案二：
fun(m-1,n) 这个意思是还鞋子的一个站在最前面，然后剩下的人再进行排列;
fun(m,n-1) 意思是借鞋子的一个站在最后面，剩下的人再排列。
解决方案三：
这都是什么人啊，ysuwood 的回答有什么问题，居然还点了踩。
这不就是递归么，每一个组合都可以分为m-1,n和,n-1两个组合的并集。
lz有什么不理解的可以继续问。
解决方案四：
这就是递归函数，方法中调用自身