計算可能的組合數 - C＃

Question

我想要計算可能的組合數，所以我在這裏使用了一些數學（準確的階乘因子）。例如，如果我有50個號碼，並且我想將它們組織爲5個組，則可以製作多少個組（組合）。我使用的是這個公式：allNumbers!/(allNumbers - PerGroup)!，但是對於這個特定的例子它出現了一個錯誤。它說，除以零是被禁止的。我怎樣才能管理這個工作？ 這是我的代碼：

int b = 1; 
int n = 1; 

if (allNumbers - PerGroup == 0) 
{ 
     return 1; 
} 
else if (allNumbers - PerGroup == 1) 
{ 
     return allNumbers; 
} 
else 
{ 
     for (int i = 1; i <= allNumbers; i++)  
     { 
      b *= i; 
     } 

     for (int i = 1; i <= allNumbers - PerGroup; i++) 
     { 
      n *= i; 
     } 

     if (Enumerable.Range(1,int.MaxValue).Contains(b/n)) //line with ERROR! 
     { 
      return b/n; 
     } 
     else 
     { 
      return int.MaxValue; 
     } 
} 

Answer 1

因爲allNumbers!總是包含(allNumbers - PerGroup)!，你爲什麼不從開始排除。

int b = 1; 

if (allNumbers - PerGroup == 0) 
{ 
     return 1; 
} 
else if (allNumbers - PerGroup == 1) 
{ 
     return allNumbers; 
} 
else 
{ 
     for (int i = (allNumbers - PerGroup + 1); i <= allNumbers; i++)  
     { 
      b *= i; 
     } 

     return b; 
} 

Answer 2

Enumerable.Range(1,int.MaxValue).Contains(b/n)檢查不檢查值是有效的，因爲B/N已經計算並通過此時INT存儲。

由於變量n溢出並且變爲零，所以您得到除法零。在下面的代碼中，您可以看到溢出發生的方式。

using System; 

public class Test 
{ 
    public static void Main() 
    { 
     int n = 1; 
     for (int i = 1; i <= 50; i++) { 
      n *= i; 
      Console.WriteLine("i = {0}, n = {1}", i, n); 
     } 
    } 
} 

輸出：

i = 1, n = 1 
i = 2, n = 2 
i = 3, n = 6 
i = 4, n = 24 
i = 5, n = 120 
i = 6, n = 720 
i = 7, n = 5040 
i = 8, n = 40320 
i = 9, n = 362880 
i = 10, n = 3628800 
i = 11, n = 39916800 
i = 12, n = 479001600 
i = 13, n = 1932053504 
i = 14, n = 1278945280 
i = 15, n = 2004310016 
i = 16, n = 2004189184 
i = 17, n = -288522240 
i = 18, n = -898433024 
i = 19, n = 109641728 
i = 20, n = -2102132736 
i = 21, n = -1195114496 
i = 22, n = -522715136 
i = 23, n = 862453760 
i = 24, n = -775946240 
i = 25, n = 2076180480 
i = 26, n = -1853882368 
i = 27, n = 1484783616 
i = 28, n = -1375731712 
i = 29, n = -1241513984 
i = 30, n = 1409286144 
i = 31, n = 738197504 
i = 32, n = -2147483648 
i = 33, n = -2147483648 
i = 34, n = 0 
i = 35, n = 0 
i = 36, n = 0 
i = 37, n = 0 
i = 38, n = 0 
i = 39, n = 0 
i = 40, n = 0 
i = 41, n = 0 
i = 42, n = 0 
i = 43, n = 0 
i = 44, n = 0 
i = 45, n = 0 
i = 46, n = 0 
i = 47, n = 0 
i = 48, n = 0 
i = 49, n = 0 
i = 50, n = 0 

Answer 3

我猜的錯誤是OutOfMemoryException異常，因爲你創造了巨大的不必要integers量。 （Enumerable.Range(1,int.MaxValue)）請注意，每個int需要從您的內存4字節。

林不知道你在那裏試圖做什麼，但你可以使用double類型，所以如果數量變得非常大，它只會給你PositiveInfinity。

或者您可以使用checked來控制try和catch的整數溢出。

另一種方法是預先計算整數溢出發生時的數量。例如14的階乘會溢出int，22的階乘會溢出long。

另外你不必爲循環寫兩次。你可以使用方法來達到這個目的。您不需要檢查allNumbers - PerGroup == 0以防止零分割。這不會發生，因爲0的階乘是1，當輸入爲0時，我們的階乘實現返回1的性質！ （因爲for循環在這種情況下，從來沒有進行迭代，並從1計數器開始）

private static int Cominations(int allNumbers, int perGroup) 
{ 
    if(allNumbers > 13) 
    { 
     Console.WriteLine("Too big number!"); 
     return -1; 
    } 

    return Factorial(allNumbers)/Factorial(allNumbers - perGroup); 
} 

private static int Factorial(int number) 
{ 
    int n = 1; 

    for (int i = 1; i < number; i++) 
    { 
     n *= i; 
    } 

    return n; // returns 1 when number is 0 
} 

如果要計算更大的數字階乘使用來自System.Numberics命名空間BigInteger類型。

using System.Numerics; 

//... 

private static BigInteger Factorial(int number) 
{ 
    BigInteger n = 1; 

    for (int i = 1; i < number; i++) 
    { 
     n *= i; 
    } 

    return n; 
}