求出这m+n个人排队购票，使得售票处 不至于 出现找不开钱的局面的 不同排队 种数。(注意,允许出现0种哦.)

​

/* 双参 递归案例题: /

/ 一场球赛开始之前，售票工作正在紧张的进行中。

每张球票为50元。

现有m+n个人排队等待购票，

其中有m个人手持50元的钞票，

另外n个人手持100元的钞票。

求出这m+n个人排队购票，使得售票处 不至于 出现找不开钱的局面的 不同排队 种数。(注意,允许出现0种哦.)

约定，拿 同样面值钞票的人 对换位置后为 同一种排队。

输入

输入m,n (m<100, n<100)

输出

输出排队种数

样例输入

15,12

样例输出

4345965

提示

算法思路

定义函 数f(m,n) 表示m个人手持50元，n个人手持100元共有的排队种数

这里有两个参量m,n ,情况会麻烦些.

先从 简单/极端 的情况入手讨论.(对这类情况的讨论往往为递归出口的处理和设计提供了便利):

当n=0,没有手持100元的人排队，这个情况是找得开钱 f(m,0) =1

当m<n,(手持50元的人数小于手持100元的人数) f(m,n)=0

其他情况(m>n>0)

又分为两种情况,但这次采用逆向(逆推)的思维考虑递推

(是否感觉到,当大一些规模的问题要受较小规模时的解决方案的影响时,多多考虑递归的方案)

而分类(无论时一个参量还是两个参量)思维会将递归的威力进一步发挥出来…以及边逆推还原场景,边分类讨论.

当 第 m+n 个人 手持100元，他 之前 的m+n-1个人 有m个人手持50元，n-1个人手持100元，共有的排队种数为f(m,n-1)

当第m+n个人手持50元，他之前的m+n-1个人有m-1个人手持50元，n个人手持100元，共有的排队种数为f(m-1,n)

根据上述情况可得到

//另外递归出口的处理和设计是十分重要的.      

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>

int f(int m,int n)
{
    if (n == 0)/* 如果在判断句中把==写作了=,那么往往出不了解过,甚至segementation fault */
    {
        return 1;
    }
    else if (m < n)
    {
        return 0;
    }
    else
    {
        /* return (一个或多个较小小规模的f()的函数表达式. */
        return f(m, n - 1) + f(m - 1, n);
    }
}
//主函数main
int main()
{
    
    int m, n;
    while (scanf("%d %d", &m, &n) != EOF)
    {
      printf("%d\n", f(m, n));
        break;
    }

    return 0;
}