查找大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 

我認爲可以使用分割在每個step.That避免溢出是 開始用正的值（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（明登）; //替換早期使用的NUM /明登，既NUM和明登都BigDecimal的在這種情況下

即使如果數量沒有一個準確的十進制表示，鑑於BigDecimal的任意精度的結果誤差將有如果它沒有拋出異常，它會被最小化。 ** 如果浮點或雙精度除法運算的結果沒有一個準確的十進制表示，那麼爲什麼不拋出異常？**

我驗證了使用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); 
} 

請建議我一個更好的辦法來做到這一點，而不使用設g BigDecimal

Answer 1

關於BigDecimal代碼異常的問題的一部分對我來說並不清楚，所以我不會對此發表評論。

關於用於計算nCr的乘法和除法序列，wikipedia顯示了一個易於實現的公式。你在問題中的第一部分代碼可能與它相同，可能是下面的python代碼的一部分。它使用64位整數運算計算至61C30; 62C31需要另外一兩個位。

def D(n, k): 
    c, j, k = 1, n, min(k,n-k) 
    for i in range(1,k+1): 
     c, j = c*j/i, j-1 
    return c 

是計算的這個命令的作品，與所有部門爲準確區劃的原因，是因爲nC(j+1) = nCj * (n-j)/(j+1)很容易從nCj = n!/j!(n-j)!和一些代數驗證。也就是說，您可以完全以整數算術計算大n和r的nCr，而不需要任何小數位。

假設K=142857。 請注意，減少中間項模K會導致問題，並且可能不可行。如果分子的模數K減小，則在普通算術中有些分區不會精確。如果K是素數，則可以使用擴展的GCD算法來針對所有數字找到反模數K.但是由於Bézout's lemma和一些模數代數的原因，K = 3 * 9 * 11 * 13 * 37並且反數mod K不會存在於3,11,13或37的倍數的數字上。

Answer 2

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); 
} 

} 

} 

我認爲這段代碼可能會幫助你。

Answer 3

你不應該劃分。在內存中繪製Pascal triangle。這將只需要添加並且將容易地應用模塊化算術。

此外，這將持續時間不會超過分部，因爲您無法避免計算階乘因子。

package tests.StackOverflow; 

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 

public class q13241166 { 

    public static void main(String[] args) throws IOException { 

     BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); 
     String s; 
     String[] ss; 
     int[] n; 
     int[] r; 
     int T; 

     /* 
     System.out.println("Input T:"); 
     s = in.readLine(); 
     T = Integer.parseInt(s); 

     if(T < 1 || T > 100000) { 
      throw new IllegalArgumentException(); 
     } 
     */ 
     T = 9; 

     /* 
     n = new int[T]; 
     r = new int[T]; 

     System.out.println("Input n r pairs:"); 
     for(int i=0; i<T; ++i) { 
      s = in.readLine(); 
      ss = s.split("\\s+"); 

      n[i] = Integer.parseInt(ss[0]); 
      if(n[i] < 1 || n[i] > 1000000000) { 
       throw new IllegalArgumentException(); 
      } 

      r[i] = Integer.parseInt(ss[1]); 
      if(r[i] < 0 || r[i] > n[i]) { 
       throw new IllegalArgumentException(); 
      } 

     } 
     */ 
     n = new int[] {2, 4, 5, 10, 22, 24, 25, 16, 87}; 
     r = new int[] {1, 0, 2, 3, 17, 17, 17, 15, 28}; 


     int modulobase = 142857; 
     int[] answers_old, answers = null; 
     System.out.println("Output"); 
     for(int i=0; i<T; ++i) { 
      for(int nn=0; nn<=n[i]; ++nn) { 
       answers_old = answers; 
       answers = new int[nn+1]; 
       for(int rr=0; rr<=nn; ++rr) { 
        if(rr == 0 || rr == nn) { 
         answers[rr] = 1; 
        } 
        else { 
         answers[rr] = answers_old[rr-1] + answers_old[rr]; 
        } 

        answers[rr] %= modulobase; 
       } 
      } 

      System.out.println(answers[r[i]]); 

     } 



    } 


} 

輸出如下：

Output 
2 
1 
10 
120 
26334 
60390 
81576 
16 
141525 

Answer 4

相當簡單的實現：

public long combinations(int n, int k) { 
    BigInteger factorialN = factorial(n); 
    BigInteger factorialK = factorial(k); 
    BigInteger factorialNMinusK = factorial(n - k); 
    return factorialN.divide(factorialK.multiply(factorialNMinusK)).longValue();; 
} 

private BigInteger factorial(int n) { 
    BigInteger ret = BigInteger.ONE; 
    for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i)); 
    return ret; 
}