
A forma habitual de calcular combinações, que nos ensinaram na escola, é a seguinte:

$$
C_k^n = \frac{n!}{k! \times (n - k)}
$$

No entanto, calcular desta forma numa aplicação informática levanta desde logo dois problemas:

1. A maior parte das linguagens de programação não tem uma função para calcular factoriais, embora
seja muito fácil fazer uma, simplística, é certo, de forma recursiva:

```clike
função factorial(n)
  devolve (n * factorial(n - 1));
fim de função factorial
```

2. Mesmo os mais modestos factoriais atingem rapidamente o limite dos tipos inteiros. Por exemplo,
usando `Int32`, o limite é 2.147.483.647, ou 4.294.967.295 (sem sinal); o reles $13!$ já rebenta
com qualquer um deles. OK, podíamos usar inteiros de 64 _bits_, afinal, quase todos os
processadores actuais são de 64 _bits_ (mas o sistema operativo também tem que ser, não se
esqueçam); ficávamos com limites de 9.223.372.036.854.780.000 ou 18.446.744.073.709.600.000 (sem
sinal). Pois, mas basta um $21!$ para ficarmos logo sem pé outra vez.

Posto isto, que fazer?

Desmontando a fórmula das combinações, poderíamos chegar a uma fórmula recursiva, e respectivo
algoritmo:

$$
\begin{aligned}
C_k^n = [(n - 0) / (k - 0)]
\newline
\times [(n - 1) / (k - 1)]
\newline
\times \dots
\newline
\times ([n - (k - 1)] / [k - (k - 1)])
\end{aligned}
$$

```clike
função numeroDeCombinacoes(n, k, dif)
  se (dif = k - 1) então:
    devolve ((n - dif) / (k - dif));
  senão:
    devolve (((n - dif) / (k - dif)) * numeroDeCombinacoes(n, k, dif - 1));
fim de função numeroDeCombinacoes
```

As funções recursivas, porém, não são lá muito amigas da performance… mesmo com _tail optimization_
(que este exemplo nem tem). Para alguns factoriais mais _musculados_, esta função cedo ia
arrastar-se nos cálculos.

O algoritmo que vou apresentar de seguida foi publicado em 1963 (não, não é gralha, é mesmo
seis-três) por **M. L. Wolfson** e **H. V. Wright**.

```clike
função numeroDeCombinacoes(n, k)
  seja dif = n - k;

  se (k < dif) então:
    seja dif = k;
    seja k = n - dif;

  seja combinações = k + 1;

  se (dif = 0) então:
    seja combinações = 1;
  senão: se (dif >= 2) então:
    para (i = 2; i <= dif; i = i + 1)
      seja combinações = (combinações * (k + i)) / i;
    fim de para;

  devolve combinações;
fim de função numeroDeCombinacoes
```

Reparem como ainda podemos reconhecer a fórmula explicada acima neste formato não recursivo.
É maravilhosamente elegante e (ainda) é o algoritmo mais rápido para se calcular o número de
combinações.



Aqui há dias relembraram-me o quanto eu gosto de datas. Um tipo – que eu não conheço de lado
nenhum – pediu ajuda num fórum para fazer uma função em C que calculasse o número de dias entre
duas datas; provavelmente, e tendo em consideração o pedido, para um trabalho da escola, ou coisa
que o valha. Devo dizer que fui um bocadinho totó e disponibilizei logo ali a função inteira,
quando a ideia de um fórum não é _fazer por_, mas sim _ajudar a fazer_.

Seja como for, só me decidi ajudá-lo por considerar o problema interessante; não é algo que seja
muito comum hoje em dia, até porque a maior parte das linguagens de programação tem bibliotecas
específicas para trabalhar com datas, e esta função é disponibilizada de forma directa. Além
disso, vi que as orientações que já lhe tinham dado não eram, nem de perto, nem de longe, o mais
eficaz que se podia ser.

