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 Página reemplazada por «{{destruir|trasladado a wikilibros}}».
m desde es.wiki
Línea 1:
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:
{{destruir|trasladado a wikilibros}}
*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 ==
 
Este código no está del todo bien, ya que no se contempla el caso en el que las palabras tienen letras iguales, es decir, es más fácil agregar y quitar algunas letras, que cambiarlas todas.
 
Ejemplo:
casa
asaa
 
es mejor agregar una c al comienzo y eliminar la última letra, que cambiar las letras, cosa que haría el código dado al notar que las palabras tienen la misma longitud.
 
=== Primera clase ===
 
<source lang="java">
import javax.swing.JOptionPane;
 
public class Aplicacion
{
public static void main ( String args[])
{
CambioPalabra palabras;
String palabra_u = leerPalabra("Ingrese la palabra U:");
String palabra_v = leerPalabra ("Ingrese la palabra V:");
palabras = new CambioPalabra ( palabra_u, palabra_v);
int des = palabras.verificarPalabras( palabras.getPal1(), palabras.getPal2());
if ( des == 1)
{
JOptionPane.showMessageDialog( null, "para trasformar la palabra U: " +palabra_u +
",\n en la palabra V: " + palabra_v +
",\n se necesito de: " + palabras.getContador() +
" operaciones.", "RESPUESTA", JOptionPane.PLAIN_MESSAGE);
}
 
}
 
public static String leerPalabra (String mensaje)
{
return JOptionPane.showInputDialog(mensaje);
}
}
</source>
 
=== Segunda clase ===
 
<source lang="java">
public class CambioPalabra
{
public char pal1[];
public char pal2 [];
char tabla_aux[];
int contador;
 
public CambioPalabra ( String u, String v)
{
pal1 = u.toCharArray();
pal2 = v.toCharArray();
tabla_aux = new char[pal2.length];
contador =0;
}
 
public int verificarPalabras ( char[] u, char[]v)
{
if ( u.length == v.length)
{
tabla_aux = cambiarLetras(u, v);
return 1;
}
else
{
if (u.length<v.length)
{
tabla_aux = agregarLetra (u,v);
return 1;
}
else
{
if ( u.length> v.length)
{
tabla_aux= eliminarLetra (u, v);
return 1;
}
}
}
return 0;
}
 
public char[] cambiarLetras ( char [] u, char [] v)
{
char aux[];
aux = new char [v.length];
for ( int i=0; i<u.length; i++)
{
if ( u[i]==v[i])
{
aux[i]=u[i];
}
else
{
contador++;
aux[i]= v[i];
}
}
return aux;
}
/**
* Este metodo calcula cuantas letra hay que eliminar y luego
* cambiar para convertir u en v
* @param u, es la palabra a modificar
* @param v, es la palabra a la que hay que llegar
* @return, retorna una cadena igual a v
*/
public char[] eliminarLetra ( char[]u, char v[])
{
char aux[];
int pos=0;
aux= new char[v.length];
for ( int i=0; i<u.length;i++)
{
if ( i >= pos)
{
if ( pos<v.length)
{
if ( u[i]== v[pos])
{ printf("este codigo no esta 100% terminado");
aux[pos]= v[pos];
pos++;
u[i]='0';
}
}
}
}
contador = (u.length-v.length);
aux = cambiarLetras(aux, v);
return aux;
}
public char[] agregarLetra(char[]u, char[] v)
{
char aux[], aux2[];
aux = new char[v.length];
int pos =0, cant=0;
for (int i =0; i<u.length; i++)
{
aux[i]= u[i];
}
aux2 = aux;
for ( int j=0; j<v.length;j++)
{
 
if ( aux[pos]==v[j])
{
aux[j]='0';
aux2[pos]=v[pos];
pos++;
}
else
{
cant++;
}
 
 
}
if ( cant<(v.length-u.length))
{
contador++;
}
else
{
 
}
aux2 = cambiarLetras(aux2, v);
return aux;
}
 
public char[] getPal1()
{
return pal1;
}
 
public char[] getPal2()
{
return pal2;
}
 
public int getContador()
{
return contador;
}
}
</source>
 
 
simplemnet carlos mi msn killing.saints@live.com para mayor informacion
 
== 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]]
 
[[Categoría:Algoritmos]]
[[Categoría:Optimización]]
[[Categoría:Investigación OperativaP]]