首页 > 代码库 > 蓝桥杯 算法训练 ALGO-150 6-1 递归求二项式系数值

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

  算法训练 6-1 递归求二项式系数值  
时间限制:10.0s   内存限制:256.0MB
问题描述
技术分享
样例输入
一个满足题目要求的输入范例。
3 10
样例输出
与上面的样例输入对应的输出。
技术分享
数据规模和约定
  输入数据中每一个数的范围。
  例:结果在int表示时不会溢出。
 
题目解析:
  对于递归问题,我们注意两点:(1)找出口;(2)找相似性。
  有题目中我们得知: (1)出口已经找到: 当 k = 0 或 k = n 时,结果为 1.
            (2)相似性也找到了:当 0 < k < n 时,递归调用 技术分享

 

示例代码:

 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 }

 

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