Autor Tema: Algoritmo para contar y escribir caminos

0 Usuarios y 1 Visitante están viendo este tema.

16 Junio, 2010, 06:36 pm
Leído 2492 veces

la_llorona

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 83
  • Karma: +0/-0
  • Sexo: Femenino
Hola, buenas tardes.

Tengo que hacer un algoritmo en Fortran 90 que escriba todos los posibles caminos para ir desde el (0,0) hasta un punto (m,n) donde todos los movimientos son de izquierda a derecha y de abajo hacia arriba.
Por ejemplo, para ir del (0,0) al (3,2) un camino sería XYXXY donde la X representa un movimiento a la derecha y la Y un movimineot hacia arriba.

Si me pudieran ayudar aunque sea con el pseudocódigo y yo luego lo paso a Fortran..

Muchísimas gracias!

Saludos.

16 Junio, 2010, 09:16 pm
Respuesta #1

Phicar

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 514
  • Karma: +1/-0
  • Sexo: Masculino
    • redinfocol.org
Hola, Como tas??..pos bueno primero dos cositas..

Primero, vas a tener palabras de descripcion de camino por lo cual se pueden tratar como tales :P..Por lo cual solo obtendras

\( \displaystyle\binom{n+m}{n} \)

numero de caminos posibles..

y lo puedes tratar con anagramas, la vaina es si es muy grande, por lo cual toca parametrizar esos anagramas...

por ejemplo si tienes de (0,0) hasta (4,5) tonces tendras que los caminos seran los anagramas de xxxxyyyyy...Para lo cual puedes usar recursion parametrizada con memoization....eso en cristiano es usar recursividad e ir guardando los anagramas para no repetirlos :P.

pd: Es lo que se me ocurre a mi, esperar a topo que a ese se le ocurren cosas mejores :)
redinfocol.org

17 Junio, 2010, 12:54 am
Respuesta #2

la_llorona

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 83
  • Karma: +0/-0
  • Sexo: Femenino
Hola!! Gracias por contestar.

Pero cómo hago esa recursividad? La verdad es que no se me ocurre..

También estaba pensando que si tomamos el 0 como la X y el 1 como las Y tenemos números binarios de m+n dígitos donde el 0 se repite m veces y la Y se repite n veces. Por ejemplo si m=4 y n=3 entonces tendría que generar todos los binarios desde el 0000111 hasta el 1110000 que tengan 3 unos y 4 ceros.
Empecé a hacerlo transformando todos los binarios desde esos dos números y verificando si la suma de 1 era igual a n y completando con ceros a la izquierda, pero queda muy largo y no me corrió a la final, son muchos números a transformar.

Alguien sabrá de una manera un poco más eficiente? Digamos para saber directamente en base decimal cuáles serán los números que cumplan con eso?

Muchísimas gracias!!!  :D

17 Junio, 2010, 02:01 am
Respuesta #3

Phicar

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 514
  • Karma: +1/-0
  • Sexo: Masculino
    • redinfocol.org
ve ta interesante tu metodo y pos lo tengo..perame a ver...

public class Foro{
public static void main(String args[]){//inicia el programa
int m = Integer.parseInt(args[0]);//por consola se le pasa m y n :)
int n = Integer.parseInt(args[1]);
System.out.println(ToDec(ToBin(m,n+m))+" "+ToDec(ToBin(n,n+m)));//esto era para probar que me funcionaran las funciones
String MAX = "";//el numero maximo en el caso de (3,2) sera 11100
String MIN ="";//el numero minimo en el caso de (3,2) sera 00111;
for(int p=0;p<m;p++){//siendo m los pasos a derecha los pongo como 1's
MIN+="1";
MAX+="1";
}
while(MAX.length()<(m+n))MAX+="0";//relleno con 0's la longitud que debe ser
while(MIN.length()<(m+n))MIN="0"+MIN;
int max = ToDec(MAX);
for(int x =ToDec(MIN);x<=max;x++)//recorro los numeros que estan en el intervalo
if(VerSi(x,m))System.out.println(ToBin(x,(m+n)));//si cumple la condicion los imprime
}
public static int ToDec(String a){//funcion que toma una cadena(binario) y la pasa a decimal
int tmp = 0;
for(int n = a.length()-1,c=0;n>-1;n--,c++)
tmp+=(a.charAt(n)-'0')*(Math.pow(2,c));
return tmp;
}
public static String ToBin(int a,int len){//funcion que toma un numero a lo pasa a binario y lo devuelve con longitud len
String tmp = "";
do{
tmp=(a&1)+""+tmp;
}while((a>>=1)>0);
while(tmp.length()<len)tmp="0"+tmp;
return tmp;
}
public static boolean VerSi(int b,int n){//funcion que cuenta los 1 y retorna si son los adecuados :)
int tmp = 0;
do{
tmp+=(b&1);
if(tmp>n)return false;
}while((b>>=1)>0);
return (tmp==n);
}
}

