蓝桥杯 未名湖的烦恼 fun(m-1,n)+fun(m,n-1)这句代码详细解释

Question

#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;

}

Answer 1

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个，继续递归求这种情况的队伍合法数量。