Ответ 1

Никакой стандартный тип данных C не будет точно обрабатывать числа, равные 100!. Ваш единственный вариант, если использовать произвольную арифметику целых чисел, либо через библиотеку, либо самостоятельно.

Если это всего лишь какой-то хобби-проект, я бы попробовал попробовать его сам. Это весело. Если это связано с работой, используйте уже существующую библиотеку.

Самый большой тип данных C, который вы обычно получите, - это 64-битное целое число. 100! находится в порядке 10 ¹⁵⁷ который берет большую часть 500 бит, чтобы точно хранить как целое число.

Ответ 2

100 факториал огромен, а точнее он 93326215443944152681699238856266700490715968264381621468592963895217 59999322991560894146397615651828625369792082722375825118521091686400 00000000000000000000.

Возможно, вам следует использовать библиотеку bignum, например GMP. Он получил приятные документы, довольно последовательный интерфейс, скорость, и если вы работаете в Linux, у вашего дистрибутива, вероятно, есть пакет (я думаю, что он устанавливает его по умолчанию)

Ответ 3

Чтобы приблизительно вычислить факториалы больших чисел, вы можете пойти следующим образом:

n! =  n * (n-1)!
so log(n!) = log(n) + log(n-1!)

Теперь вы можете использовать динамическое программирование для вычисления log (n!) и вычисления п! as (base) ^ (log-value)

Ответ 4

Если вы не хотите использовать библиотеку bigint, лучше всего использовать stdlib, используя long double и tgammal() из math.h:

long double fact(unsigned n)
{
    return tgammal(n + 1);
}

Это даст вам 100! с точностью до 18 десятичных знаков на x86 (т.е. 80 бит long double).

Точная реализация не так уж и сложна:

#include <math.h>
#include <stdio.h>
#include <string.h>

void multd(char * s, size_t len, unsigned n)
{
    unsigned values[len];
    memset(values, 0, sizeof(unsigned) * len);
    for(size_t i = len; i--; )
    {
        unsigned x = values[i] + (s[i] - '0') * n;
        s[i] = '0' + x % 10;
        if(i) values[i - 1] += x / 10;
    }
}

void factd(char * s, size_t len, unsigned n)
{
    memset(s, '0', len - 1);
    s[len - 1] = '1';
    for(; n > 1; --n) multd(s, len, n);
}

int main(void)
{
    unsigned n = 100;
    size_t len = ceill(log10l(tgammal(n + 1)));
    char dstr[len + 1];
    dstr[len] = 0;
    factd(dstr, len, n);
    puts(dstr);
}

Ответ 5

Каждый говорит вам правильный ответ, но еще пару пунктов.

• Ваша первоначальная идея использовать double для получения более широкого диапазона не работает, потому что double не может точно хранить эти данные. Он может выполнять вычисления, но с большим количеством округления. Вот почему существуют библиотеки bigint.

• Я знаю, что это, вероятно, пример из учебника или примера сайта, но выполнение неограниченной рекурсии укусит вас в какой-то момент. У вас есть рекурсивное решение для того, что по сути является итеративным процессом. Вы поймете, почему этот сайт назван так, как при попытке запустить вашу программу с большими значениями (Try 10000).

Простой итеративный подход выглядит следующим образом

  int answer, idx;

  for (answer = 1, idx = 1; idx <= no_of_inputs; idx++ ) {
    answer = answer * idx;
  }
  printf("Factorial of %3d =  %d\n", no_of_inputs, answer);

Ответ 6

вот что я сделал, чтобы решить загадку google несколько лет назад, она использует библиотеку GMP http://gmplib.org/:

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

void fact(mpz_t r,int n){
    unsigned int i;
    mpz_t temp;
    mpz_init(temp);
    mpz_set_ui(r,1);
    for(i=1;i<=n;i++){
        mpz_set_ui(temp,i);
        mpz_mul(r,r,temp);
    }
    mpz_clear(temp);
}
int main(void) {
    mpz_t r;
    mpz_init(r);
    fact(r,188315);
    /* fact(r,100); */
    gmp_printf("%Zd\n",r);
    mpz_clear(r);
    return(0);
}

gcc -lgmp -o fact fact.c

./факт

Ответ 7

вы можете попробовать перейти к типу unsigned long long, но это максимум, который вы можете получить со встроенными типами. Я бы предложил (как уже упоминал cletus) либо идти с известной реализацией больших чисел, либо писать самостоятельно. "его хорошее упражнение" x 2.

Ответ 8

Если вы хотите использовать только стандартные типы данных, и вам не нужен точный ответ, тогда вычислите логарифм n! вместо n! сам. Логарифм n! легко устанавливается в double (если n не является огромным).

Ответ 9

Любые способы обработки факториала больших чисел в C?

Поскольку факториалы могут быстро превышать диапазон стандартных фиксированных целых чисел ширины и даже типов с плавающей точкой, таких как double, Code должен учитывать тип пользователя, который допускает неограниченную точность целых чисел для точного ответа.

Существуют различные библиотеки с широкими целочисленными точками, но если код нуждается в простом решении, рассмотрите возможность использования строки.

Ниже приведен не быстрый и не учитывающий границ массивов, но он иллюстрирует эту идею. Преобразование '0'-'9' в/из 0-9 настолько много расточительно, но это позволяет легко пошаговую отладку.

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

