递归问题
本帖最后由 学习电脑 于 2017-2-27 21:17 编辑题目
问题描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）
输入格式
两个整数，表示m和n
输出格式
一个整数，表示队伍的排法的方案数。
样例输入
3 2
样例输出
5
数据规模和约定
m,n∈［0,18］
答案
#include <stdio.h>
int f(int i, int j)
{
if(i < j)
return 0;
if(j == 0)
return 1;
return f(i-1,j)+f(i,j-1);
}
int main(void)
{
int m,n;
scanf("%d %d", &m,&n);
printf("%d\n", f(m,n));
return 0;
}
像f(i-1,j)+f(i,j-1)这样的语句要怎么理解？
帮你列了一个表，不知道能不能帮你理解。
其实很简单，把前几种情况，都想清楚，递归就自然清楚了。
举例，
当归还<租借的情况肯定没有排列，因为都没有鞋子可租，所以i<j的情况，排列为0，我用灰色标注了。
再看租借为0的情况，表示无论归还多少鞋子，只有1种排列，所以j==0，排列为1，我用黄色标注了。
其他情况，分别对应表格f（i-1，j）和f（i，j-1）的情况，看看是否符合预期？
想明白了，递归就自然成立了。 jerryxjr1220 发表于 2017-3-6 10:33
帮你列了一个表，不知道能不能帮你理解。
其实很简单，把前几种情况，都想清楚，递归就自然清楚了。
举 ...
谢谢，但是什么情况要用到两个相加呢？ 学习电脑 发表于 2017-3-9 09:23
谢谢，但是什么情况要用到两个相加呢？
其实每个f（i，j）都是f（i-1，j）和f（i，j-1）相加，从表中就可以看出来，你仔细对着表看看。 jerryxjr1220 发表于 2017-3-9 11:18
其实每个f（i，j）都是f（i-1，j）和f（i，j-1）相加，从表中就可以看出来，你仔细对着表看看。
不是，我是不太理解怎么想到要相加的，以前用到递归没见过相加的 学习电脑 发表于 2017-3-10 19:55
不是，我是不太理解怎么想到要相加的，以前用到递归没见过相加的
很多情况都会相加啊，当f(x)包含f(x-1)的时候，就会把f(x-1)加上，这个要看具体题目来分析的。 jerryxjr1220 发表于 2017-3-11 08:14
很多情况都会相加啊，当f(x)包含f(x-1)的时候，就会把f(x-1)加上，这个要看具体题目来分析的。
好，谢谢
页:
[1]