Факториал больших чисел

Question

Нужно посчитать факториал числа N, где 1<=N<=1000. Также нужно обеспечить до 3000 символов в ответе. Я написала программу и в компиляторе она работает прекрасно:

#include <stdio.h>
#include <gmp.h>

static void
factorial (long n, mpz_t r)
{ 
  mpz_init_set_si (r, 1);
  for (; n > 1; n--) {
    mpz_mul_si (r, r, n);
  }
}

int
main (void)
{
  int n;
  mpz_t r;
  while (scanf ("%d", &n) == 1) {
    factorial (n, r);
    gmp_printf ("%Zd\n", r);
  }
  return 0;
}

Но система тестирования не принимает код, т.к. не знает библиотеки GMP. Подскажите, как это обойти?

Answer 1

Скорее всего система тестирования от вас требует знания того, как работает длинная арифметика, а также умения записать это в коде (то есть достаточного владения языком программирования). Вряд-ли целью системы является проверка лаконичности или простоты вашего кода.

Но если вам уж совсем не хочется реализовывать вручную длинную арифметику, то я вижу ещё один выход: взять код библиотеки и скопипастить его себе в файл. С этим могут возникнуть проблемы:

у системы скорее всего есть лимит на размер решения, а вы можете так его превысить;
если ваше решение также будет проверять человек (например, если вы выполняете задание как ученик, то иногда учителя так делают), то вашу уловку раскроют;

По сути такой трюк практически равносилен списыванию в случае, если вашим заданием было написать код именно на С. Если же из вариантов также доступны Java или Python (которые поддерживают длинные числа на уровне стандартной библиотеки), то это скорее выравнивание шансов :)

PS: вот вариант библиотеки, которую можно было бы встроить себе в решение: . В тестах даже есть пример вычисления факториала с её использованием.

Answer 2

Вот другое решение, но система тестирования опять-таки не хочет его принимать...

int main(int argc, char** argv)
{
    int i,j,d,sz,n=30;
    char *f=calloc(2,sizeof(char));
    *f='1';
    for(d=0,i=1; i<=n; i++)
    {
        sz=strlen(f);
        for(j=sz-1; j>=0; j--,d/=10)
        {
            d+=(f[j]-'0')*i;
            f[j]=d%10+'0';
        }
        for(sz++; d; d/=10,sz++)
        {
            f=realloc(f,(sz+1)*sizeof(char));
            memmove(f+1,f,sz*sizeof(char));
            *f=d%10+'0';
        }
        //printf("%s\n",f);
    }
    printf("%d!=%s\n",n,f);
    free(f);
    system("pause");
    return 0;
}

Answer 3

Короче говоря, вот такой код в итоге приняла система:

#include<stdio.h>
 
#define MAX 3000

int multiply(int x, int res[], int res_size);
 
void factorial(int n)
{
    int res[MAX];
     
    res[0] = 1;
    int res_size = 1;
     
    for (int x=2; x<=n; x++)
        res_size = multiply(x, res, res_size);
 
    for (int i=res_size-1; i>=0; i--)
        printf ("%d",res[i]);
}
 
int multiply(int x, int res[], int res_size)
{
    int 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;
        res_size++;
    }
    return res_size;
}
 
int main()
{   int n;
    scanf ("%d", &n);
    factorial(n);
    return 0;
}

БЛОГ НА HUSL

Факториал больших чисел

Ответы (3 шт):