Вычислить факториал сколь угодно большого числа, указав все цифры

Ответ 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' - всего лишь целочисленный массив, а factorial - простая функция, которая умножает заданное число на "большое число".

Надеюсь, что это решает ваш запрос.

Ответ 2

Принятый ответ в порядке, но это С++; мы можем сделать лучше. Пусть начнется наш собственный класс Bignum с полностью неограниченным количеством цифр.

Для максимальной эффективности мы будем работать с чистыми двоичными числами, упаковывая каждый элемент массива с таким количеством бит, как мы можем эффективно обрабатывать. Более простой подход - хранить в каждом элементе одну десятичную цифру. Здесь я пошел на компромисс, сохраняя 9 десятичных цифр в каждом элементе uint32_t.

Данные хранятся мало-endian, так как гораздо легче расширить a 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;
}

Ответ 3

Хорошее решение Шривацана Айера и мое предложение:

• По-прежнему можно повысить эффективность памяти, используя массив unsigned char, а не используя массив int для хранения цифр. Это займет всего 25% от потребности памяти в массиве int.

• Для лучшей оптимизации памяти мы также можем использовать один байт, чтобы представить 2 цифры. Поскольку достаточно всего 4 бита, чтобы представить любую цифру от 0 до 9. Таким образом, мы можем упаковать две цифры в один байт, используя побитовые операции. Это потребует 12,5% потребности в памяти для массива int.

Ответ 4

Ну, вам придется писать свои собственные математические подпрограммы с использованием массивов. Это очень просто для добавления, умножение немного сложнее, но все же возможно.

РЕДАКТИРОВАТЬ: хотел опубликовать пример, но пример Шриватсана Майера просто замечательный.

Ответ 5

Класс BigInteger решит вашу проблему, а реализация C выше дает вам представление о том, как будет реализован BigInt, за исключением того, что код оптимизирован для скорости и предназначен для вычисления только факториала.

Ответ 6

У меня есть решение для вычисления факториала, которое отлично работает, по крайней мере, для n <= 15000. Факториал 10000 можно рассчитать менее 1 секунды, а для вычисления факториала требуется менее 2 секунд. (Конечно, ваш вопрос ничего не говорит о временных ограничениях, и эти тайминги полностью зависят от машины). В любом случае, концепция довольно проста. Я использую массив char. Первым символом массива является "1". LSB хранятся из индекса, начинающегося с 0. Переменная (m в соответствии с моей программой) отслеживает факториальную длину. Конечным значением m является количество цифр в факториале, а (m-1) -й элемент массива char - 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;
}

Ответ 7

Это на самом деле довольно легко. Вот два способа. Одно точное, а одно - приближение. Для точных цифр любое число более 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 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'), '_');
}

Ответ 8

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

Ответ 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;
}

Ответ 10

Поскольку все проголосовали за Шривацана, я просто сомневаюсь в этой проблеме. Нужно ли хранить все цифры? Если да, то решение Шривацана прекрасное. Если нет, почему бы просто не отображать числа, как вы вычисляете факториал? Я не форматирую вывод правильно, но это может служить цели.

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

UPDATE Для всех downvoters, хотя этот 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.

Я думал, что это то, о чем спросили.