Solução do Problema de Ontem

Apresento aqui uma solução resumida do problema de ontem. Não pensem que eu achei a solução completa e clara (como espero estar abaixo) de imediato; foi preciso pensar bastante e alguns detalhes só ficaram claros após ler os comentários no The Daily WTF.

O primeiro passo é fazer uma simulação na mão, por exemplo para dez armários:

Na figura acima, os * indicam os toques nos armários e os X indicam os armários que ficaram abertos no final. Deste exercício dá para intuir algumas coisas:

• Se olharmos as colunas (armários) dá apra perceber que neste processo estamos tocando neles conforme os seus divisores.
• Os armários que ficaram abertos correspondem aos "quadrados perfeitos" (quadrados exatos de um número inteiro).
• A distância entre os ármários abertos vai crescendo conforme os números impares ou, se preferir, entre os armários abertos temos um número de armários fechados que correspondem aos números pares. (Isto talvez não seja tão evidente com apenas 10 armários).

Os dois últimos pontos são, por enquanto, hipóteses. Vamos aprofundar um pouco mais no primeiro ponto. Os armários que ficam abertos são os que tem um número impar de divisores, já que os pares de toque se cancelam.

Vamos pensar um pouco em como os divisores se distribuem e como podemos pareá-los. Se um número é divisível por a, ele será também divisível por n/a. Se um número n é divisível por a <= sqrst(n), é fácil perceber que n/a >= sqrt(n), onde sqrt é a raiz quadrada. Em outras palavras, os fatores se distribuem equilibradamente em torno da raiz quadrada. Por exemplo, considerando os fatores do número 6, podemos agrupá-los em (1,6) e (2,3). Já para o número 4, teremos o par (1, 4) e a raiz (2) isolada. Este raciocínio confirma a nossa hipótese de que os armários que ficam abertos são os quadrados perfeitos, e sugere a seguinte solução:

view plaincopy to clipboardprint?

1. void Solucao1 (int n)  
2. {  
3.    int i, max;  
4.   
5.    max = (int) floor(sqrt (n));  
6.    for (i = 1; i <= max; i++)  
7.        printf ("%d ", i*i);  
8. }  

void Solucao1 (int n)
{
   int i, max;

   max = (int) floor(sqrt (n));
   for (i = 1; i <= max; i++)
       printf ("%d ", i*i);
}

E quanto à nossa intuição sobre a distãncia entre as portas abertas? Uma técnica muito útil quando queremos otimizar um algoritmo é fazer os cálculos de forma incremental, calculando o resultado seguinte a partir do anterior. No nosso caso, a fórmula para calcular (n+1)² a partir de n²:

(n+1)² = n² + 2*n + 1

O que sugere uma segunda solução:

view plaincopy to clipboardprint?

1. void Solucao2 (int n)  
2. {  
3.    int i, num;  
4.   
5.    for (i = 1, num = 1; num <= n; num = num + (i << 1) + 1, i++)  
6.        printf ("%d ", num);  
7. }  

void Solucao2 (int n)
{
   int i, num;

   for (i = 1, num = 1; num <= n; num = num + (i << 1) + 1, i++)
       printf ("%d ", num);
}

Esta segunda solução tem as vantagens de eliminar a raiz quadrada e a multiplicação (que ficou reduziada a um shift). Este tipo de técnica (cálculo incremental) é muito útil em processadores mais "fracos" como os que eram usados nos primeiros computadores pessoais ou presentes na maioria dos microcontroladores.