首页 > 专题系列 > Java解POJ > POJ 2249 Binomial Showdown [解题报告] Java
2013
11-11

POJ 2249 Binomial Showdown [解题报告] Java

Binomial Showdown

问题描述 :

In how many ways can you choose k elements out of n elements, not taking order into account?

Write a program to compute this number.

输入:

The input will contain one or more test cases.

Each test case consists of one line containing two integers n (n>=1) and k (0<=k<=n).

Input is terminated by two zeroes for n and k.

输出:

For each test case, print one line containing the required number. This number will always fit into an integer, i.e. it will be less than 231.

Warning: Don’t underestimate the problem. The result will fit into an integer – but if all intermediate results arising during the computation will also fit into an integer depends on your algorithm. The test cases will go to the limit.

样例输入:

4 2
10 5
49 6
0 0

样例输出:

6
252
13983816

解题代码:

//* @author  [email protected]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {    
    static long[][] M=new long[2000][2000];
    public static long comb(int n,int k){
        if(k>(n/2))k=n-k;
        if(n< 2000&&k< 2000) return M[n][k];
        else if(k==n||k==0) return 1;
        else if(k==1) return n;
        else return comb(n-1,k)+comb(n-1,k-1);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token;
        int n=0,k=0;
        for(int i=0;i< 2000;i++){
            M[i][i]=1;
            M[i][0]=1;
            M[i][1]=i;
            M[0][i]=0;
        }
        for(int i=1;i< 2000;i++){
            for(int j=2;j< 2000;j++){
                if(i!=j){
                    M[i][j]=M[i-1][j-1]+M[i-1][j];
                }
            }
        }
        while(true){
          token=new StringTokenizer(stdin.readLine());
           n=Integer.parseInt(token.nextToken());
           k=Integer.parseInt(token.nextToken());
           if(k==0&&n==0) break;
           System.out.println(comb(n,k));
        }
    }
}

  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。