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

Question

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

我搜索了不同的地方,并在几个论坛上询问.但我想知道是否有任何方法可以在不使用像GMP这样的库的情况下实现这一目标.

谢谢.

Answer 1

GNU Multiprecision库是一个很好的库!但是既然你说不允许使用外部库,那么我认为它的可能性只是采用一个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'只是一个整数数组,factorial是一个简单的函数,它将给定的数字乘以'大数'.

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

Answer 2

接受的答案很好,但这是C++; 我们可以做得更好.让我们开始我们自己的Bignum类,具有完全无限的数字.

为了获得最高效率,我们将使用纯二进制数,使用尽可能多的位来打包每个数组元素.更简单的方法是在每个元素中存储一个十进制数字.在这里,我已经做了妥协,在每个uint32_t元素中存储9个十进制数字.

数据存储为little-endian,因为vector当我们需要更高阶元素时,更容易扩展a .

一旦我们有了这个类,因子函数本身就是简单的.

#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. 通过使用无符号char数组而不是使用int数组来存储数字，仍可以使内存效率更高。它只需要int数组所需内存的25％。

2. 为了获得最佳的内存优化，我们还可以使用单个字节代表2位数字。由于仅4位就足以表示0到9之间的任何数字。因此，我们可以使用按位运算将两个数字打包在一个字节中。这将占用int数组所需内存的12.5％。