用於計算大因數的商的C++程序

Question

如何編寫一個C++程序來計算大的因子。例如，如果我想計算（100！）/（99！），我們知道答案是100，但是如果我分別計算分子和分母的階乘因子，那麼這兩個數字都是巨大的。

Answer 1

對德克的回答擴張（這海事組織是正確的）：

 
#include "math.h" 
#include "stdio.h" 
int main(){ 
    printf("%lf\n", (100.0/99.0) * exp(lgamma(100)-lgamma(99))); 
} 

嘗試它，它確實你想要什麼，即使它看起來有點瘋狂，如果你不熟悉它。使用bigint庫會非常低效。採取gammas日誌的exps是超級快速的。這會立即運行。

你需要乘以100/99的原因是伽瑪相當於n-1！不是！所以，你可以用exp（lgamma（101）-lgamma（100））來代替。而且，伽瑪定義的不僅僅是整數。

Answer 2

下面是如何做到這一點的例子：

http://www.daniweb.com/code/snippet216490.html

他們採取的辦法是大＃分別存儲爲一個數字字符數組。

也看到這個問題的SO：Calculate the factorial of an arbitrarily large number, showing all the digits

Answer 3

可以使用伽瑪功能，而不是見the Wikipedia page也指針代碼。

Answer 4

您可以使用一個大整數庫，如gmp，它可以處理任意大的整數。

Answer 5

解決x！/ y！對於X> Y：

int product = 1; 
for(int i=0; i < x - y; i ++) 
{ 
    product *= x-i; 
} 

若y> x開關變量，並採取解決方案的倒數。

Answer 6

可以在這裏進行的唯一優化（考慮到在m!/n!m大於n）意味着在使用乘法之前將所有可以完成的操作都劃掉。

如果m小於n我們將不得不首先交換元素，然後計算階乘，然後使類似於1/result。請注意，在這種情況下的結果是雙重的，你應該把它作爲雙重處理。

這是代碼。

if (m == n) return 1; 

    // If 'm' is less than 'n' we would have 
    // to calculate the denominator first and then 
    // make one division operation 
    bool need_swap = (m < n); 
    if (need_swap) std::swap(m, n); 

    // @note You could also use some BIG integer implementation, 
    // if your factorial would still be big after crossing some values 

    // Store the result here 
    int result = 1; 
    for (int i = m; i > n; --i) { 
     result *= i; 
    } 

    // Here comes the division if needed 
    // After that, we swap the elements back 
    if (need_swap) { 
     // Note the double here 
     // If m is always > n then these lines are not needed 
     double fractional_result = (double)1/result; 
     std::swap(m, n); 
    } 

另外提一下（如果你需要一些大INT實施，並希望自己做） - 這是不是很難實現的對待你的int用作塊序列的最佳方法，最好的是把你的int分成幾個系列，每個系列包含4個數字。

例如：1234 | 4567 | 2323 | 2345 | ...。那麼你將不得不實施你需要的每一個基本的操作（總之，多重，也許戰俘，部門實際上是一個艱難的）。

Answer 7

我問過類似的問題，並得到了一些指點一下庫：

How can I calculate a factorial in C# using a library call?

這取決於你是否並不需要所有的數字，或者只是一些接近。如果你只是想要一些東西，Stirling's Approximation是一個很好的開始。

Answer 8

當然這個特定的表達式應該被優化，但是對於標題問題，我喜歡GMP，因爲它提供了一個體面的C++接口，並且很容易獲得。

#include <iostream> 
#include <gmpxx.h> 

mpz_class fact(unsigned int n) 
{ 
     mpz_class result(n); 
     while(n --> 1) result *= n; 
     return result; 
} 

int main() 
{ 
     mpz_class result = fact(100)/fact(99); 
     std::cout << result.get_str(10) << std::endl; 
} 

編譯的Linux上g++ -Wall -Wextra -o test test.cc -lgmpxx -lgmp

Answer 9

通過您的意見的聲音，你也需要計算像100的表達！/（96！* 4！）。

在「取消96」後，留下（97 * ... * 100）/ 4！自己，然後通過儘可能少的數字「從頂部」保持算法在更小的範圍內你走。所以，在這種情況下：

i = 96 
j = 4 
result = i 
while (i <= 100) or (j > 1) 
    if (j > 1) and (result % j == 0) 
     result /= j 
     --j 
    else 
     result *= i 
     ++i 

你當然可以比同樣的方式更聰明。

這只是推遲了不可避免的，但是：最終你達到了你的固定尺寸類型的限制。因子分解速度如此之快以致於重載使用，您將需要多個精度。