Tính giai thừa của một số lớn tùy ý, hiển thị tất cả các số

Question

Gần đây tôi đã được hỏi, trong một cuộc phỏng vấn, để mô tả một phương pháp tính giai thừa của bất kỳ số lượng lớn tùy ý; một phương pháp trong đó chúng tôi có được tất cả các số các số của câu trả lời.

Tôi đã tìm kiếm các địa điểm khác nhau và được hỏi trong một số diễn đàn. Nhưng tôi muốn biết nếu có bất kỳ cách nào để thực hiện điều này mà không sử dụng các thư viện như GMP.

Cảm ơn bạn.

Answer 1

Thư viện đa năng GNU là thư viện tốt nhất! Nhưng kể từ khi bạn nói việc sử dụng các thư viện bên ngoài không được phép, chỉ có cách tôi tin rằng nó có thể là bằng cách lấy một mảng int và sau đó nhân số như bạn làm với bút trên giấy!

Đây là mã tôi đã viết một số thời gian trở lại ..

#include<iostream> 
#include<cstring> 

int max = 5000; 

void display(int arr[]){ 
    int ctr = 0; 
    for (int i=0; i<max; i++){ 
     if (!ctr && arr[i])   ctr = 1; 
     if(ctr) 
      std::cout<<arr[i]; 
    } 
} 


void factorial(int arr[], int n){ 
    if (!n) return; 
    int carry = 0; 
    for (int i=max-1; i>=0; --i){ 
     arr[i] = (arr[i] * n) + carry; 
     carry = arr[i]/10; 
     arr[i] %= 10; 
    } 
    factorial(arr,n-1); 
} 

int main(){ 
    int *arr = new int[max]; 
    std::memset(arr,0,max*sizeof(int)); 
    arr[max-1] = 1; 
    int num; 
    std::cout<<"Enter the number: "; 
    std::cin>>num; 
    std::cout<<"factorial of "<<num<<"is :\n"; 
    factorial(arr,num); 
    display(arr); 
    delete[] arr; 
    return 0; 
} 

'arr' chỉ là một mảng số nguyên, và thừa là một chức năng đơn giản mà nhân với số lượng nhất định để các 'số lượng lớn'.

Hy vọng điều này giải quyết truy vấn của bạn ..

Answer 2

Vâng, bạn phải viết các quy trình toán học của riêng mình bằng cách sử dụng mảng. Điều đó rất dễ để bổ sung, phép nhân thì khó hơn một chút, nhưng vẫn có thể.

EDIT: Muốn đăng một ví dụ, nhưng ví dụ của Srivatsan Iyer là tốt.

Answer 3

Một BigInteger lớp sẽ giải quyết vấn đề của bạn, và việc thực hiện C trên cung cấp cho bạn một ý tưởng về cách thức một bigint sẽ được thực hiện, ngoại trừ mã được tối ưu hóa cho tốc độ và phù hợp để tính toán giai thừa.

Answer 4

đẹp giải pháp bởi Srivatsan Iyer và đề nghị của tôi là:

1. Nó vẫn có thể được thực hiện bộ nhớ hiệu quả hơn bằng cách sử dụng mảng char unsigned hơn là sử dụng int mảng để lưu trữ chữ số. Nó sẽ chỉ mất 25% bộ nhớ cần đến của mảng int.

2. Để tối ưu hóa bộ nhớ tốt nhất, chúng tôi cũng có thể sử dụng một byte để đại diện cho 2 chữ số. Vì chỉ có 4 bit đủ để đại diện cho bất kỳ chữ số nào từ 0 đến 9. Vì vậy, chúng tôi có thể đóng gói hai chữ số trong một byte bằng cách sử dụng các thao tác bitwise. Nó sẽ chiếm 12,5% bộ nhớ cần cho mảng int.

Answer 5

Vì mọi người đã bỏ phiếu cho Srivatsan, tôi chỉ nghi ngờ về vấn đề này. Bạn có cần lưu trữ tất cả các chữ số không? Nếu có, thì giải pháp của Srivatsan là tốt. Nếu không, tại sao không chỉ hiển thị các con số, khi bạn tính toán giai thừa? Tôi không định dạng đầu ra đúng cách, nhưng điều này có thể phục vụ mục đích.

int factorial(int num) 
{ 
    if (num <= 0) 
     return 1; 
    else 
    { 
     std::cout << num << std::endl; 
     return num * factorial(num - 1); 
    } 
} 

CẬP NHẬT Đối với tất cả các downvoters, mặc dù bài này 5 tuổi, và đầu ra cho factorial(3);

3 
2 
1 
6 // this is the result of the factorial and the digits above are the ones all the digits in the calculation. 

Tôi nghĩ đây là những gì hỏi.

Answer 6

Câu trả lời được chấp nhận là tốt, nhưng đây là C++; chúng ta có thể làm tốt hơn. Hãy bắt đầu lớp Bignum của riêng chúng tôi, với số chữ số hoàn toàn không bị chặn.

