Este es un problema de optimización parecido al problema de las monedas.
El juego es así, dado un n:
· Si n es divisible por 3, n = n/3
· SI n es divisible por 2, n = n/2
· Si no cumple las anteriores, n = n -1 .
Ahora lo que tengo que conseguir es el menor número de operaciones posibles.
Si nosotros lo pensamos así:
Código
void juego (int n){ if (n == 1) return ; if (n%3 == 0){ juego(n/3); } else if (n%2 == 0){ juego(n/2); } else{ juego(n-1); } }
No conseguiríamos el óptimo, ya que si por ejemplo pongo 10
El resultado es:
Código:
10/2 = 5
5-1 = 4
4/2 = 2
2/2 = 1
Utilicé 4 monedas para resolver el problema, cuando en realidad la solución óptima es:
Código:
10-1 = 9
9/3 = 3
3/3 = 3
Estoy intentando de resolver el óptimo algoritmo todavía estoy pensando, pero cualquier respuesta me vendría bien.
Saludos.