首页 > 专题系列 > Java解POJ > POJ 1306 Combinations [解题报告] Java
2013
11-09

POJ 1306 Combinations [解题报告] Java

Combinations

问题描述 :

Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large. Challenges are the stuff of contests. Therefore, you are to make just such a computation given the following:

GIVEN: 5 <= N <= 100; 5 <= M <= 100; M <= N

Compute the EXACT value of: C = N! / (N-M)!M!

You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long. For the record, the exact value of 100! is:

93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621, 468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253, 697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000

输入:

The input to this program will be one or more lines each containing zero or more leading spaces, a value for N, one or more spaces, and a value for M. The last line of the input file will contain a dummy N, M pair with both values equal to zero. Your program should terminate when this line is read.

输出:

The output from this program should be in the form:

N things taken M at a time is C exactly.

样例输入:

100  6
20  5
18  6
0  0

样例输出:

100 things taken 6 at a time is 1192052400 exactly.
20 things taken 5 at a time is 15504 exactly.
18 things taken 6 at a time is 18564 exactly.

解题代码:

//* @author 洪晓鹏<[email protected]>
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(true)
		{
			int n = in.nextInt();
			int m = in.nextInt();
			int m1 = m;
			BigInteger sum1 = new BigInteger("1");
			BigInteger sum2 = new BigInteger("1");
			BigDecimal a;
			if(n == 0 && m == 0)
				break;
			if(m > n/2)
			{
				m = n - m;
			}
			for(int i = 0; i< m; i++)
			{
				sum1 = sum1.multiply(new BigInteger(String.valueOf(n-i))); 
			}
			for(int i = 0; i< m; i++)
			{
				sum2 = sum2.multiply(new BigInteger(String.valueOf(i+1)));
			}
			System.out.println(n + " things taken " + m1 +" at a time is " 
					+ sum1.divide(sum2) +" exactly.");
		}
	}

}

  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