C中10000因子

Question

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

struct node;
typedef struct node* PtrToNode;

struct node {
  long long n;
  PtrToNode next;
};

PtrToNode factorial(int n, PtrToNode init);
void multiply(long long n, PtrToNode init, long long carry);

int main() {
  int n;
  while (1) {
    scanf("%d", &n);
    if (n > 0) {
      break;
    } else if (n == 0){
      printf("1\n");
      return 0;
    } else {
      printf("Retry.\n");
    }
  }
  PtrToNode init = malloc(sizeof(struct node));
  init->n = 1;
  init->next = NULL;
  PtrToNode head = factorial(n, init);
  PtrToNode tail = reverse(head);
  PtrToNode backup = tail;
  printf("%lld", tail->n);
  tail = tail->next;
  while(tail != NULL) {
    printf("%04lld", tail->n);
    tail = tail->next;
  }
  PtrToNode t;
  while (backup != NULL) {
    t = backup;
    backup = backup->next;
    free(t);
  }
}


PtrToNode factorial(int n, PtrToNode init) {
  for (int i = 1; i <= n; i++)
    multiply(i, init, 0);
  return init;
}

void multiply(long long n, PtrToNode init, long long carry) {
  long long temp = n * init->n + carry;
  init->n = temp % 10000;
  carry = temp / 10000;
  if (init->next != NULL) {
    multiply(n, init->next, carry);
  } else if (carry > 0) {
    init->next = malloc(sizeof(struct node));
    init->next->n = carry;
    init->next->next = NULL;
  } else {
    return;
  }
}

这是我计算10000阶乘的函数,我已经计算出与在线数据相比的正确答案.但是,当我将n的范围限制为[0.999]时,我甚至无法计算2000阶乘.为什么当我将n'范围转换为[0,9999]时,它可以计算出2000!甚至10000!？

Answer 1

将数字簇限制为三位数的问题是将三位数乘以1,000以上的值可能会产生四位数的进位.

虽然这不会立即产生问题,但是当您将值传递到计算链时,错误将会累积.2000年的结果超过5000位!进位溢出肯定会在结果中产生可见的错误.这发生在计算2000年的第1258步!

对于四位数群集而言,这不会发生这种情况,因为进位可以"溢出"到下一个数字的唯一位置是最后一个群集的计算,并且long long有足够的空间来容纳这个而没有溢出.