Java - Backtracking (Java)

 
Vista:

Backtracking (Java)

Publicado por Backtrack (1 intervención) el 13/01/2015 17:27:43
Buenas tardes,

Necesito una solución para un problema de backtracking, a continuación o pongo el enunciado, gracias:

Dado un conjunto de palabras C, y dos palabras a, b pertenecientes a C, formar, si es posible, una cadena de palabras tal que:

▪ la primera palabra sea a
▪ la última palabra sea b
▪ todas las palabras de la cadena sean elementos de C
▪ cada palabra de la cadena sea igual a la precedente, cambiando en ella una única letra.

Por ejemplo, si C contiene las palabras del diccionario Merriam- Webster, y las palabras referidas son stone y money, es posible formar la cadena: {stone store shore chore choke choky cooky cooey coney money}

La solución se presentará definiendo la clase:

/**
* Las instancias de esta clase sirven para resolver el puzle
* descrito en el enunciado. Cada instancia almacena un conjunto
* de palabras.
*/
public class Puzle {
public Puzzle(String[] palabras){}
Precondición:
◦ el array palabras no contiene valores null
◦ todos los valores de palabras son distintos unos de otros (en el sentido definido por equals)
Descripción: Construye una nueva instancia, que almacena el conjunto de palabras especificado.

public List<String> resolver(String a, String b){}
Precondición: a y b son distintos de null.
Devuelve: null, si no es posible formar una cadena de palabras con las características indicadas (ver arriba): el conjunto de palabras C es el especificado en la constructora. En caso contrario, devuelve una cadena de palabras con esascaracterísticas.
}
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder