Problem 369 Combinations，組合 C(n, m) 的計算

這題所要完成的C語言程式是計算組合，C(n, m)是指計算在n個物品中取出m個的方法數。如果寫成C(m, n)就表示m中取n的方法數。這題acm用的變數是以前者來表示。
題目中的數字範圍是 5 <= m <= n <= 100，組合的公式為
如果先算完N!，那結果就很難看了，因為答案將高達10的152次方，完成這麼大的數字乘法，就是一個挑戰。其實，這個題目可以不用這麼做。如果先化簡，那C語言的處理就會單純許多。例如，C(10, 7)或C(10, 3)是相等的，第一步的化簡可以變成(10*9*8)/(3*2*1)，第二步簡化時，分子分母再進一步相消，式子的計算就更簡單了，加上其題目都先告訴你答案會是小於32位元的整數，所以不用擔心數字太大。
首先，我們先進行第一步的化簡，算出分子項目數(與分母數相同)，並設定階乘的項目，C語言程式碼如下，其中Na是分子項陣列，Ma是分母項陣列：

aSize = (n-m > m) ? m : n-m;
for (i=0;i<aSize;i++)
{
   Na[i] = n-i;
   Ma[i] = i+1;
}

接者進行第二步的相消簡化，allOne為化簡為1的分母項數，nofactor為不能化簡的分母項數：

while (allOne<aSize && nofactor<aSize)
{
    nofactor = 0;
    for (i=0;i<aSize;i++)
    {
        j=1;
        allOne = 1;
        while (j<aSize)
        {
            if (Ma[j]==1)
                allOne++;
            else if (Na[i]%Ma[j]==0)
            {
                Na[i] /= Ma[j];
                Ma[j] = 1;
            }
            else
                nofactor++;
            j++;
        }
    }
}

最後再進行實際的乘除，即可算出成果。C語言程式碼可以輕鬆寫出。
p369題目連結
回ACM題庫目錄
回首頁