Diferencia entre revisiones de «Programación dinámica/Problema del cambio de palabra (programación dinámica en Java)»
Contenido eliminado Contenido añadido
m + hoja suelta |
m Bot: Fixing redirects; cambios triviales |
||
Línea 2:
{{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 más:
* abbac → abcac (cambiamos b en la posición 3 por c)
* →abcbc (cambiamos a en la posición 4 por b)
== Código ==
Línea 123:
{
char aux[];
int
aux= new char[v.length];
for ( int i=0; i<u.length;i++)
Línea 132:
{
if ( u[i]== v[pos])
{
aux[pos]= v[pos];
pos++;
Línea 201:
== Véase también ==
* [[Programación dinámica (computación)]]
* [[Programación dinámica/Problema de la mochila con programación dinámica|Problema de la mochila con programación dinámica]]
* [[Programación dinámica/Problema de las monedas con programación dinámica|Problema de las monedas con programación dinámica]]
[[Categoría:Algoritmos]]
| |||