14 marzo 2008

1031tensai revival (II)

Imagen de Porphyria Poppins bajo una licencia Creative Commons
Un poco de autobombo no hace daño...

Entradas revisadas:
  • Elemental querido Watson Muchos personajes tienen citas o frases famosas que nunca llegaron a decir o escribir. Groucho Marx no tiene en su tumba el epitafio "Perdone señora que no me levante"
  • Nosotros el PCI y McDOnalds Cuando escribí esta entrada había ido a un McDonalds hacia poco me fije en la tabla de calorías que tienen en su mantel, esperando ver una burrada de calorías, pero en ese momento estaba cursando técnicas energéticas y estaba acostumbrado a ver valores energéticos mucho más altos (para mantener una vivienda normal necesitas la energía de 100 personas, para un coche de 120CV la de 882 personas)... me encanta hacer conversiones de estas :D
  • Caete siete veces, levantate ocho Cuando el Liverpool jugó la final de la Champions Leage "iba" con ellos, supongo que porque en el equipo hay muchos jugadores de aquí, disfruté muchísimo de esa final y este vídeo, la verdad, levanta el ánimo (al menos a mi)

08 marzo 2008

¿A que no adivinas que número estoy pensando?

Foto de MetalPhoeniX bajo una licencia Creative Commons
Mi novia y yo estábamos jugando con los sobrinos a adivinar que número estaba pensando la otra persona. Para los que no hayan jugado nunca se trata de que A diga un número y si no acierta B le dice si el número pensado es mayor o menor.

Jugábamos con números del 1 al 10 o si queríamos que la partida se alargase del 1 al 100, en este último caso acababan usando un montón de intentos (incluso repetían números que no se acordaban que habían dicho). En eso que les aseguré que era capaz de adivinar cualquier número del 1 al 10.000 en 20 intentos máximo. La primera vez lo hice en 12 cosa que atribuyeron a la suerte, la segunda en 14 (creo)... jajaja, bueno los niños son un publico fácil, al menos en esto.

El método no es muy difícil, es ir reduciendo el número de candidatos a la mitad cada vez. Por ejemplo
-5.000
-menos
-2.500
-menos
-1.250
-mas
(etc)

Lo que no es tan inmediato es saber cuantos intentos se necesitan de antemano como máximo. Para calcular el numero de intentos se hace el logaritmo base 2 del número de candidatos. De esta manera el número de intentos necesarios en nuestro caso es log210.000 = 13,29 intentos. Para hacerlo de cabeza contáis el número de ceros (4 en nuestro caso) y lo multiplicáis por 3, os quedará un número aproximado a la baja. Por ejemplo si el rango es de 1 a 1.000.000 es aprox 6x3=18 (en realidad 20).

Todo esto se utiliza bastante en programación en búsquedas en listas ordenadas. En realidad la mayoría de nosotros lo ha hecho, porque de las miles de personas que aparecen en la guía telefónica apenas tardamos 1 minuto en dar con el que buscamos, o con las miles de entradas que tiene un diccionario. Pensemos como lo hacemos, buscamos la palabra "pereza" abrimos el diccionario por un poco más de la mitad, nos aparece "muerte" como "muerte" va antes que pereza nos olvidamos de todas las palabras que hay antes de muerte (acabamos de reducir la búsqueda a la mitad), ahora buscamos en la mitad de las páginas que nos quedan, aparece "pardo" (uy, ya casi estamos) etc. Si nos fijamos lo que hacemos es ir acotando la búsqueda, no haciendo una exhaustiva.

Pero sólo lo podemos hacer con listas ordenadas. Si el diccionario no siguiese ningún orden preestablecido (o no lo conociésemos nosotros), estaríamos obligados a hacer una búsqueda exhaustiva, es decir, ir mirando una por una todas las palabras. ¿Como se busca en un diccionario chino? jejeje