Để đạt hiệu quả cao nhất, chúng tôi sẽ làm việc với các số nhị phân thuần túy, đóng gói từng phần tử mảng với nhiều bit khi chúng ta có thể xử lý hiệu quả. Cách tiếp cận đơn giản hơn là lưu trữ một chữ số thập phân duy nhất trong mỗi phần tử. Ở đây tôi đã đi cho một sự thỏa hiệp, lưu trữ 9 chữ số thập phân trong mỗi yếu tố uint32_t.

Dữ liệu được lưu trữ ít người dùng, vì việc mở rộng vector ở cuối cùng dễ dàng hơn nhiều khi chúng tôi cần các yếu tố đặt hàng cao hơn.

Khi chúng tôi có lớp này, hàm giai thừa là tính đơn giản.

#include <assert.h> 
#include <iomanip> 
#include <iostream> 
#include <stdint.h> 
#include <vector> 

class Bignum 
{ 
public: 
    Bignum(int value) 
    { 
     assert(value >= 0 && value <= 999999999); 
     parts.push_back(value); 
    } 

    Bignum& operator*=(int rhs) 
    { 
     assert(rhs >= 0 && rhs <= 999999999); 
     uint32_t carry = 0; 
     for (size_t i = 0; i < parts.size(); i++) 
     { 
      uint64_t product = (uint64_t)parts[i] * (uint64_t)rhs + carry; 
      parts[i] = (uint32_t)(product % 1000000000LL); 
      carry = (uint32_t)(product/1000000000LL); 
     } 
     if (carry != 0) 
      parts.push_back(carry); 
     return *this; 
    } 

    friend std::ostream & operator<<(std::ostream& stream, const Bignum& num); 

private: 
    std::vector<uint32_t> parts; 
}; 

inline std::ostream& operator<<(std::ostream& stream, const Bignum& num) 
{ 
    char oldfill = stream.fill('0'); 
    for (std::vector<uint32_t>::const_reverse_iterator it = num.parts.rbegin(); it != num.parts.rend(); it++) 
     stream << *it << std::setw(9); 
    stream.fill(oldfill); 
    stream.width(0); 
    return stream; 
} 

Bignum factorial(int n) 
{ 
    Bignum fac = 1; 
    for (int i = 2; i <= n; i++) 
     fac *= i; 
    return fac; 
} 

int main(int argc, char* argv[]) 
{ 
    for (int n = 0; n <= 52; n++) 
     std::cout << factorial(n) << std::endl; 
    return 0; 
} 

Answer 7

Điều đó thực sự khá dễ dàng. Dưới đây là hai cách. Một là chính xác và một là một xấp xỉ. Đối với các số liệu chính xác, bất kỳ số nào trên 10.000 sẽ mất nhiều giây để tính toán. Ước tính nó sẽ mất một phần nghìn giây, cho đến khi bạn nhận được hàng triệu. Đó là xấp xỉ Stirling nếu có ai quan tâm.

Giai thừa 10.000.000 là aprox 1.2024234127436e + 65657059 Điều này mất 5,9 giây Tìm số tiền chính xác sẽ mất 34 ngày.

<?php 
$test= 3579; 

echo 'Factorial of '.$test.'<br><br>'; 

$tm= microtime(true); 

echo 'Exact '.($f= factorialexact($test)).' e+'.(strlen($f)-1).' missing decimal place after first digit<br>'; 

echo (microtime(true) - $tm). ' seconds<br><br>'; 

$tm= microtime(true); 

echo 'Aprox '.factorialapprox($test).'<br>'; 

echo (microtime(true) - $tm). ' seconds<br><br>'; 


function factorialexact($n){ 
    $f= '1'; 
    for ($i=$n; $i>1; $i--){ 
     $f= JL_bcmul($f, (''.$i)); 
    } 
    return $f; 
} 

function factorialapprox($n){ 
    // Stirling's factorial approximation 
    // aprox factorial n = sqrt(2 * pi * n) * n^n/e^n 
    // store in t the easy part, calc the first term easily 
    $t= sqrt(2 * 3.14159265358979 * $n); 
    // things get tough from here because for large n 
    // n^n can blow away floating point pachages 
    // declare exponent of the number 
    $e= 0; 
    // the remaining terms are n^n/e^n 
    // both n and e (natural log) are raised to the same power 
    // that is n, just negative of each other 
    for ($i=0; $i<$n; $i++){ 
     // loop to 
     // mulitply by n and divide by e for each iteration 
     $t= $t * $n/2.71828182845904; 
     // exponents are going to get away from us 
     // so reduce or increase t 
     while ($t>1000){ 
      $t= $t/1000; 
      $e= $e+3; 
     } 
     while ($t<0.001){ 
      $t= $t*1000; 
      $e= $e-3; 
     } 
    } 
    // garentee the base number is between 1 and 10 
    while ($t>=10){ 
     $t= $t/10; 
     $e= $e+1; 
    } 
    while ($t<1){ 
     $t= $t*10; 
     $e= $e-1; 
    } 
    // return at a floating string. 
    // do not use parseFloat() or floatval() 
    // $v= explode('e', $result); $floatvalue= $v[0] * pow(10, $v[1]); 
    // won't work either. $v[1] is way too large 
    // the exponent can easily be in the tens of thousands 
    $p= '-'; 
    if ($e>=0){ $p= '+'; } 
    return $t.'e'.$p.$e; 
}  

