elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General (Moderador: Littlehorse)
| | |-+  Algoritmia
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] Ir Abajo Respuesta Imprimir
Autor Tema: Algoritmia  (Leído 4,055 veces)
Leo Gutiérrez.
. . .. ... ..... ........ ............. .....................
Colaborador
***
Desconectado Desconectado

Mensajes: 3.069


/^$/


Ver Perfil WWW
Re: Algoritmia
« Respuesta #14 en: 8 Febrero 2012, 04:52 »

¿y el subforo de algoritmia?

¿Y si lees el post entero?


En línea

Código
  1. (( 1 / 0 )) &> /dev/null || {
  2. echo -e "stderrrrrrrrrrrrrrrrrrr";
  3. }
  4.  
http://leonardogtzr.wordpress.com/
leogutierrezramirez@gmail.com
H1tchclock

Desconectado Desconectado

Mensajes: 263


Binario, Dialéctico e inmerso en la Lógica de 3


Ver Perfil WWW
Re: Algoritmia
« Respuesta #15 en: 21 Febrero 2012, 22:05 »

¿Y si lees el post entero?

Ya lo he leido, incluso fuí uno de los primeros en comentar.... La cuestion es esta, solo es un post, con buenas intenciones....
Un buen video en el YouTube: http://www.youtube.com/watch?v=QsJidER3NbM.

Saludos desde Bolivia.  ;D


En línea

Mi inteligencia es proporcional al tiempo que invierto en internet
YeisonSoto

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Analisis Problema de las 8 reinas (Backtracking)
« Respuesta #16 en: 29 Noviembre 2012, 05:19 »

Hola amigos tengo un pequeño problema con el  algoritmo de las 8  reinas.....

Código
  1.  
  2. <?php
  3.  
  4. function ocho_reinas($pos, $solucion, $diagonal_desc, $diagonal_asc) {
  5.  
  6. if($pos > 7){ //Validación para saber si ha terminado de recorrer todas las posibles soluciones.
  7.  
  8. echo "{";
  9. foreach($solucion as $i =>$j ){ //Recorre el Array de soluciones para mostrarlas.
  10.  
  11. echo "".$j.",";
  12.  
  13. if($i==7){
  14. echo "}";
  15. echo "<br>";
  16. }
  17. }
  18. }
  19. else {
  20.  
  21.     for ($i = 0; $i < 8; $i++) { //Recorremos las filas
  22.  
  23.  
  24.         if(!in_array($i, $solucion) AND !in_array(($pos+$i), $diagonal_asc) AND !in_array(($pos-$i), $diagonal_desc) ) {
  25. //Entra , si esa casilla no está amenazada!
  26.  
  27.  
  28.             $diagonal_asc[$pos] = $pos+$i; //diagonal ascendente.
  29.             $diagonal_desc[$pos] = $pos-$i; //diagonal descendente.
  30.  
  31.             $solucion[$pos] = $i; //Se guarda una posición valida.
  32.  
  33.  
  34.    ocho_reinas($pos+1, $solucion, $diagonal_desc, $diagonal_asc);
  35.  
  36.        }
  37.  
  38.     }
  39.  
  40.  }
  41. }
  42.  
  43.  
  44. $pos = 0; //Posicion inicial
  45. $solucion = Array();//posibles soluciones.
  46. $diagonal_desc = Array();//diagonales descendentes
  47. $diagonal_asc = Array();//diagonales ascendentes .
  48.  
  49.  
  50. ocho_reinas($pos, $solucion, $diagonal_desc, $diagonal_asc);//Se llama al metodo de la lógica de las reinas.
  51.  
  52.  
  53.  
  54. ?>


He hecho  la prueba de escritorio



  y  los datos que arroja  son los mismos hasta cierto punto que muestra la ejecucion del algoritmo...

- Tengo una duda, como  funciona el  la parte recursiva del lagortmo?, es decir c por ejemplo  cuando  la i  del  for va en  1 y se cumple la condicion if(!in_array($i, $solucion)....), al  llamar mi  metodo  recursivamente,  el  for continua con  su  ietraccion normalmente? es decir sigue con i =2, i=3...  y asi  sucesivante,   o  vuelve a iniciar en  0???

