Diferencia entre revisiones de «Programación dinámica/Problema del cambio de palabra (programación dinámica en Java)»
Contenido eliminado Contenido añadido
imported>Jison |
|||
Línea 1:
{{a wikilibros}}
El '''problema del cambio de palabra''' se produce cuando siendo "u" y "v" dos palabras ([[Cadena de caracteres|cadenas de caracteres]]). Se desea transformar u en v con el mínimo número de operaciones básicas del tipo siguiente: eliminar un carácter, añadir un carácter, y cambiar un carácter. Por ejemplo, podemos pasar de abbac a abcbc en tres pasos:
*abbac _ abac (eliminamos b en la posición 3)▼
*_ ababc (añadimos b en la posición 4)▼
*_ abcbc (cambiamos a en la posición 3 por c)▼
Sin embargo, esta tranformación no es óptima. Lo que queremos en este caso es [[Diseño|diseñar]] un [[algoritmo]] que calcule el número mínimo de operaciones, de esos tres tipos, necesarias para transformar u en v y cuáles son esas operaciones. En el caso anterior se podría llevar a cabo con dos operaciones nada mas:
*abbac → abcac (cambiamos b en la posición 3 por c)▼
*→abcbc (cambiamos a en la posición 4 por b)▼
▲abbac _ abac (eliminamos b en la posición 3)
▲_ ababc (añadimos b en la posición 4)
▲_ abcbc (cambiamos a en la posición 3 por c)
▲abbac → abcac (cambiamos b en la posición 3 por c)
▲→abcbc (cambiamos a en la posición 4 por b)
== Código ==
=== Primera clase===
<source lang="java">
import javax.swing.JOptionPane;
Línea 48 ⟶ 41:
</source>
=== Segunda clase
<source lang="java">
Línea 197 ⟶ 190:
== Véase también ==
* [[Programación dinámica (computación)]]▼
*[[Problema de la mochila con programación dinámica]]
*[[Problema de las monedas con programación dinámica]]
| |||