O problema no meio disto tudo, como não podia deixar de ser, é a existência ou não de anos
bissextos no intervalo. Como Arthur C. Clarke colocou de forma hilariante em
_3001 – Odisseia Final_, “um dia, um dos menores erros de Deus será corrigido e o ano terá 12
meses de 30 dias exactamente iguais”.

Vamos recordar, como aquecimento, como se detecta se um ano é bissexto ou não.

Duma forma básica, um ano é bissexto se o resto da sua divisão por quatro for zero. E esta regra
tem-nos servido razoavelmente. No entanto, como o leitor com mais de 120 anos se recordará, 1900
não foi bissexto; é que há outra regra: um ano **não é bissexto** se o resto da sua divisão por
100 for zero. Porém, ainda agora tivemos a viragem de século, e 2000 _foi_ bissexto! Certo – ainda
falta a terceira regra: um ano **é mesmo bissexto** (e desta, é mesmo para cumprir), se o resto da
sua divisão por 400 for zero.

Resumindo e baralhando: um ano é bissexto se o resto da sua divisão por 400 for zero ou se o resto
da sua divisão por quatro for zero e, por 100, diferente de zero.

Mas vamos ao cálculo da diferença, então.

A pior sugestão que alguma vez ouvi foi a um colega, com
quem mantive uma discussão há uns anos sobre datas e programação, cuja sugestão envolvia o uso e
manutenção de um vector com todos os anos bissextos existentes.

Quando lhe fiz notar a imensidade a que se propunha, dando-lhe datas de interesse histórico, como
o ano da fundação de Portugal, atirou-me à cara, não sem razão, que era um absurdo, visto que a
bissextalidade da forma como a conhecemos hoje em dia, só foi instiuida no calendário Gregoriano,
em vigor desde 1582. Contra-argumentei com possível interesse histórico e académico na diferença
entre as datas usadas no calendário Juliano e Gregoriano e, finalmente, com os anos futuros.

Retirei-me da conversa quando a resposta dele foi “quando se chegar ao limite do que está no
vector, acrescenta-se mais umas centenas de anos bissextos”…

Outra sugestão, que era a tal que deram no fórum, seria percorrer todos os anos, desde o ano da
data mais antiga até ao ano da data mais recente, e testá-los um a um pela sua bissextalidade;
uma melhoria óbvia seria testar um a um até encontrar o primeiro e depois testar apenas de 4 em 4.

Com ou sem melhorias, esta metodologia envolverá sempre iterações, o que não abona nada em favor
da _performance_, e que fará com que intervalos maiores demorem mais tempo a ser calculados.

