計算大數的組合

-2

我試圖計算帕斯卡三角形的第100行中的特定條目是否可以被3整除。我使用公式nCr計算了這個，其中n = 100，r是不同的第100行中的條目。我使用以下代碼來計算組合計算大數的組合

public static double Combination(int n, int m, double comb) 
    { 
     for (int r = -1; ++r < m;) 
      comb = comb * (n - r)/(r + 1); 
     return comb; 
    }

但對於值如100C16我得到含有十進制和e在其大的數字。我在互聯網上搜索發現，實際上有12個數字是不能被3整除的，但是我的程序給了我63個數字，這些數字在第100行不能被3整除，這是錯誤的。可以告訴我它是什麼，做錯了。

來源

2012-03-09 Jay

請與你的同學分享這個鏈接。我厭倦了這個問題。 http://math.stackexchange.com/questions/117978/finding-number-of-entries-not-divisible-by-number-n-in-100th-row-of-pascals-tri – 2012-03-09 21:23:52

可能的重複[Find number的數字不能被x在第100行的Pascal Triangle中整除]（http://stackoverflow.com/questions/9607923/find-number-of-digits-not-divisible-by-x-in-100th-row-of- pascal-triangle） – 2012-03-09 22:16:42

我假設「nCr」是n-choose-r的簡寫，或者從N中選擇r，對不對？

要查看nCr是否可以被三整除，你不需要計算結果，你只需要弄清楚它是否可以被3整除。你必須看看n有多少次！可以被3整除，然後r多少次！可以被3整除和多少次（n-r）！是。

它確實很簡單 - 1！不能被3整除！不是，3！可以一次劃分。 4！和5！也可以一次劃分。 6！可以兩次整除，所以是7！和8 !. 9！可分4次，依此類推。一直到n（或者不用逐步計算就可以計算出公式，這並不是那麼困難），然後檢查。澄清 - 我的數學研究在希伯來語中，所以「n可以被3整除多少次」可能不是英語的恰當表達方式。「n！可以被3整除」我的意思是n!=3^m*k，其中k不能被3整除。

編輯：一個例子。讓我們來看看10c4是否可以被3整除。

讓我們做一個小桌子，說k次！是被3整除（！k個欄只是爲了演示，你實際上並不需要計算divisiblity列時）：

k  k!  Divisibility 
    1  1  0 
    2  2  0 
    3  6  1 
    4  24  1 
    5  120  1 
    6  720  2 
    7 5040  2 
    8 40320  2 
    9 362880  4 
10 3628800  4

10C4是10！ /（6！* 4！）。

10！可分4次（意思是10！= 3^4 *不能被3整除的東西）， 6！可分2次 4！可1分割

所以10！（6！* 4！）可以被3整除。實際上是3 * 70.

來源

2012-03-09 20:13:57 zmbq

讓我們舉一個小例子 - 是20c5可以被3整除嗎？可以用這個解釋嗎？ – Jay 2012-03-09 20:25:42

我會舉一個更小的例子並進行編輯。 – zmbq 2012-03-09 20:26:54

首先您使用的是雙打，我認爲這不是一個好主意。浮點數會在一段時間後出現錯誤。

如果數量不會增長是一個巨大的可以用下面的方法：

public static long nCr (int m, int n) { 
    long tmp = 1; 
    int j = 2; 
    int k = m-n; 
    for(int i = m; i > k; i--) { 
     tmp *= i; 
     while(j <= n && tmp%j == 0) { 
      tmp /= j++; 
     } 
    } 
    while(j <= n) { 
     tmp /= j++; 
    } 
    return tmp; 
}

在這種情況下，然而，這仍然是不夠的。在這種情況下，可以使用BigInteger結構中System.Numerics

public static BigInteger nCr (int m, int n) { 
     BigInteger tmp = 1; 
     int j = 2; 
     int k = m-n; 
     for(int i = m; i > k; i--) { 
      tmp *= i; 
      while(j <= n && tmp%j == 0) { 
       tmp /= j++; 
      } 
     } 
     while(j <= n) { 
      tmp /= j++; 
     } 
     return tmp; 
    }

你可以說，有一個BigInteger一個不需要交錯劃分及其乘法。但是，如果BigInteger非常大，那麼對數據的操作將需要一些時間（因爲數字表示爲一個字節數組）。通過保持較小的值可以避免較長的計算時間。

來源

2012-03-09 20:26:56

計算大數的組合

回答

相關問題