In these days you can more and more often happen to see programs which perform some useful calculations being executed rather then trivial screen savers. Some of them check the system message queue and in case of finding it empty (for examples somebody is editing a file and stays idle for some time) execute its own algorithm.
As an examples we can give programs which calculate primary numbers.
One can also imagine a program which calculates a factorial of given numbers.
In this case it is the time complexity of order O(n) which makes troubles,
but the memory requirements. Considering the fact that 500! gives 1135-digit
number no standard, neither integer nor floating, data type is applicable here.
Assumptions: Value of a number ``n" which factorial should be calculated of does not exceed 1000 (although 500! is the name of the problem, 500! is a small limit).
10 30 50 100
10! 3628800 30! 265252859812191058636308480000000 50! 30414093201713378043612608166064768844377641568960512000000000000 100! 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
#include <stdio.h> #include <string.h> #define BN_MAX 2600 /* * representacao em num é do indice 0 e por ordem inversa * por ex, 123 fica num[0] = 3, num[1] = 2, num[2] = 1 * * nao sao feitos checks de overflow, o BN_MAX tem de chegar */ struct BigNum { int size; int sign; char num[BN_MAX]; }; typedef struct BigNum BigNum; void bignum_2str(BigNum *a, char *s) { int i; if (a->sign == -1) *s++ = '-'; if (a->size == 0) *s++ = '0'; for (i = a->size-1; i >= 0; i--) *s++ = a->num[i] + '0'; *s = '\0'; } void bignum_str2(char *s, BigNum *r) { int i; r->sign = *s == '-' ? s++, -1 : 1; while (*s == '0' && *s != '\0') s++; r->size = strlen(s); for (i = r->size-1; i >= 0; i--) r->num[i] = (*s++) - '0'; } void bignum_copy(BigNum *a, BigNum *r) { r->sign = a->sign; r->size = a->size; memcpy(r->num, a->num, r->size); } void bignum_add(BigNum *a, BigNum *b, BigNum *r) { int i, j, k, carry, tmp; if (a->sign == b->sign) { r->sign = a->sign; i = j = k = carry = 0; while (i < a->size || j < b->size || carry) { tmp = carry; carry = 0; tmp += i < a->size ? a->num[i++] : 0; tmp += j < b->size ? b->num[j++] : 0; if (tmp >= 10) { carry = 1; tmp -= 10; } r->num[k++] = tmp; } r->size = k; } } void bignum_mul(BigNum *a, BigNum *b, BigNum *r) { static BigNum amults[10]; BigNum *c; int i, j, k, carry, base; char *num = r->num; r->sign = a->sign == b->sign ? 1: -1; if (a->size < b->size) { c = a; a = b; b = c; } bignum_str2("0", amults+0); bignum_copy(a, amults+1); for (i = 2; i < 10; i++) { bignum_add(a, amults + i - 1, amults + i); } for (i = 0; i < BN_MAX; i++) num[i] = 0; j = base = 0; for (i = 0; i < b->size; i++) { c = amults + b->num[i]; k = carry = 0; j = base; while (k < c->size) { num[j] += c->num[k] + carry; carry = 0; if (num[j] >= 10) { num[j] -= 10; carry = 1; } k++, j++; } if (carry) num[j++] = 1; base++; } r->size = j; } char s[BN_MAX]; BigNum f, tmp, one, f2; char factorial[1001][BN_MAX+1]; int main() { int i, n; bignum_str2("1", &f); bignum_str2("1", &one); bignum_str2("0", &tmp); bignum_2str(&f, factorial[0]); for (i = 1; i <= 1000; i++) { bignum_add(&tmp, &one, &tmp); bignum_mul(&f, &tmp, &f2); bignum_copy(&f2, &f); bignum_2str(&f, factorial[i]); } while (scanf("%d", &n) != EOF) { printf("%d!\n%s\n", n, factorial[n]); } return 0; }Esta implementação de BigNum's não é perfeita mas serve para o problema :) Repare-se que para inputs do tipo
1000 1000 1000 1000 ...o programa não recalcula 1000! todas as vezes. Isto pode ser importante para evitar Time Limit Exceeded caso hajam testes destes. Por isso guardamos o resultado num array de strings. Há vários problemas na acm.uva.es que podem ser resolvidos facilmente depois de ter uma implementação de BigNums. Também levo a minha implementação imprimida para os torneios, nunca se sabe :) Na 1ª edição da TIUP2005, em Aveiro, usei BigNums para resolver o problema B, por isso valeu o tempo de passar o código do papel para o computador. Mais uma vez, sugiro que criem uma implementação vossa de BigNums, são umas rotinas úteis e vale a pena o esforço.