计算任意大数的阶乘，显示所有数字

Question

最近在一次采访中，我被要求描述一种计算任意大数的阶乘的方法；我们获得答案的所有数字的方法。

我搜索了各个地方并在一些论坛上询问。但我想知道是否有任何方法可以在不使用 GMP 等库的情况下完成此任务。

谢谢。

Answer 1

GNU 多精度库是一个很好的库！但既然你说不允许使用外部库，我相信它可能的唯一方法就是采用一个 int 数组，然后将数字相乘，就像用笔在纸上做的那样！

这是我不久前写的代码..

#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”只是一个整数数组，而阶乘是一个简单的函数，它将给定的数字乘以“大数”。

希望这能解决您的疑问..

Answer 2

接受的答案很好，但这是 C++；我们可以做得更好。让我们从我们自己的 Bignum 类开始，它具有完全无限的位数。

为了获得最高效率，我们将使用纯二进制数，将每个数组元素包装为我们可以有效处理的尽可能多的位。更简单的方法是在每个元素中存储一个十进制数字。在这里，我采取了折衷方案，在每个 uint32_t 元素中存储 9 位十进制数字。

数据以小端存储，因为当我们需要更高阶的元素时，在末尾扩展向量要容易得多。

一旦我们有了这个类，阶乘函数本身就很简单了。

#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 3

Srivatsan Iyer 提出了一个很好的解决方案，我的建议是：

1. 通过使用 unsigned char 数组而不是使用 int 数组来存储数字，仍然可以提高内存效率。
   与 int 数组相比，它只需要 25% 的内存需求。

2. 为了获得最佳的内存优化，我们也可以使用单个字节来表示 2 位数字。
   因为只要 4 位就足以表示从 0 到 9 的任何数字。
   因此，我们可以使用按位运算将两个数字打包在一个字节中。
   与int数组相比，它会占用12.5%的内存。

Answer 4

BigInteger 类可以解决您的问题，上面的 C 实现可以让您了解如何实现 BigInt，只不过代码针对速度进行了优化，并且只针对计算阶乘进行了定制。

Answer 5

好吧，您必须使用数组编写自己的数学例程。加法很容易，乘法有点困难，但仍然是可能的。

编辑：想发布一个示例，但 Srivatsan Iyer 的示例就很好。

Answer 6

我有一个计算阶乘的解决方案，它至少适用于 n<=15000。 10000的阶乘可以在1秒内计算出来，计算阶乘只需不到2秒。 （当然，您的问题没有说明时间限制，这些时间完全取决于机器）。无论如何，这个概念非常简单。我使用字符数组。数组的第一个字符是“1”。 LSB 从从 0 开始的索引存储。变量（根据我的程序是 m）跟踪阶乘长度。 m 的最终值是阶乘中的位数，char 数组的第 (m-1) 个元素是阶乘的 MSB。
当循环迭代时，字符将添加到数组的右侧。变量“c”跟踪进位。

使用数组的缺点是留下大量未使用的字节。超过某个点，您就无法为数组保留空间。此外，数组往往会变慢。

你可以在ideone上查看我的程序： http://ideone.com/K410n7

我相信我的解决方案仍然可以优化。请建议如何。

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 7

#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 8

这实际上很容易。这里有两种方法。一种是精确的，一种是近似的。对于精确的数字，任何超过 10,000 的数字都将需要数秒的时间来计算。近似它需要几微秒，直到达到数百万秒。如果有人感兴趣的话，这是斯特林的近似。

10,000,000 的阶乘约为 1.2024234127436e+65657059 这需要 5.9 秒 找到确切的金额需要 34 天。

<?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 9

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

Answer 10

代码如下所示：

#include<bits/stdc++.h>
using namespace std;
#define MAX 5000

void factorial(int n)
{
    int carry , res_size = 1, res[MAX];
    res[0] = 1;

    for(int x=2; x<=n; x++)
    {
        carry = 0;
        for(int i=0; i<res_size; i++)
        {
          int prod = res[i]*x + carry;
          res[i] = prod % 10;
          carry  = prod/10;
        }
        while (carry)
        {
          res[res_size++] = carry%10;
          carry = carry/10;
        }
     }
     for(int i=res_size-1; i >= 0; i--) 
     {
         cout<<res[i];
     }
}
int main()
{
      int n;
      cin>>n;
      factorial(n);
      cout<<endl;
      return 0;
}

Answer 11

既然每个人都投票给斯里瓦特桑，我只是对这个问题有疑问。您需要存储所有数字吗？如果是，那么 Srivatsan 的解决方案就很好。如果不是，为什么在计算阶乘时不只显示数字呢？我没有正确格式化输出，但这可以达到目的。

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

更新
对于所有投反对票的人，尽管这是一篇 5 年前的帖子，以及 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.

我认为这就是所要求的。