25 septiembre 2009

Floyd-Warshall

Después de mucho darle vueltas a un problema he descubierto cuál era el error. Escribí de cabeza el algoritmo de floyd-warshall y lo probé con un ejemplillo y funcionaba bien. Total, son 3 bucles y un if... Pues estaba mal.

Floyd-Warshall devuelve la matriz dist con la distancia mínima entre todas las parejas de nodos de un grafo.

Este es el algoritmo correcto:


for (k = 0; k < nnodes; k++) {
for (j = 0; j < nnodes; j++) {
for (i = 0; i < nnodes; i++) {
double d = dist[i][k] + dist[k][j];
if (d < dist[i][j])
dist[i][j] = d;
}
}
}


Yo había puesto el bucle exterior recorriendo la i y el interior la k y eso no da el resultado correcto.

En fin, he conseguido pasar al capítulo 3 de la USACO.

14 septiembre 2009

Libro: El Enigma de Fermat



Este ha sido uno de los mejores libros que he leído ultimamente. Cuenta la historia del Último teorema de Fermat y de cómo después de 3 siglos un hombre consiguió demostrarlo. No se mete nada en temas matemáticos complejos y pasa directamente a anécdotas y la historia. Tampoco creo que el autor pudiera meterse mucho en la demostración ya que pone que es un artículo de unas 200 páginas y si han tardado 3 siglos y medio de demostrarlo no debe ser sencillo...

12 septiembre 2009

Half Life Platinum Pack

El mes pasado cuando estaba jugando bastante al Team Fortress 2 se me ocurrió agregar en Steam el antiguo Half Life que tenía. Lo daban con el periódico El Mundo hace un porrón de años y yo me lo compré para poder jugar al Counter en su día.

Me sorprendió bastante porque al meter el cd-key del Half Life en el Steam me registró el "Half Life Platinum Pack" que incluye los siguientes juegos:

Half life
Opposing Force
Blue shift
Day of Defeat
Counter-strike
Team fortress classic
Deathmatch Classic
Half-life Deathmatch: source
Ricochet

Lo mejor son las 2 expansiones del HL: Blue Shift y Opposing Force que para mi gusto son mucho mejores que el propio juego.

Si alguien tiene el HL antiguo recomiendo que lo registre en Steam y juegue a las expansiones porque tienen mucha más historia que el HL. Cuando jugué al Half Life 2 en junio me sorprendió la cantidad de personas que había y resulta que todos son personajes de las extensiones.

Además de los juegos que aparecen para instalar con el Platinum Pack, si se accede a la dirección steam://install/150 podremos instalar el Counter Strike Steamworks. Que es una versión del Counter Strike clásico pero adaptada a los usuarios de Steam (implementa lo de los amigos y todo eso).