[已解决]递归问题

学习电脑

题目
问题描述
　　每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
　　每天早上，租鞋窗口都会排起长龙，假设有还鞋的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)这样的语句要怎么理解？

最佳答案

月排行榜 / 总排行榜

jerryxjr1220

2017-3-11 08:14:05

学习电脑 发表于 2017-3-10 19:55
不是，我是不太理解怎么想到要相加的，以前用到递归没见过相加的

很多情况都会相加啊，当f(x)包含f(x-1)的时候，就会把f(x-1)加上，这个要看具体题目来分析的。

跳转到最佳答案楼层

jerryxjr1220

帮你列了一个表，不知道能不能帮你理解。
其实很简单，把前几种情况，都想清楚，递归就自然清楚了。
举例，
当归还<租借的情况肯定没有排列，因为都没有鞋子可租，所以i<j的情况，排列为0，我用灰色标注了。
再看租借为0的情况，表示无论归还多少鞋子，只有1种排列，所以j==0，排列为1，我用黄色标注了。
其他情况，分别对应表格f（i-1，j）和f（i，j-1）的情况，看看是否符合预期？
想明白了，递归就自然成立了。

学习电脑

jerryxjr1220 发表于 2017-3-6 10:33
帮你列了一个表，不知道能不能帮你理解。
其实很简单，把前几种情况，都想清楚，递归就自然清楚了。
举 ...

谢谢，但是什么情况要用到两个相加呢？

jerryxjr1220

学习电脑 发表于 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）相加，从表中就可以看出来，你仔细对着表看看。

不是，我是不太理解怎么想到要相加的，以前用到递归没见过相加的

jerryxjr1220

学习电脑 发表于 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)加上，这个要看具体题目来分析的。

好，谢谢