Você conhece o Project Euler?

Quer praticar suas habilidades de programação e matemática de forma simples e interessante? Ou apenas é louco por resolver problemas? Então o Project Euler é seu site ideal. Saiba mais sobre essa ferramenta muito usada tanto por entusiastas quanto profissionais de T.I. do mundo inteiro.

O que é Project Euler e como funciona?

Não há muito segredo: você se registra, escolhe um dos atualmente 370 problemas, resolve da maneira que quiser (pode até à mão, se conseguir!) e o sistema verifica se a resposta está correta. Ao solucionar um problema, o usuário ganha acesso ao tópico do fórum correspondente. Lá é possível ver soluções postadas em diversas linguagens de programação, mostrar seu programa, discutir ideias etc.

Só há duas "regras": o programa deve chegar à resposta em menos de um minuto, para incentivar algoritmos minimamente eficientes, e você não pode simplesmente copiar e colar a resposta do Google, por motivos óbvios. Claro que é válido — e encorajado — procurar maneiras de como resolver o problema.

A graça é justamente esta: ir aprendendo mais sobre a linguagem ou matemática à medida em que os problemas ficam mais difíceis.

O que o Project Euler tem de especial?

O Project Euler oferece uma metodologia de aprendizado particularmente útil em programação e matemática: você é confrontado por um problema e busca conhecimento para resolvê-lo. Ao fazê-lo, você é capaz de desafiar outros problemas, e assim por diante.

Pode parecer que não, mas faz toda diferença a curto e longo prazo. O estudante efetivamente quer obter o conhecimento, e aplica-o logo em seguida. Essa abordagem voltada à resolução de problemas é muito mais próxima ao que a matemática e programação realmente são do que, por exemplo, decorar modelos de problemas. Além de ser bem mais interessante e estimular o engajamento.

Vamos dar uma olhada em um exemplo para ilustrar melhor o ponto.

Exemplo - Problema 1 do Project Euler

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Tradução:

Se listarmos todos os naturais menores que 10 que são múltiplos de 3 ou 5, obtemos 3, 5, 6 e 9. A soma desses múltiplos é 23. Encontre a soma de todos os múltiplos de 3 ou 5 menores que 1000.

Do ponto de vista computacional, é uma questão bem simples que pode ser resolvida por força-bruta. Qualquer um consegue escrever um programa que a resolva em praticamente qualquer linguagem que quiser, mesmo não a conhecendo. Basta implementar o seguinte algoritmo:

soma <- 0

Para i de 1 até 999:

Se i mod 3 = 0 ou i mod 5 = 0, então:

soma <- soma + i

Fim-se

Fim-para

Basta um conhecimento básico de variáveis, controle de fluxo, operações aritméticas e voilá! Mas há algo ainda mais interessante por trás da coisa. Note que o problema faz a seguinte questão:

S(3) + S(5) - S(15) = ?

Onde S(3) é a soma dos múltiplos de 3, S(5) a soma dos múltiplos de 5 e S(15) a soma dos múltiplos de 15. Subtraímos S(15) para eliminar as duplicatas: por exemplo, 15 é um múltiplo tanto de 3 quanto 5, então ele aparece duas vezes. Agora veja que os múltiplos seguem progressões aritméticas:

Múltiplos de 3: {3, 6, 9, ..., 999} -> 333 elementos
Múltiplos de 5: {5, 10, 15, ..., 995} -> 199 elementos
Múltiplos de 15: {15, 30, 45, ..., 990} -> 66 elementos

Podemos usar a fórmula da soma dos n termos de uma progressão aritmética:

$$ S_n = \frac{n(a_1 + a_n)}{2} $$

Daí:

$$ S(3) + S(5) - S(15) = \frac{333 \times 1002}{2} + \frac{199 \times 1000}{2} - \frac{66 \times 1005}{2} $$

O que pode ser facilmente calculado por um programa simples, com complexidade computacional na ordem de O(1).

Fontes

How I Failed, Failed, and Finally Succeeded at Learning How to Code
Project Euler