सी ++ कार्यक्रम बड़े फैक्ट्रोरियल के उद्धरणों की गणना करने के लिए

Question

बड़े फैक्ट्रोरियल की गणना करने के लिए मैं एक सी ++ प्रोग्राम कैसे लिख सकता हूं।

उदाहरण, अगर मैं गणना करना चाहता हूं (100!)/(99!), हम जानते हैं कि उत्तर 100 है, लेकिन यदि मैं संख्यात्मक और denominator के व्यक्तिगत रूप से तथ्यों की गणना करता हूं, तो दोनों संख्याएं बड़े पैमाने पर बड़ी हैं।

Answer 1

एक प्रकार की कटार के जवाब पर विस्तार (जो imo सही एक है):

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

यह कोशिश करते हैं, यह वास्तव में आप क्या चाहते हैं, भले ही यह एक छोटे से पागल लग रहा है अगर आप इसे से परिचित नहीं हैं करता है। एक बड़ी पुस्तकालय का उपयोग जंगली रूप से अक्षम होने जा रहा है। गामा के लॉग का विस्तार लेना बहुत तेज़ है। यह तुरंत चलाता है।

100/99 तक गुणा करने की आवश्यकता यह है कि गामा एन -1 के बराबर है! एन नहीं!। तो हाँ, आप बस exp (lgamma (101) -lgamma (100)) कर सकते हैं इसके बजाय। इसके अलावा, गामा को केवल पूर्णांक से अधिक के लिए परिभाषित किया गया है।

Answer 2

यहाँ कैसे ऐसा करने के लिए की एक उदाहरण है:

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

दृष्टिकोण वे ले अंकों के एक चरित्र सरणी में बड़ा # से स्टोर करने के लिए है। Calculate the factorial of an arbitrarily large number, showing all the digits

Answer 3

आप गामा फ़ंक्शन के बजाय का उपयोग कर सकते, the Wikipedia page जो भी कोड की ओर संकेत करती देखें:

इसके अलावा इस तो सवाल यह देखते हैं।

Answer 4

आप gmp जैसी बड़ी पूर्णांक लाइब्रेरी का उपयोग कर सकते हैं जो मनमाने ढंग से बड़े पूर्णांक को संभाल सकता है।

Answer 5

एक्स को हल करने के लिए!/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 से बड़ा है) का मतलब है गुणा का उपयोग करने से पहले आप जो भी कर सकते हैं उसे पार कर सकते हैं।

यदि mn से कम है तो हमें पहले तत्वों को स्वैप करना होगा, फिर फैक्टरियल की गणना करना होगा और फिर 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 को विभाजित करने के लिए, जिसमें प्रत्येक 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 पसंद है क्योंकि यह एक सभ्य सी ++ इंटरफेस प्रदान करता है, और आसानी से उपलब्ध है।

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

g++ -Wall -Wextra -o test test.cc -lgmpxx -lgmp

Answer 9

अपनी टिप्पणी की आवाज़ तक साथ लिनक्स पर संकलित, आप भी 100 की तरह भाव गणना करना चाहते हैं!/(96! * 4!)।

अपने आप को छोड़कर "9 6 * ... * 100)/4 के साथ छोड़कर" 96 को रद्द कर दिया "है, तो आप अंकगणितीय को शीर्ष से" शीर्ष से "जितनी संभव हो सके छोटी सीमाओं के भीतर रख सकते हैं तुम जाओ। तो, इस मामले में:

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 

आप निश्चित रूप से उसी नस में उससे अधिक स्पष्ट हो सकते हैं।

यह केवल अपरिहार्य है, हालांकि: अंत में आप अपने निश्चित आकार के प्रकार की सीमा तक पहुंच जाते हैं। फैक्टोरियल इतनी जल्दी विस्फोट करते हैं कि भारी कर्तव्य के उपयोग के लिए आपको कई परिशुद्धता की आवश्यकता होगी।