Continuando a série de resoluções dos problemas do Project Euler, e considerando aqueles que foram resolvidos por poucas pessoas, escolhi o problema 29 para apresentar a sua solução.
Mas vamos ao enunciado do problema:
Considere todas as combinações de inteiros de ab para 2 <= a <= 5 and 2 <= b <= 5:
22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125Se os números fossem dispostos em ordem numérica, removendo todas as repetições, temos a seguinte sequência de 15 elementos distintos:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
Quantos termos distintos existem na sequência gerada por 2 <= a <= 100 e 2 <= b <= 100?
A solução para este problema pode ser facilmente encontrada se usarmos uma linguagem que nos fornceça uma abstração para trabalharmos números grandes (com ~ 200 dígitos) e conjuntos sem repetição (em muitas linguagens chamados de set). Com essas premissas, decidi resolver o problema utilizando Scala.
O código que resolve o problema, apresentado abaixo, é bem simples, principalmente pelas abstrações oferecidas pelas classes BigInt e Set.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
object Problem29 { def main(args: Array[String]) { var valueSet = scala.collection.mutable.Set.empty[BigInt] for(i < - 2 to 100) { for(j < - 2 to 100) { var value = BigInt(i) value = value.pow(j) valueSet.add(value) } } println("The solution is: " + valueSet.size) } } Problem29.main(args) |
Bom, é isso, simples e rápido. O tempo total de execução é algo em torno de 8 segundos e a resposta final é 9183.
Em breve mais soluções! 🙂