function JL_bcmul($a, $b){ 
    if (function_exists('bcmul')){ 
     return bcmul((''.$a), (''.$b)); 
    } 
    $s= array(); 
    for ($i=0; $i < count($a) + count($b); $i++){ $s[$i]= '0'; } 
    $t= 0; 
    for ($i=0; $i < strlen($b); $i++){ 
     for ($j=0; $j < strlen($a); $j++){ 
      $t= $s[$i+$j] + intval($a[strlen($a) - $j - 1]) * intval($b[ strlen($b) - $i - 1]); 
      $s[$i+$j]= $t % 10; 
      $s[$i+$j+1]= $s[$i+$j+1] + floor($t/10); 
     } 
    } 
    $s= array_reverse($s); 
    return trim(trim((implode('', $s).'_'), '0'), '_'); 
} 

Answer 8

Tôi có giải pháp tính giai thừa, hoạt động tốt cho ít nhất n < = 15000. Hệ số 10000 có thể được tính dưới 1 giây và để tính giai thừa mất ít hơn 2 giây. (Tất nhiên câu hỏi của bạn không nói gì về thời gian hạn chế và những thời gian này hoàn toàn phụ thuộc vào máy). Dù sao, khái niệm này khá đơn giản. Tôi sử dụng một mảng char. Ký tự đầu tiên của mảng là '1'. Các LSB được lưu trữ từ chỉ mục bắt đầu bằng 0. Một biến (m theo chương trình của tôi) theo dõi độ dài giai thừa. Giá trị cuối cùng của m là số chữ số trong giai thừa và phần tử thứ m (m-1) của mảng char là MSB của giai thừa. Khi vòng lặp lặp lại, các ký tự được thêm vào ở bên phải của mảng. Một biến 'c' theo dõi việc thực hiện.

Những hạn chế của việc sử dụng mảng được để lại trên nhiều byte không sử dụng. Và ngoài một điểm nhất định, bạn không thể dự trữ không gian cho một mảng. Ngoài ra, mảng có xu hướng chậm.

Bạn có thể kiểm tra chương trình của tôi trên ideone: http://ideone.com/K410n7

Tôi tin rằng giải pháp của tôi vẫn có thể được tối ưu hóa. Xin đề nghị làm thế nào.

include<stdio.h> 

char res[200000]; 

inline int fact(int n) 
{ 

    int i,j; 

    register int m,c; 

    m=1; 

    res[0]='1'; 

    for(i=2;i<=n;i++) 
    { 

     c=0; 

     for(j=0; j< m; j++){ 

      c =((res[j]-48)*i)+c; 

      res[j]=(c%10)+48; 

      c=c/10; 

     } 
     while(c>0){ 
      res[m]=(c%10)+48; 

      c=c/10; 

      m++; 

     } 

    } 

    return m; 

} 

int main() { 


    int n,i,d; 

    scanf("%d",&n); 


    d=fact(n); 

    for(i=d-1;i>=0;i--) 

     printf("%c",res[i]); 


    return 0; 
} 

Answer 9

#include <iostream> 
using namespace std; 
int main() 
{ 
    int i,n,p=1; 
    cout<<"Enter a number: "; 
    cin>>n; 
    cout<<endl; 

    for (i=1;i<=n; i++) 
    { 
     cout<<i<<" X "; 
     p=p*i; 
    } 
    cout<<endl<<endl<<p<<" factorial of "<<n; 

    return 0; 
} 

Answer 10

#include<stdio.h> 
#include<string.h> 
char f[10000]; 
char factorial[1010][10000]; 
void multiply(int k){ 
    int ci,sum,i; 
    int len = strlen(f); 
    ci=0; 
    i=0; 
    while(i<len){ 
     sum=ci+(f[i] - '0') * k; 
     f[i] = (sum % 10) + '0'; 
     i++; 
     ci = sum/10; 
    } 
    while(ci>0){ 
     f[i++] = (ci%10) + '0'; 
     ci/=10; 
    } 
    f[i]='\0'; 
    for(int j=0;j<i;j++)factorial[k][j]=f[j]; 
    factorial[k][i]='\0'; 
} 
void fac(){ 
    int k; 
    strcpy(f,"1"); 
    for(k=2;k<=1000;k++)multiply(k); 
} 
void print(int n){ 
    int i; 
    int len = strlen(factorial[n]); 
    printf("%d!\n",n); 
    for(i=len-1;i>=0;i--){ 
     printf("%c",factorial[n][i]); 
    } 
    printf("\n"); 
} 
int main() 
{ 
    int n; 
    factorial[0][0]='1'; 
    factorial[1][0]='1'; 
    fac(); 
    while(scanf("%d",&n)==1){ 
     print(n); 
    } 
    return 0; 
}