蓝桥杯算法训练 ALGO-150 6-1 递归求二项式系数值-蒲公英云

蓝桥杯算法训练 ALGO-150 6-1 递归求二项式系数值

算法训练 6-1 递归求二项式系数值

时间限制：10.0s 内存限制：256.0MB

问题描述

format_png

样例输入

一个满足题目要求的输入范例。
3 10

样例输出

与上面的样例输入对应的输出。
format_png 1

数据规模和约定

　　输入数据中每一个数的范围。
　　例：结果在int表示时不会溢出。

题目解析：

　　对于递归问题，我们注意两点：（1）找出口；（2）找相似性。

　　有题目中我们得知：　（1）出口已经找到：当 k = 0 或 k = n 时，结果为 1.

　　　　　　　　　　　　（2）相似性也找到了：当 0 < k < n 时，递归调用 format_png 2

示例代码：

1 import java.io.BufferedReader;
 2 import java.io.IOException;
 3 import java.io.InputStreamReader;
 4 
 5 public class Main {
 6     public static void main(String[] args) throws IOException{
 7         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 8         String[] str = br.readLine().split(" ");
 9         int m = Integer.parseInt(str[0]);
10         int n = Integer.parseInt(str[1]);
11         
12         int coefficient = binomialCoe(m,n);
13         
14         System.out.println(coefficient);
15     }
16 
17     private static int binomialCoe(int k, int n) {
18         if( k == 0 || k ==n)
19             return 1;
20         return binomialCoe( k , n-1 ) + binomialCoe( k-1 , n-1 );
21     }
22 }