No se que tan dificil sea pasarlo a Foltran
pd2: Mi manera es un poco mas lenta con mas caracteres y mucho mas rapida con pocos caracteres :)

redinfocol.org

17 Junio, 2010, 02:03 am
Respuesta #4

la_llorona

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 83
  • Karma: +0/-0
  • Sexo: Femenino
 :o Odio C++!!   :laugh:

Pero muchas gracias!!! Veré si logro descifrarlo y pasarlo a Fortran.. Ya me veo buscando mis viejas guías del amigo C  :D

Muchas gracias igual!!  :)

17 Junio, 2010, 02:12 am
Respuesta #5

Phicar

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 514
  • Karma: +1/-0
  • Sexo: Masculino
    • redinfocol.org
jejejjejeje Es Java :D...te lo comentare ;)
redinfocol.org

17 Junio, 2010, 02:16 am
Respuesta #6

la_llorona

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 83
  • Karma: +0/-0
  • Sexo: Femenino
 :o :o :o

jaja te lo agradecería muchísimo!!! No conozco nada de Java  :'(

Gracias!!  ;)

25 Julio, 2010, 06:07 am
Respuesta #7

Daniel

  • $$\Large \color{red}\pi\,\pi\,\pi$$
  • Mensajes: 151
  • Karma: +0/-0
  • Sexo: Masculino
    • Worksheets Site
Esta es una forma, lenta, de hacerlo en LogoFE:
http://neoparaiso.com/logofe/

Código: [Seleccionar]
escribe dista [x y] [3 2]

[3 2] [x y]

escribe transpon [lista] dista [x y] [3 2]

[3 x] [2 y]

escribe transpon [clona lista] dista [x y] [3 2]

[x x x] [y y]

escribe junta transpon [clona lista] dista [x y] [3 2]

x x x y y

escribe expon [cuenta mismo] junta transpon [clona lista] dista [x y] [3 2]

5 [x x x y y]

escribe permuconj expon [cuenta mismo] junta transpon [clona lista] dista [x y] [3 2]

[x x x y y] [x x x y y] [x x y x y] [x x y y x] [x x y x y] [x x y y x] [x x x y y] [x x x y y] [x x y x y] [x x y y x] [x x y x y] [x x y y x] [x y x x y] [x y x y x] [x y x x y] [x y x y x] [x y y x x] [x y y x x] [x y x x y] [x y x y x] [x y x x y] [x y x y x] [x y y x x] [x y y x x] [x x x y y] [x x x y y] [x x y x y] [x x y y x] [x x y x y] [x x y y x] [x x x y y] [x x x y y] [x x y x y] [x x y y x] [x x y x y] [x x y y x] [x y x x y] [x y x y x] [x y x x y] [x y x y x] [x y y x x] [x y y x x] [x y x x y] [x y x y x] [x y x x y] [x y x y x] [x y y x x] [x y y x x] [x x x y y] [x x x y y] [x x y x y] [x x y y x] [x x y x y] [x x y y x] [x x x y y] [x x x y y] [x x y x y] [x x y y x] [x x y x y] [x x y y x] [x y x x y] [x y x y x] [x y x x y] [x y x y x] [x y y x x] [x y y x x] [x y x x y] [x y x y x] [x y x x y] [x y x y x] [x y y x x] [x y y x x] [y x x x y] [y x x y x] [y x x x y] [y x x y x] [y x y x x] [y x y x x] [y x x x y] [y x x y x] [y x x x y] [y x x y x] [y x y x x] [y x y x x] [y x x x y] [y x x y x] [y x x x y] [y x x y x] [y x y x x] [y x y x x] [y y x x x] [y y x x x] [y y x x x] [y y x x x] [y y x x x] [y y x x x] [y x x x y] [y x x y x] [y x x x y] [y x x y x] [y x y x x] [y x y x x] [y x x x y] [y x x y x] [y x x x y] [y x x y x] [y x y x x] [y x y x x] [y x x x y] [y x x y x] [y x x x y] [y x x y x] [y x y x x] [y x y x x] [y y x x x] [y y x x x] [y y x x x] [y y x x x] [y y x x x] [y y x x x]

