Форум программистов [Powered by Invision Power Board]

Код


public class IntroductoryUnderstanding {

    public static void main(String args[]) {
        System.out.println(countBinomialCoefficient(10000,2000));
    }
    
    public static BigInteger countBinomialCoefficient(int n, int k) {
        
        // in order not to count crazy large numbers
        
        int tmpN = n;
        
        ArrayList<Integer> topFactors = new ArrayList<Integer>();
        topFactors.add(n);
        
        boolean factorLeft;
        int factor;
        
        if (k < Math.ceil(n/2)) {
            factorLeft = true;
            factor = n - k;
        } else {
            factorLeft = false;
            factor = k;
        }
        
        while (tmpN > factor + 1) {
            
            topFactors.add(tmpN - 1);
            tmpN = tmpN - 1;
            
        }
        
        BigInteger topFactor = BigInteger.valueOf(0);
        
        for (int i = 0; i < topFactors.size(); i++) {
            
            if (i == 0) {
                topFactor = BigInteger.valueOf(topFactors.get(0));
            } else {
                topFactor = topFactor.multiply( BigInteger.valueOf(topFactors.get(i)) );
            }
            
        }
        
        if (factorLeft) {
            
            BigInteger kFactorial = factorial(k);
            return topFactor.divide(kFactorial);
            
        } else {
            
            BigInteger knFactorial = factorial(n-k);
            return topFactor.divide(knFactorial);
        }
        
    }
    

    public static BigInteger factorial( int n ) {
        
     if( n <= 1 ) {
            return BigInteger.valueOf(1);
     } else {
            return BigInteger.valueOf(n).multiply( factorial( n - 1 ) );
     }
     
    }
    
}