Blogaritmo natural

Una muestra de las delicias campesinas.

El blog se ha unido al programa de Zync.es. La idea detrás de este asunto es encontrar bloggers que escriban una revisión sobre un producto o sitio, y a cambio de eso reciben dinero.

De modo que si deseas obtener una revisión en este blog, puedes hacerlo entrando al siguiente enlace:

En una entrada anterior prometí publicar la solución al problema 291 - The House of Santa Claus. Aquí está:

El problema

Teniendo el siguiente grafo, el problema consiste en encontrar todos los caminos posibles en que se pueden recorrer todas las aristas del grafo una única vez, partiendo de la esquina inferior izquierda. Esto en matemática de grafos es conocido cómo un camino de Euler.

 El grafo

Cada nodo está numerado como se muestra en la figura y cada arista es bidireccional, es decir, se puede ir del nodo 1 al 5 si y sólo si se puede ir del nodo 5 al 1.

 La solución

El algoritmo que se me ocurrió para solucionar el problema fue crear una función recursiva que se llamara cada vez que se visite un nodo, y que a su vez vuelva a llamarse con los próximos nodos a visitar, usando cómo parámetro la lista de los nodos ya visitados en el orden de visita. Me explico: la primera vez la función se llamará con los nodos visitados, es decir, [1], y se llamará a ella misma para cada nodo que sea posible visitar a partir del nodo actual. En nuestro caso, la llamada anterior llamará a la misma función 3 veces: una para cada posible siguiente nodo, a saber, se llamará nuevamente con los parámetros [12], [13], [15]. Puede verse que si se tiene la lista de nodos visitados en el orden de visita, se sabrá que aristas ya han sido visitadadas. Por ejemplo, para saber si ya se visitó la arista que conecta los nodos 4 y 5, bastará con fijarse si en la lista están dichos números en posiciones adyacentes. De esta manera, la llamada recursiva de la función sólo se generará sobre los nodos destino a los que sea posible visitar (o sea que no se repita arista). La recursividad se detendrá o bien cuando no es posible moverse a otro nodo sin repetir arista o bien cuando se han recorrido 8 aristas.

La implementación

Mi solución está escrita en C++.

Read more »

Buenísima canción de uno de mis grupos preferidos, el Cuarteto de Nos.

(Se necesita Macromedia Flash para escucharla).

Si no puedes escuchar la canción, por favor deja un comentario!

Otras canciones anteriores:

• Aphex Twin - Window Licker

Habla sobre la web y aparecerás en ella es una campaña iniciada por la web de DragoN. Consiste en escribir un pequeño post sobre dicha página para ganarse un enlace. Esta web es un portal bastante completo que lleva ya varios años en la red. Trata temas especialmente relacionados con internet y computación y tiene un foro muy activo. Es actualizada con mucha frecuencia, recomendada por su gran cantidad de artículos y noticias interesantes.