espero  que me puedan ayudar...

Gracias...

Algortimo  http://squadronsuicida.99k.org/Reinas/Reinas.php.
Descarga http://squadronsuicida.99k.org/Reinas/Reinas.txt

[-- --]


Prueba http://squadronsuicida.99k.org/Reinas/Reinas_Prueba.php.
Descarga http://squadronsuicida.99k.org/Reinas/Reinas_Prueba.txt
En línea

$Edu$


Desconectado Desconectado

Mensajes: 1.843



Ver Perfil
Re: Algoritmia
« Respuesta #17 en: 29 Noviembre 2012, 16:04 »

Si llamas al metodo otra vez recursivamente el for empieza desde 0 otra vez, porque al leer el bucle de for se inicia la variable i=0 de nuevo.

No entendi bien que es lo que quieres hacer o era solo esa pregunta?
En línea

YeisonSoto

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Re: Algoritmia
« Respuesta #18 en: 29 Noviembre 2012, 17:13 »

Si llamas al metodo otra vez recursivamente el for empieza desde 0 otra vez, porque al leer el bucle de for se inicia la variable i=0 de nuevo.

No entendi bien que es lo que quieres hacer o era solo esa pregunta?


Amigo,  gracias, por responder,  entonces el for arranca nuevamente desde 0?,   y que pasa con las 6 iteraciones restantes i=1, i=2, i=3.....i=7?, se pierden cundo  el  metod es llamado  recursivamente?
volvere  a hacer la prueba de escritorio  a ver como  me da...

- Tengo otra pregunta, donde se aplica el backtraking???,  tengo  entendido  que el  backtraking al  no  encontrar una posible solucion regresa a un  estado  anteriror  y  empieza la busqueda desde ahi....


« Última modificación: 29 Noviembre 2012, 17:16 por YeisonSoto » En línea

$Edu$


Desconectado Desconectado

Mensajes: 1.843



Ver Perfil
Re: Algoritmia
« Respuesta #19 en: 29 Noviembre 2012, 19:35 »

Por las dudas te digo que yo no he entrado a la universidad por lo que algunas cosas no he aprendido aun, no se bien que es la prueba de escritorio, me podrias explicar si quieres.

Cuando el metodo es llamado recursivamente lo que hace ejecutar la funcion de nuevo pero los valores que tenia antes tomados en la funcion anterior quedan guardados en la memoria para que se usen luego. Es complicado explicarte porque para entender todo sin que te quedes con ninguna duda tendrias que aprender el lenguaje ASM para ver como funcionan los programas a nivel del procesador.

Pero por ahora solo te puedo dar un ejemplo de una funcion recursiva para que entiendas mejor.
La funcion para saber el factorial de un numero se puede hacer con un bucle, seguramente lo has hecho alguna vez, donde vas guardando la variable del numero y lo multiplicas por el numero anterior y a ese nuevo numero lo multiplicas por el anterior y todo asi, por ejemplo el factorial de 4 seria 4 * 3 * 2 * 1 y en tu programa harias un bucle con la variable i que vaya desde 4 a 1 donde vas guardando los resultados de las multiplicaciones y vas multiplicando por i hasta que i sea 1 o 2 total al multiplicar por 1 no cambia y se termina el bucle y la funcion.

Pero lo bueno de los metodos recursivos viene aca.. el factorial de 4 (llamemosle 4!) es igual a 4*3! no? y 3! (factorial de 3) se puede calcular 3 * 2! y 2! sabemos que es 2 * 1 que es 2. Entonces al usar un metodo recursivo la funcion solamente quedaria asi:

Factorial(n) {

if n=2 return 2; ' devuelve 2 y sale de la funcion

return n * Factorial(n - 1) ' como en el ejemplo si n es 4 entonces multiplica 4 por factorial de 3.

}

