Repasadme una recursiva.

[pakoito]

Bueno, es para wartricks. Una recursiva para calcular el rango de movimiento. Os pongo el enunciado y mi resolución utilizando pseudocódigo medio C medio Pascal.


Código que permita calcular el rango movimiento de una criatura, con los siguientes extras:
-Cada criatura tiene un numero de puntos de movimiento diferente. Los costes de moverse una casilla 100ptos, en diagonal 141, cambiando los valores en función del tipo de terreno de la casilla (factor_mov).
-Tablero 10x10 almacenado en una array.
-Para marcar las casillas, un código de colores: negro fuera del rango, amarillo dentro. En las imágenes a continuación el rojo representa el rango, el amarillo el ganado con las diagonales.

http://img222.imageshack.us/img222/130/grid102ne0.jpghttp://img86.imageshack.us/img86/5130/grid103eq3.jpghttp://img86.imageshack.us/img86/4909/grid104vv4.jpghttp://img86.imageshack.us/img86/4037/grid105bg3.jpg





//Llamada a la función
.
.
.
tablero_a_negro(tablero);
movim(tablero, posicionx, posiciony, movimiento_criatura)
.
.
.



movim(tab, posx, posy, mov_cri)//todo por valor

mov_n(tab, posx, posy, mov_cri);//moverse hacia arriba, norte
mov_s(tab, posx, posy, mov_cri);
mov_e(tab, posx, posy, mov_cri);
mov_o(tab, posx, posy, mov_cri);
mov_no(tab, posx, posy, mov_cri);//movimiento en diagonal noroeste
mov_ne(tab, posx, posy, mov_cri);
mov_so(tab, posx, posy, mov_cri);
mov_se(tab, posx, posy, mov_cri);

final movim;


//ahora solamente pondré una función en línea y otra en diagonal, ya que el resto son similares cambiando un par de parámetros


mov_n(t,px,py,mov) //todo por valor

if ((mov>=(100*factor_mov)) and (py+1 <=10) and (es_amarilla_casilla(t[px,py+1]))) //si nos queda movimiento, no nos salimos del tablero y no hemos pasado por la casilla antes
y++
mov=mov-(100*factor_mov)
cambia_color(t[px,py]) //cambiamos el color de la casilla a amarillo
movim(t,px,py,mov); //llamamos a movimiento con la nueva posici&#243;n para que calcule los siguientes saltos

fin mov_n;




mov_no(t,px,py,mov) //todo por valor

if ((mov>=(141*factor_mov)) and (py+1 <=10) and (px+1 <=10) (es_amarilla_casilla(t[px+1,py+1]))) //si nos queda movimiento, no nos salimos del tablero y no hemos pasado por la casilla antes
y++
x++
mov=mov-(141*factor_mov)
cambia_color(t[px,py]) //cambiamos el color de la casilla a amarillo
movim(t,px,py,mov); //llamamos a movimiento con la nueva posici&#243;n para que calcule los siguientes saltos

fin mov_no


&#191;Cre&#233;is que funcionar&#225;? &#191;correctamente? Y lo que m&#225;s me preocupa...&#191;es demasiada carga para el micro de un tel&#233;fono m&#243;vil?

Un saludo!

[swapd0]

Las funciones recursivas, si haces mas de una llamada suelen chupar bastante cpu, y depende de los parametros y profundidad memoria.

Creo que es mejor que guardes los posibles movimientos en una lista (cola), la idea seria asi:
Metes la posicion inicial en la lista y llamas a calcular el rango con la lista (solo 1 elemento)
sacas un elemento de la lista (por el principio)
calculas los posibles movimientos, marcando las casillas, y metiendo solo los posibles (por el final)
ir a 2 hasta que la lista se vacieEsto es lo mismo que hacerlo recursivo, pero es mas eficiente.
Editado:
Ademas las funciones recursivas son un engorro para depurarlas, incluso las mas sencillas.

[pakoito]

Las funciones recursivas, si haces mas de una llamada suelen chupar bastante cpu, y depende de los parametros y profundidad memoria.

