Projeto Euler – #48

O problema #48 do projeto Euler é bem simples. A série 11 + 22 + 33 + … + 1010 = 10405071317. Qual os últimos 10 dígitos da série 11 + 22 + 33 + … + 10001000

Bem, dá para fazer até no papel. Mas como o meu objetivo é aprender J, então vou resolver em J. Mas vou resolver passo a passo conforme o enunciado. Primeiro a geração da sequencia:

>:i.10x
1 2 3 4 5 6 7 8 9 10

Como a sequencia inicia com zero, devemos incrementar os elementos >: e o x foi utilizado para trabalhar com precisão estendida.

^~>:i.10x
1 4 27 256 3125 46656 823543 16777216 387420489 10000000000

O ^ irá elevar um número a um determinado expoente e, como o ~ duplica a lista antes do verbo, significa elevar um número a ele mesmo.

Para somar os elementos de uma lista, inserimos / o verbo + entre cada elemento dela. Como resultado temos:

+/^~>:i.10x
10405071317

Ok, está conforme o enunciado. Para obtermos os últimos dez dígitos do resultado, primeiro deveremos converter o número para um string utilizando “: e, logo em seguida, obter os últimos dez dígitos _10{. (como foi visto na resolução do problema #13, 10{. retorna os 10 primeiros elementos)

_10{.":+/^~>:i.10x
0405071317

A solução não é otimizada e resultou em um tempo mais longo do que eu espera para a sequencia 1…1000. Apesar do problema permitir que eu exclua 100 número dos cálculos (como desejamos os últimos dez dígitos e todo o múltiplo de dez ira gerar um valor como dez ou mais zeros que não seriam significativos na soma), essa exclusão não melhorou muito a performance do cálculo. Após resolver o exercício e entrar no fórum do problema, uma outra forma de resolução do problema em J possui uma performance bem melhor. Enquanto a minha leva 3s, o método lá leva 0.09s. Mas é para quem já está no nível 1 de aprendizado de J.

=-=-=-=-=
Powered by Blogilo

Anúncios