Entonces como se llama de nuevo en medio de la multiplicacion.. el return no sabe que devolver hasta que se termine la funcion Factorial que se envio como parametro el numero 3. Y vuelve el ciclo de nuevo, comprobando si n es igual a 2 y como no lo es se multiplica 3 * Factorial(2) ahora, porque n ya no es mas 4 ahora es 3, pero de nuevo el return "espera" el valor de Factorial(2) para devolver resultado a la multiplicacion. Pero en Factorial(2) ahora n vale 2 asi que devuelve 2 y ya se sabe el primer valor "base".
Asi que ahora que se llego a la base, vuelve todo para arriba poniendo los valores de los returns desde la base hasta el primero que se llamo, asi que Factorial(3) va a devolver como decia 3 * Factorial(2) que es 6. Y Factorial(4) va a devolver 4 * Factorial(3) que como Factorial(3) dio como resultado 6 entonces 4 * 6 es 24 y se termina la funcion.

Una vez que entiendas eso, que por cierto, te puse el codigo asi nomas, ya que no se PHP pero queria darte una mano de todas formas, podras entender mejor como poder hacer tu algoritmo de las 8 reinas usando Backtracking. Fijate que sin una condicion como la que hice de if n= 2 return 2; la funcion no funcionaria porque quedara buscando un valor continuamente y se generaria un bucle infinito que consumiria toda la ram.


Entonces ahora ponte a pensar que si haces una funcion recursiva donde la llamada a la misma funcion es dentro de un bucle casi no tiene sentido, ya que si haces que devuelva un valor la funcion dentro del for, solo devolvera un valor cuando recien comienza, cuando la variable i del bucle for vale 0. Por eso no sirve para eso, una funcion recursiva llamada dentro de un bucle no tendria significado, por lo menos que yo sepa, me puse a pensar en algun ejemplo y lo termine borrando porque no tenia logica asi que no vale la pena complicarse la vida pudiendolo hacer de otra forma.
Pero si es que sirve para algo, en alguna funcion que no devuelva nada, que se encargue de mostrar un mensaje talvez (por eso digo que no tiene sentido hacerlo asi ya que no devolvera nada entonces no vale la pena hacerlo recursivo pudiendo hacer que repita ese mensaje las veces que quieras en un bucle) la variable i quedara con ese valor esperando que se llegue a la base para despues que "suba" hasta la primer llamada seguir aumentando otra vez su valor haciendo repetir todo de nuevo, se te podrian generar miles de bucles sin sentido pero bueno, tu preguntaste xD


Para hacer uso de backtracking tendras que tener un metodo principal y otros que se encargaran de hacer un movimiento y verificar si es un movimiento valido.

Como resolverias el problema de las 8 reinas en un papel con lapicera? yo lo que hice fue poner una cruz en la primer posicion, alla abajo de todo en la izquierda, luego puse otra cruz en la siguiente columna pero tuve q ponerla 2 posiciones mas arriba para que no se crucen, no la puse mas de 2, solo lo minimo posible, lo mismo para la tercera y para las siguientes ya que sino se cruzaban. En la quinta columna comenze de nuevo desde abajo, la primera posicion no podia porque estaba ocupada por la primer cruz que hice, pero la segunda si asique puse una cruz ahi, luego en la sexta columna fui mirando si podia desde la posicion de abajo de todo hasta arriba hasta que encontre una que si, la septima lo mismo, siempre probando desde la posicion de abajo hasta arriba, pero ya la octaba columna no pude poner ninguna, asi que use el backtracking en mi cabeza y dije, borrare la ultima cruz que puse (dar un paso atras) y vere si tenia otro lugar donde ponerla sin perder, siempre siguiendo probando desde la posicion de abajo hacia arriba, para seguir un orden. Y no habia otra posicion asi que borre la anterior a esa tambien para buscar otro lugar para ponerla y tampoco, todo asi tienes que seguir hasta que encuentres una cruz que puedes cambiarla para poder empezar a avanzar otra vez y ver si llegas a una solucion, si no llegas vuelves de nuevo para atras de la misma forma, desde la ultima cruz hasta que puedas usar otra posicion nueva en alguna cruz para volver otra vez a avanzar xD

Si lo haces con papel y lapiz como te lo redacte entenderas como funciona. La cosa es que yo cuando estaba queriendo hacer uno de esos ejercicios, pero en vez de el de las reinas era el del caballo, esas posiciones que sabia que no iban a tener solucion las iba agregando en arrays para no pasar por ellas, pero era un caos total, si usas backtracking haciendo tu funcion principal recursiva, lograras hacerlo, trata de pensarlo bien y puedes dejar tu idea. Mucho papel y lapicera necesitaras para escribir codigos y algoritmos antes de empezar a programarlo. Saludos!
En línea

