java - 查找大 n 的组合数 C(n,r)(十进制表示的精度)

Question

这是 CodeSprint3 的问题 https://cs3.interviewstreet.com/challenges/dashboard/#problem/50877a587c389基本上，问题是计算给定 n 和 r 的可能组合的数量 nCr。此外，1 <= n <= 1000000000 和 0 <= r <= n。输出所有答案模 142857。

 Since 6C4=6!/4! 2!
        =6*5/2!     
        =6*5/2*1

我认为在每一步都使用除法可以避免溢出。那是从 n 的值开始(在这种情况下 n 是 6)。减少 n 并将其与先前的值相乘(所以这变成 6*5)对分母进行除法，然后递减( 6*5/2 分母2变为1)重复上述步骤，直到 n 小于 2 个分母的最大值，并且在相同的迭代次数中除数(最小分母将变为 1)

   int count(int n,int r)
   {int maxDen=r>(n-r)?r:n-r;      //larger number in the denominator
    int minDen=n-maxDen;           //the smaller number in denominator
    double num=1;
    for(int j=n;j>maxDen;j--)     
     {num=j*num;              //for C(6,4) example num=6*5 and so on   
    // System.out.println("num "+num +" minDen "+minDen);
       num=num/minDen;         //divide num 6*5 in this case by 2
       minDen--;
      }
   num=num%142875;           //output the result modulo 142875
  return (int) num;
}

但可能由于执行更多除法时精度下降，它给出了错误的值，但它仍然给出了某些值的正确输出。因为它代表正确的 22 17 但不是 24 17。

(22 17) = 26334 //gives Correct value

(24 17)= 60353 //wrong value correct value is 60390

(25,17)=81450 //wrong value correct value is 81576

(16 15)= 16 //gives correct value

(87 28)= 54384 //wrong value correct value is 141525

我尝试将 num 用作 BigDecimal，结果我不得不用 BigDecimal 替换所有内容以执行操作。对于在上面的代码中给出正确结果的输入，输出是相同的。但是对于给出的输入结果错误，程序抛出异常

 Exception in thread "main" **java.lang.ArithmeticException: Non-terminating   decimal  expansion; no exact representable decimal result.**
at java.math.BigDecimal.divide(Unknown Source)
at Combination.NcRcount2.count(NcRcount2.java:16)
at Combination.NcRcount2.main(NcRcount2.java:37)

第 16 行是 num=num.divide(minDen);//代替之前使用的 num/minDen，在这种情况下 num 和 minDen 都是 BigDecimal

即使数字没有精确的十进制表示，考虑到 BigDecimal 的任意精度，如果它不抛出异常，结果中的错误也会被最小化。** 如果 float 或 double 的除法结果没有精确的十进制表示，那么为什么不抛出异常？**

我使用 BigDecimal 和动态规划方法验证了结果

   C(n,r)=C(n-1,r-1)+C(n-1,r)

在我看来，这在所有情况下都能正常工作，但必须有更好的方法

  BigDecimal Comb (int n, int k)
   {  if(k>n-k)
       k=n-k;
       BigDecimal B[][]=new BigDecimal[n+1] [k+1];

    for (int i = 0; i <= n; i++)
   { int min;
     if(i>=k)
      min=k;
    else
     min=i;
   for (int j = 0; j <= min; j++)
    { if (j == 0 || j == i)
           B[i][j] =new BigDecimal(1);
       else{ 
           if(j>i-j)
            B[i][j]=B[i][i-j];
            else
            B[i][j] = B[i - 1][j - 1].add(B[i - 1] [j]);
          }
    }
 }
BigDecimal div=new BigDecimal(142857);
return B[n][k].remainder(div);
}

请建议我一个不使用 BigDecimal 的更好方法

Answer 1

public class Solution {

public static void main(String arg[]) {
    Scanner s = new Scanner(System.in);
    List<BigInteger> ar = new ArrayList<BigInteger>();
    int tot = Integer.parseInt(s.nextLine());
    BigInteger max = BigInteger.ZERO;
    for (int i = 0; i < tot; i++) {
        String str[] = s.nextLine().split(" ");
        Long n1 = Long.parseLong(str[0]);
        Long r1 = Long.parseLong(str[1]);
        Long nr1 = n1 - r1;
        BigInteger n = BigInteger.valueOf(n1);
        BigInteger r = BigInteger.valueOf(r1);
        BigInteger nr = BigInteger.valueOf(nr1);
        ar.add(n);
        ar.add(r);
        ar.add(nr);
        if (n.compareTo(max)==1) {
                max=n;
        }
        if (r.compareTo(max)==1) {
            max=r;
        }
        if (nr.compareTo(max)==1) {
            max=nr;
        }

    }
    HashMap<BigInteger,BigInteger> m=new HashMap<BigInteger,BigInteger>();
    m.put(BigInteger.ZERO, BigInteger.ONE);
    BigInteger fact=BigInteger.ONE;
for(BigInteger i=BigInteger.ONE;i.compareTo(max.add(BigInteger.ONE))==-1;i=i.add(BigInteger.ONE)){
    fact=fact.multiply(i);
    if(ar.contains(i)){
        m.put(i, fact);
    }
}

for(int i=0;i<ar.size();i=i+3){
    BigInteger n=m.get(ar.get(i));
    BigInteger r=m.get(ar.get(i+1));
    BigInteger nr=m.get(ar.get(i+2));
    BigInteger rem=r.multiply(nr);
    BigInteger act=n.divide(rem);
    BigInteger res=act.remainder(BigInteger.valueOf(142857));
    System.out.println(res);
}

}

}

我认为这段代码可能会对您有所帮助。