¿Cuantos pasos se necesitan para romper una barra de chocolate de m x n en 1 x 1 pedazos? Puedes romper el pedazo de chocolate horizontal o verticalmente, no puedes romper dos o mas pedazos a la vez (no cortar uno enzima de otro)Respuesta:
Los pasos que se necesitan son m n - 1 veamos porque.
A partir de una pieza, hacemos cortes aumentando el numero total de piezas llevando siempre en minoría uno que viene siendo la pieza existente, porque en un paso lo dividimos en 2, en dos pasos lo dividimos en 3 y así sucesivamente.
Esto tiene lógica porque no podemos tener iguales o mas pasos que pedazos de chocolate.
Obteniendo la función (con ayuda de la profesora).
Si rompemos una barra ya sea horizontal o verticalmente, al ir cortando las piezas siempre vamos a tener mas piezas pero de menor tamaño hasta llegar a uno, en donde siempre la solución va ser el numero que tenemos horizontal por el numero vertical menos uno.
Podemos concluir que nunca va a ver pasos minimos ya que en cualquier lugar que cortemos, siempre sera uno menos que la multiplicación de los lados de la barra.
Caso mas basico.
Suponiendo que las lineas de color negro son los cortes, vemos que son el mismo numero de cortes R(m,n) = mn - 1, R(m,n) = (2)(2) -1, R(m,n) = 3, Podemos ver que es indiferente cortar horizontal o verticalmente y nos da el mismo resultado
Otro caso.
Estuve trabajando en implementarlo en el lenguaje lógico prolog, pero no logre un resultado satisfactorio, siempre obtenía errores, trate también de utilizar el lenguaje Mercury, pero no obtuve el resultado.
Espero que mi explicación les sirva, si tienen algún comentario acerca de esta entrada, espero me digan ya que estoy abierto a cualquier error.
Te pongo los tres del reporte 5. Si logras luego el programa lógico, puedes sacar como puntos extra los 2 que faltaron del reporte 6 de la solución por programación.
ResponderEliminar