YeisonSoto

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Re: Algoritmia
« Respuesta #20 en: 1 Diciembre 2012, 02:44 »

Por las dudas te digo que yo no he entrado a la universidad por lo que algunas cosas no he aprendido aun, no se bien que es la prueba de escritorio, me podrias explicar si quieres.

Cuando el metodo es llamado recursivamente lo que hace ejecutar la funcion de nuevo pero los valores que tenia antes tomados en la funcion anterior quedan guardados en la memoria para que se usen luego. Es complicado explicarte porque para entender todo sin que te quedes con ninguna duda tendrias que aprender el lenguaje ASM para ver como funcionan los programas a nivel del procesador.

Pero por ahora solo te puedo dar un ejemplo de una funcion recursiva para que entiendas mejor.
La funcion para saber el factorial de un numero se puede hacer con un bucle, seguramente lo has hecho alguna vez, donde vas guardando la variable del numero y lo multiplicas por el numero anterior y a ese nuevo numero lo multiplicas por el anterior y todo asi, por ejemplo el factorial de 4 seria 4 * 3 * 2 * 1 y en tu programa harias un bucle con la variable i que vaya desde 4 a 1 donde vas guardando los resultados de las multiplicaciones y vas multiplicando por i hasta que i sea 1 o 2 total al multiplicar por 1 no cambia y se termina el bucle y la funcion.

Pero lo bueno de los metodos recursivos viene aca.. el factorial de 4 (llamemosle 4!) es igual a 4*3! no? y 3! (factorial de 3) se puede calcular 3 * 2! y 2! sabemos que es 2 * 1 que es 2. Entonces al usar un metodo recursivo la funcion solamente quedaria asi:

Factorial(n) {

if n=2 return 2; ' devuelve 2 y sale de la funcion

return n * Factorial(n - 1) ' como en el ejemplo si n es 4 entonces multiplica 4 por factorial de 3.

}

Entonces como se llama de nuevo en medio de la multiplicacion.. el return no sabe que devolver hasta que se termine la funcion Factorial que se envio como parametro el numero 3. Y vuelve el ciclo de nuevo, comprobando si n es igual a 2 y como no lo es se multiplica 3 * Factorial(2) ahora, porque n ya no es mas 4 ahora es 3, pero de nuevo el return "espera" el valor de Factorial(2) para devolver resultado a la multiplicacion. Pero en Factorial(2) ahora n vale 2 asi que devuelve 2 y ya se sabe el primer valor "base".
Asi que ahora que se llego a la base, vuelve todo para arriba poniendo los valores de los returns desde la base hasta el primero que se llamo, asi que Factorial(3) va a devolver como decia 3 * Factorial(2) que es 6. Y Factorial(4) va a devolver 4 * Factorial(3) que como Factorial(3) dio como resultado 6 entonces 4 * 6 es 24 y se termina la funcion.

Una vez que entiendas eso, que por cierto, te puse el codigo asi nomas, ya que no se PHP pero queria darte una mano de todas formas, podras entender mejor como poder hacer tu algoritmo de las 8 reinas usando Backtracking. Fijate que sin una condicion como la que hice de if n= 2 return 2; la funcion no funcionaria porque quedara buscando un valor continuamente y se generaria un bucle infinito que consumiria toda la ram.


Entonces ahora ponte a pensar que si haces una funcion recursiva donde la llamada a la misma funcion es dentro de un bucle casi no tiene sentido, ya que si haces que devuelva un valor la funcion dentro del for, solo devolvera un valor cuando recien comienza, cuando la variable i del bucle for vale 0. Por eso no sirve para eso, una funcion recursiva llamada dentro de un bucle no tendria significado, por lo menos que yo sepa, me puse a pensar en algun ejemplo y lo termine borrando porque no tenia logica asi que no vale la pena complicarse la vida pudiendolo hacer de otra forma.
Pero si es que sirve para algo, en alguna funcion que no devuelva nada, que se encargue de mostrar un mensaje talvez (por eso digo que no tiene sentido hacerlo asi ya que no devolvera nada entonces no vale la pena hacerlo recursivo pudiendo hacer que repita ese mensaje las veces que quieras en un bucle) la variable i quedara con ese valor esperando que se llegue a la base para despues que "suba" hasta la primer llamada seguir aumentando otra vez su valor haciendo repetir todo de nuevo, se te podrian generar miles de bucles sin sentido pero bueno, tu preguntaste xD


