POJ 1306 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

Input

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.

Output

The output from this program should be in the form:
N things taken M at a time is C exactly.

Sample Input

100  6
20  5
18  6
0  0

Sample Output

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.


读完题目发现 这是一道求排列组合的。但是公式已经给出。所以也就是求公式的值。

直接使用double是可以通过的。我这里给一个延展答案。就是如果数据量真的特别大大,double也放不下的那种长度的做法。

用string计算乘法,使用辗转相除法进行约分。

注释写得比较详细,请参考代码。

简答double 和复杂计算都有, 因为参加过一次考试,和这个题目比较类似。用的比较大的数据量计算。特别遗憾。在此记录


double
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class POJ1306{

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (br.ready()) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            double N = Integer.parseInt(st.nextToken());
            double M = Integer.parseInt(st.nextToken());

            if(N == 0 && M == 0) break;

            double ans = 1;
            int idx = 0;
            for (double i = N; i > 0 ; i--) {
                ans *= i;
                idx++;

                if(idx == M) break;
            }

            for (double i = M; i > 0 ; i--) {
                ans /= i;
            }

            System.out.println(String.format("%.0f things taken %.0f at a time is %.0f exactly.", N, M, ans));
        }
    }
}

 

用string计算乘法, 超详细注释
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// C = N! / (N-M)!M! 通过约分 == (N*N-1*...*N-M+1) / M!
public class VjudgeJ2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (br.ready()) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 总共的数据
            int M = Integer.parseInt(st.nextToken()); // 挑选的数据
            if(N == 0 && M == 0) break;
            int[] fenzi = new int[N]; //公式的分子
            int[] fenmu = new int[N]; //公式的分母
            int idx = 0; // 存出分子分母数组的索引
            for (int i = N; i > N - M ; i--) {
                fenzi[idx++] = i;
            }
            idx = 0;
            for (int i = M; i > 0 ; i--) {
                fenmu[idx++] = i;
            }

            // 寻找最大公约数
            while (true) {
                boolean isEnd = true; // 不能继续进行约分
                for (int i = 0; i < idx; i++) { // 遍历分子分母
                    for (int j = 0; j < idx; j++) {
                        int gdc = gdc(fenzi[i], fenmu[j]); // 辗转相除寻找最大公约数
                        if(gdc != 1) { // 找到的结果不等于1 可以进行约分
                            fenzi[i] /= gdc;
                            fenmu[j] /= gdc;
                            isEnd = false;
                        }
                    }
                }

                if(isEnd) break; // 当无法约分时跳出循环
            }

            String ans = "1";
            for (int i = 0; i < idx; i++) {
                ans = mult(fenzi[i]+"", ans); // 因为此题目特殊分母最后总是1,所以只需要相乘分子
            }

            // %d是数字 %s是字符串 %.0f是浮点型
            System.out.println(String.format("%d things taken %d at a time is %s exactly.", N, M, ans));
        }
    }

    // 辗转相除法。如果大数不能整除小数,则小数和余数的整除时,小数就是他们的最大公约数
    private static int gdc(int a, int b) {
        if(a > b){
            int r = a % b;
            if(r == 0) return  b;
            return gdc(b, r);
        }

        int r = b % a;
        if(r == 0) return  a;
        return gdc(a, r);
    }

    // 大整数相乘
    private static String mult(String a, String b) {
        // 整数转换数组
        char[] aarr = a.toCharArray();
        char[] barr = b.toCharArray();
        // 分别存储长度整数数组
        char[] bigArr = aarr.length > barr.length ? aarr : barr;
        char[] smallArr = aarr.length > barr.length ? barr : aarr;
        // 模仿真正的乘法。midSum存储,相乘过程中的结果。
        int[][] midSum = new int[smallArr.length][a.length()+b.length()];
        // 模相乘过程中的结果进行叠加就是真正的值。
        int[] sum = new int[a.length()+b.length()];

        // 循环两个整数,从索引最大的开始,因为数字相乘从右到左进行
        for (int i = smallArr.length-1; i >= 0; i--) {
            int row = smallArr.length - 1 - i;
            for (int j = bigArr.length - 1; j >= 0; j--) {
                // 因为是char我们需要转换为int
                int v = Integer.parseInt(smallArr[i]+"") * Integer.parseInt(bigArr[j]+"");
                // 计算当相乘的结果应该放置过程数组的第几位。应该是两者所在位置相加
                // 例如 10 * 10 计算时候 1*1 = 1 但是字符1的位置都是1,所以结果应该向前进两位变成100。
                int col = bigArr.length - j - 1 + smallArr.length - i - 1;

                midSum[row][col] += v; // 需要和本身位置的值进行相加,之前进过来的树需要累加
                int tem = col;

                // 如果结果大于9 需要继续向前进位。while循环进位。 因为有 ..9999这种情况
                while (midSum[row][tem] > 9) {
                    int tv = midSum[row][tem];
                    midSum[row][tem] = tv % 10;
                    midSum[row][tem+1] += tv / 10;
                    tem+=1;
                }
            }
        }

        // 循环累加结果
        for (int i = 0; i < bigArr.length + smallArr.length; i++) {
            for (int j = 0; j < smallArr.length; j++) {
                sum[i] += midSum[j][i]; // 我们需要行循环,列进行累加。所以内层循环用小数组。

                int tem = sum[i];
                int col = i;
                // 累加 如果结果大于9 需要继续向前进位。while循环进位。 因为有 ..9999这种情况
                while (tem > 9) {
                    sum[col] = tem % 10;
                    sum[col+1] += tem / 10;
                    tem = sum[col+1];
                    col+=1;
                }
            }
        }

        // 将数组位数的值转为字符串
        StringBuilder sb = new StringBuilder();
        boolean isT = false;
        for (int i = bigArr.length + smallArr.length-1; i >=0; i--) {
            if(sum[i] != 0) isT = true;
            if(isT) sb.append(sum[i]);
        }

        return sb.toString();
    }
}

 






上一篇:Leetcode 17. 电话号码的字母组合


下一篇:LeetCode 77. Combinations