#OJ2038. 递归求组合数

递归求组合数

递归求组合数

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

从n个不同元素中,任取k(k≤n)个元素并成一组,叫做从n个不同元素中取出k个元素的一个组合;从n个不同元素中取出k(k≤n)个元素的所有组合的个数,叫做从n个不同元素中取出k个元素的组合数,记作C(n,k)。 组合数C(n,k)满足下面三个公式: (1) C(n, k) = n! / ((n - k)! * k!) (2) C(n, k) = C(n - 1, k - 1) + C(n - 1, k) (3) C(n, k) = C(n, n - k) 例如: (1) C(5, 3) = 5! / ( (5 - 3)! * 3! ) = (5 * 4 * 3) / (3 * 2 * 1) (2) C(5, 3) = C(4, 2) + C(4, 3) (3) C(5, 3) = C(5, 2) = (5 * 4) / (2 * 1) 现在要求你用递归的方法来求解一个组合数,公式(2)是组合数的递归公式。

Invalid Word(禁用单词)错误:在解决这个题目时,某些关键词是不允许被使用的。如果提交的程序中包含了下列的关键词之一,就会产生这个错误。 被禁用的关键字:循环语句for、while,甚至包括分支语句的switch、case、goto、break。 被禁用的头文件:math.h、stdlib.h。

Input

输入为两个正整数n和k。输入不保证k≤n。满足n,k≤25。

Output

输出一个整数:从n个不同元素中取出k个元素的组合数。

Sample Input

5 3

Sample Output

10

HINT

当k>n时,就是从n个元素中选出比n多的元素来,那是不可能的,也就是组合数为0。