Para hacer uso de backtracking tendras que tener un metodo principal y otros que se encargaran de hacer un movimiento y verificar si es un movimiento valido.

Como resolverias el problema de las 8 reinas en un papel con lapicera? yo lo que hice fue poner una cruz en la primer posicion, alla abajo de todo en la izquierda, luego puse otra cruz en la siguiente columna pero tuve q ponerla 2 posiciones mas arriba para que no se crucen, no la puse mas de 2, solo lo minimo posible, lo mismo para la tercera y para las siguientes ya que sino se cruzaban. En la quinta columna comenze de nuevo desde abajo, la primera posicion no podia porque estaba ocupada por la primer cruz que hice, pero la segunda si asique puse una cruz ahi, luego en la sexta columna fui mirando si podia desde la posicion de abajo de todo hasta arriba hasta que encontre una que si, la septima lo mismo, siempre probando desde la posicion de abajo hasta arriba, pero ya la octaba columna no pude poner ninguna, asi que use el backtracking en mi cabeza y dije, borrare la ultima cruz que puse (dar un paso atras) y vere si tenia otro lugar donde ponerla sin perder, siempre siguiendo probando desde la posicion de abajo hacia arriba, para seguir un orden. Y no habia otra posicion asi que borre la anterior a esa tambien para buscar otro lugar para ponerla y tampoco, todo asi tienes que seguir hasta que encuentres una cruz que puedes cambiarla para poder empezar a avanzar otra vez y ver si llegas a una solucion, si no llegas vuelves de nuevo para atras de la misma forma, desde la ultima cruz hasta que puedas usar otra posicion nueva en alguna cruz para volver otra vez a avanzar xD

Si lo haces con papel y lapiz como te lo redacte entenderas como funciona. La cosa es que yo cuando estaba queriendo hacer uno de esos ejercicios, pero en vez de el de las reinas era el del caballo, esas posiciones que sabia que no iban a tener solucion las iba agregando en arrays para no pasar por ellas, pero era un caos total, si usas backtracking haciendo tu funcion principal recursiva, lograras hacerlo, trata de pensarlo bien y puedes dejar tu idea. Mucho papel y lapicera necesitaras para escribir codigos y algoritmos antes de empezar a programarlo. Saludos!

Muchas gracias, gracias a tu explicacion ahora  tengo la idea mucho  mas clara....

Pero  tengo  una ultima pregunta,  sabes como  puedo   medir la eficiencia de este algoritmo (Notacion asintotica)?




En línea

$Edu$


Desconectado Desconectado

Mensajes: 1.843



Ver Perfil
Re: Algoritmia
« Respuesta #21 en: 1 Diciembre 2012, 18:47 »

Ni idea, pero de la forma que te dije yo seria la mas lenta ya que hay otras formas para sacar mejores las soluciones, mejores algoritmos.
En línea

Páginas: 1 [2] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Algoritmia - Métodos para resolución de problemas
Programación General
Myth.ck 11 11,043 Último mensaje 20 Mayo 2009, 01:29
por Myth.ck
Problema con ejercicio de Algoritmia
Programación General
hasukronos 0 965 Último mensaje 11 Junio 2009, 23:47
por hasukronos
Algoritmia-Ejercicios introductorios. « 1 2 3 »
Ejercicios
h0oke 29 8,705 Último mensaje 4 Agosto 2009, 05:39
por Shadowofvilla
Subforo de Matematicas y Algoritmia
Sugerencias y dudas sobre el Foro
Nippa?! 1 1,777 Último mensaje 28 Febrero 2010, 13:43
por sirdarckcat
Ejercicio de algoritmia para c++
Programación C/C++
NRRR 1 1,001 Último mensaje 28 Septiembre 2011, 11:56
por skapunky
Powered by SMF 1.1.19 | SMF © 2006-2008, Simple Machines