escribe esencia permuconj expon [cuenta mismo] junta transpon [clona lista] dista [x y] [3 2]

[x x x y y] [x x y x y] [x x y y x] [x y x x y] [x y x y x] [x y y x x] [y x x x y] [y x x y x] [y x y x x] [y y x x x]

Así que el algoritmo es:

Código: [Seleccionar]
funciona "caminos [esencia permuconj expon [cuenta mismo] junta transpon [clona lista] dista [x y]]
Ejemplos:

Código: [Seleccionar]
escribe caminos [3 2]

[x x x y y] [x x y x y] [x x y y x] [x y x x y] [x y x y x] [x y y x x] [y x x x y] [y x x y x] [y x y x x] [y y x x x]

escribe caminos [2 2]

[x x y y] [x y x y] [x y y x] [y x x y] [y x y x] [y y x x]

escribe caminos [4 5]

[x x x x y y y y y] [x x x y x y y y y] [x x x y y x y y y] [x x x y y y x y y] [x x x y y y y x y] [x x x y y y y y x] [x x y x x y y y y] [x x y x y x y y y] [x x y x y y x y y] [x x y x y y y x y] [x x y x y y y y x] [x x y y x x y y y] [x x y y x y x y y] [x x y y x y y x y] [x x y y x y y y x] [x x y y y x x y y] [x x y y y x y x y] [x x y y y x y y x] [x x y y y y x x y] [x x y y y y x y x] [x x y y y y y x x] [x y x x x y y y y] [x y x x y x y y y] [x y x x y y x y y] [x y x x y y y x y] [x y x x y y y y x] [x y x y x x y y y] [x y x y x y x y y] [x y x y x y y x y] [x y x y x y y y x] [x y x y y x x y y] [x y x y y x y x y] [x y x y y x y y x] [x y x y y y x x y] [x y x y y y x y x] [x y x y y y y x x] [x y y x x x y y y] [x y y x x y x y y] [x y y x x y y x y] [x y y x x y y y x] [x y y x y x x y y] [x y y x y x y x y] [x y y x y x y y x] [x y y x y y x x y] [x y y x y y x y x] [x y y x y y y x x] [x y y y x x x y y] [x y y y x x y x y] [x y y y x x y y x] [x y y y x y x x y] [x y y y x y x y x] [x y y y x y y x x] [x y y y y x x x y] [x y y y y x x y x] [x y y y y x y x x] [x y y y y y x x x] [y x x x x y y y y] [y x x x y x y y y] [y x x x y y x y y] [y x x x y y y x y] [y x x x y y y y x] [y x x y x x y y y] [y x x y x y x y y] [y x x y x y y x y] [y x x y x y y y x] [y x x y y x x y y] [y x x y y x y x y] [y x x y y x y y x] [y x x y y y x x y] [y x x y y y x y x] [y x x y y y y x x] [y x y x x x y y y] [y x y x x y x y y] [y x y x x y y x y] [y x y x x y y y x] [y x y x y x x y y] [y x y x y x y x y] [y x y x y x y y x] [y x y x y y x x y] [y x y x y y x y x] [y x y x y y y x x] [y x y y x x x y y] [y x y y x x y x y] [y x y y x x y y x] [y x y y x y x x y] [y x y y x y x y x] [y x y y x y y x x] [y x y y y x x x y] [y x y y y x x y x] [y x y y y x y x x] [y x y y y y x x x] [y y x x x x y y y] [y y x x x y x y y] [y y x x x y y x y] [y y x x x y y y x] [y y x x y x x y y] [y y x x y x y x y] [y y x x y x y y x] [y y x x y y x x y] [y y x x y y x y x] [y y x x y y y x x] [y y x y x x x y y] [y y x y x x y x y] [y y x y x x y y x] [y y x y x y x x y] [y y x y x y x y x] [y y x y x y y x x] [y y x y y x x x y] [y y x y y x x y x] [y y x y y x y x x] [y y x y y y x x x] [y y y x x x x y y] [y y y x x x y x y] [y y y x x x y y x] [y y y x x y x x y] [y y y x x y x y x] [y y y x x y y x x] [y y y x y x x x y] [y y y x y x x y x] [y y y x y x y x x] [y y y x y y x x x] [y y y y x x x x y] [y y y y x x x y x] [y y y y x x y x x] [y y y y x y x x x] [y y y y y x x x x]