Foro de elhacker.net

Programación => Programación General => Mensaje iniciado por: AoX04 en 8 Enero 2012, 20:26 pm



Título: Algoritmia
Publicado por: AoX04 en 8 Enero 2012, 20:26 pm
Hey que tal buenas

Me preguntaba si en el foro ya existia una sección especifica en la cual se discuta algoritmia (Desarrollo y analisis de algoritmos).

He buscado pero no encuentro, tengo experiencia en el area y me gustaria aportar. Gracias.


Título: Re: Algoritmia
Publicado por: Aberroncho en 8 Enero 2012, 23:03 pm
Supongo que lo más parecido es "Programación general" :huh:


Título: Re: Algoritmia
Publicado por: leogtz en 9 Enero 2012, 02:48 am
Sí, aquí en esta sección está bien. :D


Título: Re: Algoritmia
Publicado por: [Case] en 9 Enero 2012, 02:51 am
Pero casi nadie postea sobre Algoritmos, y aunque yo no tengo mucho tiempo para estar contribuyendo, me gustaría de vez en cuando ver hilos sobre estos temas.


Título: Re: Algoritmia
Publicado por: Caster en 9 Enero 2012, 19:01 pm
Sería interesente ver más post sobre este tema, buena idea  :)


Título: Re: Algoritmia
Publicado por: Littlehorse en 9 Enero 2012, 21:17 pm
En esta sección puede ir perfectamente. Cualquier duda me avisas por pm.

Saludos!


Título: Re: Algoritmia
Publicado por: H1tchclock en 9 Enero 2012, 21:32 pm
Es una buena idea para los moderadores del foro, un subforo de ALGORITMIA... SUPER!!!


Título: Re: Algoritmia
Publicado por: AoX04 en 10 Enero 2012, 08:12 am
Un Sub foro de algoritmia me pareceria perfecto, tengo + o - 70 soluciones de problemas en projecteuler.net que me gustaria compartir, aparte de + o - 20 soluciones a problemas de spoj.pl...



Título: Re: Algoritmia
Publicado por: leogtz en 10 Enero 2012, 10:57 am
Sería muy interesante ver dichas soluciones, no dudes en compartirlas. :D


Título: Re: Algoritmia
Publicado por: [Case] en 10 Enero 2012, 17:13 pm
Un Sub foro de algoritmia me pareceria perfecto, tengo + o - 70 soluciones de problemas en projecteuler.net que me gustaria compartir, aparte de + o - 20 soluciones a problemas de spoj.pl...



Cuales son las de spot.pl que has resuelto?


Título: Re: Algoritmia
Publicado por: ghastlyX en 10 Enero 2012, 19:50 pm
A mi también me interesa mucho la algoritmia y de hecho cuando surge algún tema relacionado en el foro suelo intentar ayudar.

También tengo bastantes problemas de jueces online resueltos, especialmente de UVa, Codeforces, Timus, SGU y Live Archive y participo con mi universidad en el ICPC, además de a título individual en otros concursos como el Google Code Jam o en el mismo Codeforces.

Sin embargo, no veo mucha actividad del tema en el foro. No sé hasta qué punto sería útil un subforo si la gente no muestra demasiado interés por el tema.


Título: Re: Algoritmia
Publicado por: leogtz en 10 Enero 2012, 21:13 pm
@ghastlyX

Para fomentarnos el interés, creo que debemos ir de a poco, porque he visto que a veces ponen cosas algo avanzadas y ahí es cuando se nos va el interés, pero creo que a todos nos interesa la algoritmia, si tu escribieras algún artículo claro que lo leería.

Saludos.


Título: Algoritmia
Publicado por: alfonsofeo1 en 17 Enero 2012, 19:52 pm
Aquí hay un manual. Lo practiqué antes de darle de lleno a la programación en C.

http://www.mediafire.com/?v5dfqgmwr1gr1jf (http://www.mediafire.com/?v5dfqgmwr1gr1jf)


Título: Re: Algoritmia
Publicado por: H1tchclock en 7 Febrero 2012, 08:08 am
¿y el subforo de algoritmia?


Título: Re: Algoritmia
Publicado por: leogtz en 8 Febrero 2012, 04:52 am
¿y el subforo de algoritmia?

¿Y si lees el post entero?


Título: Re: Algoritmia
Publicado por: H1tchclock en 21 Febrero 2012, 22:05 pm
¿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


Título: Analisis Problema de las 8 reinas (Backtracking)
Publicado por: YeisonSoto en 29 Noviembre 2012, 05:19 am
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
(http://squadronsuicida.99k.org/Reinas/reinas.png)


  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 (http://squadronsuicida.99k.org/Reinas/Reinas.php).
Descarga http://squadronsuicida.99k.org/Reinas/Reinas.txt (http://squadronsuicida.99k.org/Reinas/Reinas.txt)

[-- --]


Prueba http://squadronsuicida.99k.org/Reinas/Reinas_Prueba.php (http://squadronsuicida.99k.org/Reinas/Reinas_Prueba.php).
Descarga http://squadronsuicida.99k.org/Reinas/Reinas_Prueba.txt (http://squadronsuicida.99k.org/Reinas/Reinas_Prueba.txt)


Título: Re: Algoritmia
Publicado por: $Edu$ en 29 Noviembre 2012, 16:04 pm
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?


Título: Re: Algoritmia
Publicado por: YeisonSoto en 29 Noviembre 2012, 17:13 pm
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....




Título: Re: Algoritmia
Publicado por: $Edu$ en 29 Noviembre 2012, 19:35 pm
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!


Título: Re: Algoritmia
Publicado por: YeisonSoto en 1 Diciembre 2012, 02:44 am
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)?






Título: Re: Algoritmia
Publicado por: $Edu$ en 1 Diciembre 2012, 18:47 pm
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.