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

本是古典何须时尚 2023-10-06 09:40 12阅读 0赞

算法训练 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 }

[format_png]: http://imgconvert.csdnimg.cn/aHR0cDovL2x4LmxhbnFpYW8uY24vUmVxdWlyZUZpbGUuZG8_ZmlkPTVEeWZCUnlH?x-oss-process=image/format,png
[format_png 1]: http://imgconvert.csdnimg.cn/aHR0cDovL2x4LmxhbnFpYW8uY24vUmVxdWlyZUZpbGUuZG8_ZmlkPXQ3akx5NURE?x-oss-process=image/format,png
[format_png 2]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDQvMTExOTA5Ny0yMDE3MDQxMDE4MjU0MDY4OC05OTk2MjMzMjcucG5n?x-oss-process=image/format,png