static char *strfact_mult(char *s, unsigned x) {
  unsigned sum = 0;
  size_t len = strlen(s);
  size_t i = len;
  while (i > 0) {
    sum += (s[--i] - '0') * x;
    s[i] = sum % 10 + '0';
    sum /= 10;
  }
  while (sum) {
    len++;
    memmove(&s[1], s, len);
    s[i] = sum % 10 + '0';
    sum /= 10;
  }
  return s;
}

char *str_fact(char *dest, unsigned n) {
  strcpy(dest, "1");
  while (n > 1) {
    strfact_mult(dest, n--);
  }
  return dest;
}

void test_fact(unsigned n) { 
  char s[1000];
  printf("%3u %s\n", n, str_fact(s, n));
}

int main(void) {
  test_fact(0);
  test_fact(4);
  test_fact(54);
  test_fact(100);
}

Выход

  0 1
  4 24
 54 230843697339241380472092742683027581083278564571807941132288000000000000
100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Ответ 10

Я предполагаю, что, поскольку вы переполняете диапазон int, который составляет около ок. 2 миллиарда. Вы можете получить до 4 миллиардов, если используете unsigned int, но помимо этого вы должны использовать библиотеку bigint.

Ответ 11

100!= 933262154439441526816992388562667004907159682643816214685929 6389521759999322991560894146397156518286253697920827223758251185210 +916864000000000000000000000000

Вы не можете представить число, такое большое с int или long.

Ответ 12

Это, безусловно, связано с переполнением. Вам нужен способ представления больших чисел (unsigned long long даже не будет содержать до 25!).

Ответ 13

В дополнение к советам других, я бы предложил ознакомиться с ограничениями хранения основных типов (int, long, long long,...) для любого используемого вами компьютера/платформы. ( "Если есть сомнения, распечатайте больше!" )

Один более ранний плакат ссылался на предел точности в 80 бит, но особенно на процессор x86.

Другой человек цитировал ISO C90 несколько раз, хотя C99 является последним стандартом; даже если многие компиляторы не полностью реализовали C99, вы, вероятно, обнаружите, что они очень-очень вероятно имеют хотя бы поддержку в течение долгого времени, что должно соответствовать >= 64-битной точности.

Ответ 14

Вычислить большие факториалы без какой-либо внешней библиотеки

_{Это действительно старая проблема. Я вижу большинство ответов, предлагающих внешнюю библиотеку или приблизительный результат, показывая ограничение памяти. Но, думайте немного иначе - вам не всегда нужно использовать integer или double или unsigned long long для программирования математики!}

Я использовал int[] для вычисления Больших факториалов. Этот небольшой код Java может (теоретически) обнаруживать factorial любого числа -

public class BigFactorial {
    public static int[] calculateFactorial(int inputNumber) {
        int[] factorial = initializeFactorial(inputNumber);

        for(int i=inputNumber-1, j, k; i>0; i--){
            for(j=factorial.length-1, k=0; factorial[j] >= 0; j--){
                k += i*factorial[j];
                factorial[j] = k%10;
                k /= 10;
            }

            factorial[j] = k%10;
            k /= 10;
            factorial[j-1] = k;

            for(j=0; factorial[j]<1; j++){
                factorial[j] = -1;
            }
        }

        return factorial;
    }

    private static int[] initializeFactorial(int inputNumber){

        int digits = (int) Math.ceil(inputNumber*Math.log10(inputNumber/2))+2;
        int[] factorial = new int[digits+1];

        for(int i=0; i<factorial.length; i++){
            factorial[i] = -1;
        }

        for(int j=factorial.length-1, i=inputNumber; i>0; j--){
            factorial[j] = i%10;
            i /= 10;
        }

        return factorial;
    }

    public static void showOutput(int[] factorial){
        int i=0;
        while(factorial[i]<1){
            i++;
        }

        for(; i<factorial.length; i++){
            System.out.print(factorial[i]);
        }
    }

    ///test
    public static void main(String[] args) {
        int inputNumber = 5000;
        showOutput(calculateFactorial(inputNumber));
    }
}

Ответ 15

Вот решение для вашего вопроса:

#include <stdio.h>
void factorial(int b){
    int temp = 0, r, size = 0, x;
    int arr[200] = {0};
    int l_b = b-1;
    while(b>0){
        r = b%10;
        arr[size++] = r;
        b = b/10;
    }
    while(l_b >= 2){
        int i=0;
        while(size>0){
         x = arr[i]*l_b+temp ;
         arr[i++] = x%10;
         temp = x/10;
         size--;
        }
       while(temp>0){
          arr[i++] = temp%10;
          temp = temp/10;
       }
      size = i;  --l_b;
    }
    for(int k=size-1;k>=0;k--)
        printf("%d",arr[k]);//ok i'm taking space here
    printf("\n");
}
int main(void) {
    // your code goes here
    int fact;

    scanf("%d\n",&fact);
    factorial(fact); 

    return 0;
}

Ответ 16

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

Причина этого - когда вы вызываете факт (100), вы фактически не запускаете его 100 раз, вы фактически запускаете эту функцию 5050 раз. Что плохо, если он кэширован, тогда это может быть 100 раз, однако еще медленнее запускать вызов функции с помощью операторов if, чтобы запустить цикл.

double print_solution(int n)
{
    double rval = 1;
    unsigned int i;

    for( i = 1; i <= n; i++ ) {
        rval *= i;
    }

    return rval;

}

Используя арифметику arbitary-precision, вы можете сделать ее очень высокой, однако для этого вам нужно использовать библиотеку, или вы можете создать свою собственную библиотеку, но это займет много времени.