Creo que es mejor que guardes los posibles movimientos en una lista (cola), la idea seria asi:
Metes la posicion inicial en la lista y llamas a calcular el rango con la lista (solo 1 elemento)
sacas un elemento de la lista (por el principio)
calculas los posibles movimientos, marcando las casillas, y metiendo solo los posibles (por el final)
ir a 2 hasta que la lista se vacieEsto es lo mismo que hacerlo recursivo, pero es mas eficiente.
Editado:
Ademas las funciones recursivas son un engorro para depurarlas, incluso las mas sencillas.
Es una opci&#243;n y si que lo veo, ma&#241;ana a ver si me lo curro y te ense&#241;o una versi&#243;n 2.0


Un colega y yo discuti&#233;ndolo me cont&#243; que en algoritmia dieron salto de caballo y para eso utilizaban plantillas de movimiento metidas en arrays bidimensionales, del tipo=[2,1,-1,2],[1,2,2,1] e ir sumando y restando desde la posici&#243;n inicial. Mi problema son los tipos de terreno, que aplicarlos ah&#237; es dif&#237;cil o casi imposible si no se te ocurre la "f&#243;rmula m&#225;gica".


&#191;M&#225;s ideas?

[Puck2099]

Yo después de 6 horas ininterrumpidas haciendo la memoria de una práctica no estoy para mirar código, pero estoy con swapd0 en que no es buena idea usar una función recursiva en un dispositivo limitado como un móvil, ya no por tema de CPU que será igual que iterativa, pero principalmente por la pila que tenga implementada que eso sí que es limitado y como te pases casca el programa.

Saludos

[pakoito]

Versi&#243;n 2.0: ahora con menos recursividad.


//Llamada a la funci&#243;n
.
.
.
tablero_a_negro(tablero);
meter_primero(lista, posicion);
while (not(esvacialista(lista))) do
movim(tablero, lista, movimiento_criatura)
done
.
.
.



movim(tab, lista, mov_cri)//todo por valor

mov_n(tab, lista, mov_cri);//moverse hacia arriba, norte
mov_s(tab, lista, mov_cri);
mov_e(tab, lista, mov_cri);
mov_o(tab, lista, mov_cri);
mov_ne(tab, lista, mov_cri);//movimiento en diagonal noreste
mov_no(tab, lista, mov_cri);
mov_so(tab, lista, mov_cri);
mov_se(tab, lista, mov_cri);

final movim;


//ahora solamente pondr&#233; una funci&#243;n en l&#237;nea y otra en diagonal, ya que el resto son similares cambiando un par de par&#225;metros


mov_n(t,lista,mov) //todo por valor

pop(lista, pos); //pop es sacar+borrar el primero.
px=pos.x
py=pos.y
if ((mov>=(100*factor_mov)) and (py+1 <=10) and (es_amarilla_casilla(t[px,py+1]))) //si nos queda movimiento, no nos salimos del tablero y no hemos pasado por la casilla antes
y++
mov=mov-(100*factor_mov)
cambia_color(t[px,py]) //cambiamos el color de la casilla a amarillo
pos.x=px
pos.y=py
meter_final(lista, pos) //llamamos a movimiento con la nueva posici&#243;n para que calcule los siguientes saltos

fin mov_n;




mov_ne(t,lista,mov) //todo por valor

pop(lista, pos); //pop es sacar+borrar el primero.
px=pos.x
py=pos.y
if ((mov>=(141*factor_mov)) and (py+1 <=10) and (px+1 <=10) (es_amarilla_casilla(t[px+1,py+1]))) //si nos queda movimiento, no nos salimos del tablero y no hemos pasado por la casilla antes
y++
x++
mov=mov-(141*factor_mov)
cambia_color(t[px,py]) //cambiamos el color de la casilla a amarillo
pos.x=px
pos.y=py
meter_final(lista, pos) //llamamos a movimiento con la nueva posici&#243;n para que calcule los siguientes saltos

fin mov_ne