GIVEN:
Compute the EXACT value of:
You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long.
For the record, the exact value of 100! is:
93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,
468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,
697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000
The input to this program will be one or more lines each containing zero or more leading spaces, a value for N, one or more spaces, and a value for M. The last line of the input file will contain a dummy N, M pair with both values equal to zero. Your program should terminate when this line is read.
The output from this program should be in the form:
N things taken M at a time is C exactly.
100 6
20 5
18 6
0 0
100 things taken 6 at a time is 1192052400 exactly. 20 things taken 5 at a time is 15504 exactly. 18 things taken 6 at a time is 18564 exactly.
100 50 100 50 100 50 100 50 ...
Por isso, vamos pre-calcular os resultados, ou seja, calcular as respostas para todos os N e M possíveis. No sample output, pode-se ver que a resposta para 100 6 não cabe num inteiro; para 100 50 nem num long long. Também não podemos usar doubles, porque apesar de poderem representar números muito grandes, têm pouca precisão. A solução é usar uma representação de números grandes num array de chars, e fazer rotinas para somar. Isto é um tipo de problemas muito comum que envolvem usar números muito grandes.
Quanto a como calcular as combinações, basta lembrar o triângulo de Pascal e a fórmula recursiva: C(n,k) = C(n-1, k) + C(n-1, k-1). Assim, definimos C(0,0) = 1 e os outros calculamos iterativamente. Os resultados são armazenados numa matriz. Implementação em C:
#include <stdio.h>
#include <string.h>
#define MAX 100
#define BN_MAX 1000
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;
}
}
BigNum C[MAX+1][MAX+1];
char s[BN_MAX+1];
int main()
{
int n, p;
int i, j;
bignum_str2("1", &C[0][0]);
for (i = 1; i <= MAX; i++) {
bignum_copy(&C[0][0], &C[i][0]);
bignum_copy(&C[0][0], &C[i][i]);
for (j = 1; j < i; j++)
bignum_add(&C[i-1][j], &C[i-1][j-1], &C[i][j]);
}
for (;;) {
scanf("%d %d", &n, &p);
if (n == 0 && p == 0)
break;
bignum_2str(&C[n][p], s);
printf("%d things taken %d at a time is %s exactly.\n", n, p, s);
}
return 0;
}
O trabalho importante está na função main: definimos C(0,0) como 1 e depois para cada n (variável i no código), definimos C(n,0) = 1 e C(n,n) = 1, e para os outros C(n,k) usamos a fórmula recursiva. Processar o input é só converter a representação em array para uma string. Esta conversão podia não ser necessária se a representação fosse pela mesma ordem que se escreve, mas eu achei que era mais simples ter uma representação ao contrário :)
As funções relacionadas com a estrutura BigNum fazem partem de uma pequena biblioteca que fiz para estes problemas. Aconselho a fazerem uma vossa para também usarem nestes problemas e levaram uma cópia imprimida para os concursos. Além de somar, também fiz funções para multiplicar, subtrair, dividir, raiz, etc. Um dia destes meto esse código todo aqui no site :)