Skip to content

Solución: sin dos bits a uno

by en 23/03/2014

¡Hola!

Os pedimos disculpas por haber pasado una “semana en blanco” sin acertijo. Como muchos sabéis, el miércoles tuvo lugar el regional de Madrid de ProgramaMe, el concurso de programación para ciclos formativos, y no hemos tenido un momento libre.

¡Pero ya hemos vuelto! Empezamos hoy resolviendo el acertijo que os poníamos hace dos semanas. Estaba, como el anterior, relacionado con números binarios. En concreto, os preguntábamos cuántos números de 4, 10 y 24 bits no tienen una sucesión de dos bits a uno. jserra nos envió el código fuente para resolverlo pero… ¡esta vez no acertó! En el ejemplo que os poníamos, de 3 bits, salen 8 posibles combinaciones, y de esas 8, veíamos que había 5 que no tenía 2 bits consecutivos a 1. Sin embargo, la respuesta de jserra dice que hay… 12. ¡Eso son más que el número de combinaciones en primer lugar! Por tanto algo parece no funcionar…

Gualterio dio la respuesta a las tres preguntas que os hacíamos, del número de combinaciones de 4, 10 y 24 bits sin dos consecutivos a 1. Aseguró que son 8, 144 y 121393 y…. ¡acertó! Iván (¡bienvenido!, sí, deberías haber participado como profe :-p) nos dio su esbozo de la solución pero… parece que le falta el caso base 🙂 a si es que no está del todo claro si está bien o no.

Veamos nuestra solución. Ya os contábamos que lo interesante era conseguir dar la respuesta sin construir todos los números y analizar cada uno para ver si tenía o no dos bits a 1. Por tanto, hay que pensar un poco y tratar de construir los números válidos directamente.

Para eso, empezamos con un único bit. Las posibles combinaciones son 0 y 1, y ambas son válidas, pues ninguna tiene, obviamente, dos bits a 1.

Vamos con dos bits. Para eso, comenzamos con las posibilidades correctas de un único bit, y añadimos un segundo a la derecha:

  • A la configuración de un bit “0” podemos añadirle o bien un 0 o bien un 1 y seguirá siendo una combinación válida.
  • A la configuración de un bit “1” tenemos obligatoriamente que añadirle un 0. Si le añadiéramos un 1 tendríamos dos bits a 1 seguidos.

Vemos que con dos bits por tanto, tenemos tres configuraciones posibles, 00, 01 y 10.

Si damos el salto a tres bits:

  • A las configuraciones 00 y 10 podemos añadirle tanto un 0 como un 1 (recuerda que siempre añadimos por la derecha), y ambas serán configuraciones correctas.
  • A la configuración 01 sólo podemos añadirle un 0.

Por lo tanto, las configuraciones válidas son 000, 001, 100, 101 y 010, las 5 que anticipábamos en el enunciado.

La conclusión que debemos sacar de aquí es que lo importante para el siguiente paso (n+1 bits) es saber cuántas configuraciones válidas de n bits (paso anterior) acaban con 0 o con 1. Por cada configuración acabada en 0 tendremos dos configuraciones posibles de n+1 bits (la original, añadiendo por tanto un 0 y un 1). Por cada configuración acabada con 1 tendremos sólo una (la original, añadiendo un 0).

Además, pensando en los siguientes pasos, es importante recordar, de las nuevas configuraciones, cuántas acabarán en 0 y cuántas en 1. Dado que a las configuraciones de n bits acabadas en 0 las hemos añadido un 1, el número de configuraciones de n+1 bits acabadas en 1 será el de las acabadas en 0 con n bits. Por su parte, el número de configuraciones acabadas en 0 es la suma de las que había antes, pues a todas las configuraciones le podemos siempre añadir un 0.

Es decir:

configuracionesEn0(n+1) = configuraciones(n)
configuracionesEn1(n+1) = configuracionesEn0(n)
configuraciones(n) = configuracionesEn0(n+1) + configuracionesEn1(n+1)

Si nos pintamos una tabla:

# bits conf. en 0 conf. en 1 Conf. totales
1 1 1 2
2 2 1 3
3 3 2 5
4 5 3 8
5 8 5 13

¿Os suena? ¡¡Son los números de Fibonacci que ya han aparecido otras veces en nuestros acertijos!! Efectivamente, el número de combinaciones de n bits sin dos bits a 1 es el número de Fibonacci n-2 (asumiendo que empezamos la secuencia con 1, 1, 2, …). Curioso, ¿¡verdad!? 🙂

Como siempre, si programas tu solución puedes probarla aquí.

¡Hasta el próximo!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: