计算任意大数的阶乘,显示所有位数

23

最近在一次面试中,我被要求描述计算任意大数阶乘的方法;并且需要获得所有位数的答案。

我在各个地方进行了搜索,并在一些论坛上提出了问题。但我想知道是否有一种不使用像GMP这样的库来完成这个任务的方法。

谢谢。

11个回答

33

GNU多精度库是一个很好的库!但是既然你说不允许使用外部库,我认为唯一的方法是像在纸上用笔一样取一个整数数组,然后对数字进行乘法运算!

这是我以前写的代码...

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

希望这解决了你的问题。


2
main函数中那一行应该是factorial(arr,num),否则你将始终得到10!的输出。让我来修复它 :) - schnaader
非常感谢您的及时回复!这正是我所需要的! :) - undefined
1
@Prasoon,"better" 是什么意思? - Drew Dormann
1
@Prasoon:这个解决方案并不是为了效率而设计的,所以为什么要费力地将递归转换为迭代呢? - rafak
我为另一个发帖者将其移植到了C#。请参见https://dev59.com/qVnUa4cB1Zd3GeqPeNOY#6906939 - Eric J.
显示剩余6条评论

9
接受的答案不错,但这是C ++,我们可以做得更好。让我们开始创建自己的Bignum类,它具有完全无限数量的数字。 为了最高效率,我们将使用纯二进制数字,在每个数组元素中尽可能有效地处理尽可能多的位。更简单的方法是在每个元素中存储一个十进制数字。在这里,我选择了一个折衷方案,将9个十进制数字存储在每个uint32_t元素中。 数据以小端方式存储,因为当我们需要更高阶元素时,在末尾扩展vector要容易得多。 有了这个类之后,求阶乘函数就非常简单了。
#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;
}

6

这是Srivatsan Iyer提出的一个好的解决方案,我的建议是:

  1. 可以使用无符号字符数组而不是使用int数组来存储数字,以使其更加节省内存。 只需要int数组所需内存的25%。

  2. 为了获得最佳的内存优化,我们还可以使用单个字节来表示2个数字。 因为只需要4位就足以表示0到9之间的任何数字。 所以我们可以使用位运算将两个数字压缩为单个字节。 这将只占用int数组所需内存的12.5%。


或者我们可以使用32位来存储九位数字,或者使用64位来存储19位数字。 - gnasher729

3
我有一个计算阶乘的解决方案,对于n≤15000有效。10000的阶乘可以在1秒内计算出来,计算阶乘不到2秒钟。 (当然,您的问题并没有提及时间限制,这些时间完全取决于机器)。无论如何,概念非常简单。我使用一个字符数组,该数组的第一个字符为“1”。LSB从索引0开始存储。变量m(根据我的程序)跟踪阶乘长度。 m的最终值是阶乘中的数字数量,字符数组的(m-1)th元素是阶乘的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;
}

3

好的,您需要使用数组编写自己的数学例程。加法非常容易,乘法有点困难,但仍然是可能的。

编辑:想要发布一个示例,但Srivatsan Iyer的示例已经足够好了。


3
一个 BigInteger 类可以解决你的问题,上面的 C 实现让你了解到如何实现 BigInt,只是代码针对计算阶乘进行了速度优化和定制化。

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

1
下面显示的代码:
#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;
}

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

1

这其实很简单。以下是两种方法,一种精确,另一种是近似值。对于精确的数字,任何超过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'), '_');
}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接