Título: Formula o algoritmo??? Publicado por: TomaSs en 29 Mayo 2012, 18:55 pm Alguien sabría decirme si habría alguna fórmula o algoritmo para poder sacar la fila en la que te encuentras en cada momento?
Me explico, suponiendo que conocemos el número total de filas, que conocemos el número de nodo en el que nos encontramos, y el número de columna a la que pertenece dicho nodo, ¿habría algún algoritmo o fórmula para poder sacar la fila en la que se encuentra dicho nodo? Teniendo en cuenta que el árbol podría tener infinitas ramas, no únicamente los dos casos que muestro Yo creo que algo se podrá hacer, pero le he dao mil vueltas y nada... (http://oi49.tinypic.com/11sdp50.jpg)(http://oi45.tinypic.com/2vcz620.jpg) Título: Re: Formula o algoritmo??? Publicado por: $Edu$ en 29 Mayo 2012, 19:22 pm Te refieres a hallar la fila donde se encuentra el circulo con el numero 2 por ejemplo? esque no he aprendido todo eso, pero me aburro mucho y podria probar alguna forma de sacarlo si me aclaras eso, antes de que empieze a pensar al pedo xD
Título: Re: Formula o algoritmo??? Publicado por: $Edu$ en 29 Mayo 2012, 19:35 pm Tu segunda imagen tendria que estar mal no? solo la recortaste, pero entonces queda mal porque falta el 3.
Despues la distribucion de la rama no se como se hace, si es asi siempre eso o que, si me explicas eso te ayudo Título: Re: Formula o algoritmo??? Publicado por: TomaSs en 29 Mayo 2012, 19:39 pm cierto! está mal, porque la recorte si... bien visto! ;)
Pues me refiero a hallar la fila de cualquier nodo, es decir, busco una fórmula o algoritmo genérico para hallar cualquiera Título: Re: Formula o algoritmo??? Publicado por: TomaSs en 29 Mayo 2012, 19:45 pm cabe decir que no se si tendrá alguna solución, ya que es algo que me ha surgido para hacer un programilla que estoy haciendo, no es que sea el enunciado de ningún ejercicio hecho. Pero creo que si puede tener un algoritmo genérico
Título: Re: Formula o algoritmo??? Publicado por: $Edu$ en 29 Mayo 2012, 19:45 pm Pero es que yo no se bien sobre eso, pero como estoy aburrido puedo pensar algun algoritmo si me explicas.
Por ejemplo.. no me contestaste mi primer pregunta, lo de si un nodo es el numero del circulito. Y por ejemplo, la distribucion de esos nodos, si es asi lo que es, quien dice como va? eso tambien cambiara? Tu pones el primer circulo en la posicion 0,0 y el otro en la posicion 1,1, pero el siguiente (el del numero 2) lo pones en 2,3 . Por eso no se si eso cambiara y la formula tendra que partir de esa distribucion o que? explicame y te ayudo :P Título: Re: Formula o algoritmo??? Publicado por: 79137913 en 29 Mayo 2012, 19:49 pm HOLA!!!
Al fin un algoritmo complicado! me pongo a verlo! GRACIAS POR LEER!!! Título: Re: Formula o algoritmo??? Publicado por: $Edu$ en 29 Mayo 2012, 19:51 pm Espera! no empezes, cuando me explique mis dudas, empeza a ver quien lo termina primero jeje
Título: Re: Formula o algoritmo??? Publicado por: TomaSs en 29 Mayo 2012, 19:54 pm Mi idea es pasar el árbol (sea del tamaño que sea) a filas ordenadas, pero como puedes ver, el arbol está ordenado en otro orden (el cual puedes ver siguiendo la numeración de los nodos).
De manera que yo obtendría, para el arbol grande, las siguientes filas: -->0 -->1 -->4 -->2 -->5 -->6 -->7 -->3 -->8 -->9 -->11 -->10 -->12 -->13 -->14 Para lo cual debo sacar un algoritmo que me devuelva la fila, según el nodo. Entiendes? Título: Re: Formula o algoritmo??? Publicado por: $Edu$ en 29 Mayo 2012, 20:00 pm Contestame todas mis preguntas, no otra cosa que yo no he hecho esto nunca
Título: Re: Formula o algoritmo??? Publicado por: TomaSs en 29 Mayo 2012, 20:03 pm Pues la distribución siempre va a ser la misma, no se que más quieres que te explique jeje
Es decir, siempre va a seguir este esquema: http://oi47.tinypic.com/2dwcnes.jpg teniendo en cuenta que siempre los nodos de la columna 0 van a ser potencias de 2, es decir, 2, 4, 8, 16, etc, pero el recorrido del arbol siempre se hará como en esta última foto Título: Re: Formula o algoritmo??? Publicado por: $Edu$ en 29 Mayo 2012, 20:08 pm Bueno veo a ver si puedo, sino alguien lo hara
Título: Re: Formula o algoritmo??? Publicado por: 79137913 en 29 Mayo 2012, 21:07 pm HOLA!!!
Mañana posteo. GRACIAS POR LEER!!! Título: Re: Formula o algoritmo??? Publicado por: TomaSs en 29 Mayo 2012, 22:55 pm Bueno pues aquí va algo que he pensado, eso si, muy enrevesado... xddd
Es a nivel de programación, ya que algo a nivel matemático no he sido capaz de sacar. • Tenemos el número total de filas: numFilas • Dividimos dicho número de filas entre 2 para sacar el número de nodos de la columna 0: nodosCol0 = numFilas/2 • Calculamos el logaritmo en base 2 de nodosCol0 para sacar el número de columnas: numCol = log(nodosCol0)/log(2) • Creamos una matríz [numCol X nodosCol0] que albergue por cada columna, los números de nodo que le pertenecen: Recorremos el arbol de la manera que hay que recorrerlo, desde el nodo 0--> http://oi47.tinypic.com/2dwcnes.jpg Puesto que para cada nodo conocemos su columna almacenamos cada uno en su registro de la matríz correspondiente, quedando la matríz de esta manera una vez recorrido todo el arbol: Col0-->0, 4, 5, 7, 8, 11, 12, 14 Col1-->1, 6, 9, 13 Col2-->2, 10 Col3-->3 • Recorremos la matríz para sacar las filas de los nodos que contiene (suponiendo que la matríz comienza en 0): Obtenemos un multiplicador (multi) que, multiplicado por la posición de los nodos en la matríz, nos devolverá la fila que ocupa dicho nodo. De esta manera iremos almacenando las filas de cada nodo en un array, el cual contendrá todos los nodos ordenados por filas y no según el orden indicado inicialmente. for(p=0; p<=numCol; p++){ multi = 2^(p+1); for(j=0; j<nodosCol0; j++){ fila = j * multi + sumatorio(p); array[fila] = matriz[p][j]; } } • El array que obtendremos para el caso del árbol grande que he puesto en la foto sería el siguiente, es decir el orden "por filas" de los nodos: [0, 1, 4, 2, 5, 6, 7, 3, 8, 9, 11, 10, 12, 13, 14] Título: Re: Formula o algoritmo??? Publicado por: TomaSs en 30 Mayo 2012, 13:37 pm ¿Como lo veis? a ver si alguien podría aportar algo más matemático, en caso de que fuera posible ;)
Título: Re: Formula o algoritmo??? Publicado por: 79137913 en 30 Mayo 2012, 13:53 pm HOLA!!!
Hola, por metodos matematicos no pude resolver el problema (lamentable)... Pero hice un codigo para que diseñe el arbol por si a alguien le sirve. Código
GRACIAS POR LEER!!! Título: Re: Formula o algoritmo??? Publicado por: TomaSs en 30 Mayo 2012, 17:20 pm pero por lo que puedo ver, ahí no usas para nada el número de nodo que busca, el m, es porque al final solo hiciste que diseñara el arbol en vez de buscar su fila, no?
de todos modos, no es mal trabajo, aunque me cuesta un poco verlo con tanto bucle anidado haha Título: Re: Formula o algoritmo??? Publicado por: 79137913 en 30 Mayo 2012, 17:52 pm HOLA!!!
Mi idea era diseñar el arbol y luego recorrer la matriz de alguna manera y numerar los nodos, luego simplemente buscar el nodo nro sin requerir la columna. Aunque con la manera que hago los nodos te puedo decir las filas de los nodos correspondientes a una columna. GRACIAS POR LEER!!! Título: Re: Formula o algoritmo??? Publicado por: $Edu$ en 31 Mayo 2012, 17:54 pm Capas que hay alguna formula para hallarlos, seguramente si, pero si sos vos el que haces esa matriz, es facil recorrerla para saber cual es la fila, asi como dijo 79137913.
Es decir, si tenes una matriz [n][m], lo que haces es recorrer cada elemento hasta encontrar el nodo y ahi mostrar el valor de m y sera la fila. No vale la pena pensar una formula si lo podes hacer asi de facil. Título: Re: Formula o algoritmo??? Publicado por: AgnesBlack en 23 Julio 2012, 15:28 pm tarde respondo el mensaje y si hay un metodo es usando el metodo el Binary tree sort o el de busqueda con puntero te dejo un ejemplo de uno que hice principio de año
este es con busqueda de puntero que es lo mas eficiente y rapido para buscar dicho nodo que buscas Código: unit uabb2; ah traves de esto podes modificarlo para buscar el nodo que quieras y eliminarlo |