Qual é a solução que proponho? Calcular, de forma matemática, o número de dias correspondente a
cada data, desde 1 de Janeiro de 0 (sim, ano 0). Sem iterações, apenas operações matemáticas.
O maior problema para isso, é que o dia da bissextalidade é num mês horrível. Sério,
[Júlio César](https://pt.wikipedia.org/wiki/Calend%C3%A1rio_Juliano), em que raio estavas a
pensar? Fevereiro? Porque não no fim do ano? Esse tem de ser o nosso primeiro passo, passar o dia
problemático para o final do ano, e ajustar o ano da data para reflectir essa alteração. Então:

```clike
mesRecalculado = RestoDaDivisao((mes + 9) / 12);
// a seguinte divisão deve ser calculada com recurso a truncagem
// a parte decimal, se houver, é descartada - NÃO É um arredondamento
anoRecalculado = ano - mesRecalculado / 10;
```

Com este cálculo, Março passa a ser o primeiro mês do ano (na realidade, é o mês zero) e Fevereiro
o último. Devido à divisão inteira, quando o mês pedido é Janeiro ou Fevereiro (que assumem como
novo número, respectivamente, 10 e 11), o ano é reajustado como sendo o ano anterior. Com estes
dois cálculos, todos os possíveis dias 29 de Fevereiro estão agora no final de cada ano.

Vamos então calcular o número de dias sem olhar a bissextalidade (365 dias num ano), depois somar
1 por cada 4 anos, subtrair 1 por cada 100 anos e somar de novo 1 por cada 400 anos. A
bissextalidade está agora sob controlo.

Agora que temos os dias todos calculados em relação aos anos, vamos enfiar os meses na ordem
certa; o número de ordem do mês que calculamos anteriormente é multiplicado pelos dias de um ano,
retirando os meses de Janeiro e Fevereiro (isto é, 306 dias), a dividir por 10 (que são os meses
que ficaram à frente de Janeiro e Fevereiro, lembram-se?). Finalmente, vamos somar um dia por
cada mês de 31 dias existente no ano (são 7), e compensar para os 28 dias que Fevereiro,
normalmente, tem, visto que a bissextalidade já foi acertada lá atrás. Como este acerto de 5 dias
tem de entrar no reordenamento dos meses, tem de ser, também, dividido por 10, sendo somado ao
resultado da multiplicação prévia.

Com os meses também já fora do caminho, resta-nos somar o dia da data e pronto… Será?

O que é certo é que estas contas todas, embora aparentem estar correctas à primeira vista, têm
sempre um dia a mais do que é suposto.

Nem queiram saber o que eu passei para chegar a esta conclusão – tive que fazer uma versão mais
intuitiva do cálculo dos dias (percorrendo todos os anos para calcular a bissextalidade) e
comparar uma com a outra em milhares de datas. Mas é isso. No final, é só subtrair um dia.
Resulta sempre.

```clike
// todas as divisões são calculadas com recurso a truncagem
// a parte decimal, se houver, é descartada - NÃO É um arredondamento

mesRecalculado = RestoDaDivisao((mes + 9) / 12);
anoRecalculado = ano - mesRecalculado / 10;

// calcular sem anos bissextos
dias = 365 * anoRecalculado;

// 1ª regra da  bissextalidade
dias = dias + anoRecalculado / 4;

// 2ª regra da bissextalidade
dias = dias - anoRecalculado / 100;

// 3ª regra da bissextalidade
dias = dias + anoRecalculado / 400;

// reordenação e contabilização dos meses
// inclui acerto para os meses de 31 dias menos 2 de Fevereiro
dias = dias + (mesRecalculado * 306 + 5) / 10

// dias da data
dias = dias + dia;

// acerto final
dias = dias - 1;

// estas contas podem ser todas "encomboiadas" numa linha
// aqui estão separadas a bem da clareza
```

Para resolver o nosso problema inicial – calcular a diferença em dias entre duas datas, ainda se
lembram? – é tão simples como efectuar este cálculo para ambas e subtrair uma pela outra. Nem
sequer interessa qual é a mais antiga, desde que devolvam o valor absoluto do resultado.

Para finalizar, vamos verificar as limitações.

Em primeiro lugar, como deve ser óbvio, anos negativos vão dar valores negativos. Para o caso em
concreto, diferença entre datas, até se come, visto que vai dar correcto. Por exemplo, 1 de
Janeiro de 1 AC dará –365 dias, e 1 de Janeiro de 1 DC dará 365 dias. Logo, a mais antiga menos a
mais recente dará –730 dias. Ah, e tal, dirão, mas costuma ser ao contrário, isto é, a mais
recente menos a mais antiga – o que daria zero. Certo, mas tal como disse atrás, se devolverem o
valor em absoluto estão sempre safos, e basta controlarem qual é a mais antiga para ultrapassarem
esta limitação dos anos negativos.

Em segundo lugar, temos a limitação dos inteiros. Ao implementar isto, o mais normal é usar-se um
tipo inteiro, o que normalmente quer dizer 32 _bit_, com sinal, o que vem a dar um limite máximo
de 2.147.483.647. Mas chega e sobra. Esta função vai dar o seu último resultado válido precisamente
no dia 8 de Dezembro do ano cinco milhões, oitocentos e setenta e nove mil, seiscentos e dez. Que,
por incrível que possa parecer, **é bissexto**! E, sim, escrevi por extenso de propósito.

De qualquer forma, usem as bibliotecas disponíveis para lidarem com datas. Isto foi só uma
curiosidade, _just for fun_&hellip;
