Este es un problema de Topcoder: Declaración de problemas de ChessKnight
Puede encontrar una buena explicación de la solución en el editorial aquí: 2005 TopCoder Collegiate Challenge
El problema se puede resolver si escribimos una función:
double FindProbability(x, y, step) donde (x,y) es la posición del caballero en el tablero de ajedrez, y step es el número de pasos restantes.
- ¿Cuáles son algunas preguntas que se pueden hacer en una entrevista para un programador de PhP?
- ¿Cómo son las entrevistas de Google Internship Host Matching?
- ¿Cómo debería uno responder una pregunta como: cuántas líneas de código ha escrito hasta la fecha?
- Me gusta construir cosas y prepararme para entrevistas técnicas es aburrido, ¿qué debo hacer?
- Antes de una entrevista, ¿los entrevistadores de las principales compañías de software están actualizando su conocimiento de algoritmos / estructura de datos?
Dada una posición (x, y), el caballero puede moverse a otras 8 ubicaciones. Por lo tanto, la probabilidad de que el caballero se mueva a cada una de esas 8 posiciones es 1/8.
Casos base:
Hay 2 posibles casos base:
- Si la posición (x, y) está fuera del tablero, entonces la probabilidad de que esté dentro del tablero es 0. Así que solo
return 0;en este caso - Si paso == 0, entonces no nos quedan más movimientos. En este caso, si el parámetro pasado (x, y) está dentro del tablero, entonces
return 1;
Recursividad:
Una vez que se resuelven los casos base, es fácil ver que la recurrencia sería algo así como:
FindProbability (x, y, step) = [math] \ sum_ {i = 1} ^ {8} [/ math] (FindProbability (next_x, next_y, step-1)) / 8.0
donde next_x, next_y son las siguientes posiciones posibles del caballero en la posición (x, y).
Memoization:
Hay muchos cálculos superpuestos en la recursión anterior. Puede haber numerosas llamadas a la función FindProbability con los mismos parámetros. Para evitar volver a calcular estos valores una y otra vez, simplemente podemos almacenar en caché los valores calculados cada vez que los encontremos y simplemente devolver este valor para llamadas de funciones posteriores con los mismos parámetros.
Para esto, se mantiene una double memo[8][8][MAX_MOVES]double memo[8][8][MAX_MOVES]
Pseudocódigo:
double memo[8][8][100] = FillArray(-1); double FindProbability(int x, int y, int step) { if x,y not within board return 0.; if step == 0 return 1; if memo[x][y][step] != -1 // this value has already been computed return memo[x][y][step]; double ans = 0; for each (next_x, next_y) in nextMoves(x,y) { ans += (FindProbability(next_x, next_y, step-1)) / 8.0; } return memo[x][y][step] = ans; // store the computed value and then return it }