UVa 11173, Grey Codes, construye la lista reflejada de
códigos de n bits: se toma la lista de n - 1 bits, se le pega debajo su
reflejo, y se antepone un 0 a la mitad de arriba y un 1 a la de abajo. Pide
el código en la posición k. El enunciado está en
https://vjudge.net/problem/UVA-11173.
Aquí la lista se dibuja acostada: la mitad de arriba queda a la izquierda.
La función trabaja sobre el rango de posiciones [ini, fin) y en cada llamada
decide un bit.
1. n y k
n:k:
n va de 1 a 6 y k de 0 a 2n - 1. La primera
llamada es grey(0, 2n, k).
2. Baje por las mitades
Pila de llamadas, el tope arriba
(abiertas: 0)
el rango de la llamada
la posición que se busca
donde empieza la mitad derecha
bit:nuevo rango:nueva posición:
rango
k
mitad
mitad elegida
bit
nuevo rango
nueva posición
3. La recurrencia
Con m = fin - ini posiciones, una llamada hace un
trabajo constante c y una sola llamada sobre la mitad:
T(m) = T(m/2) + c, con T(1) = c. Niveles bajados:
0 de 0.
Con m = la expansión llega a
T(1) después de lg m = n niveles: T(m) = c·lg m + c, Θ(lg m), es decir
Θ(n). Construir la lista entera cuesta Θ(2n).
La comprobación
La lista entera de n bits, con la posición encima, el
código en binario y su valor debajo:
Hubo llamadas para n = :
una por bit y la del caso base.
El parámetro es el rango [ini, fin), que se
parte a la mitad en cada llamada. La propiedad es la construcción
misma: la mitad izquierda es la lista de n - 1 bits con un 0 delante y la
derecha es esa lista al revés con un 1 delante, de modo que la posición k
de la derecha corresponde a la posición mitad + fin - 1 - k en la lista sin
invertir. La trampa está en los límites: n llega a 30, así que la
lista tendría 230 códigos y no se puede construir; y hay hasta
250000 casos, de modo que cada uno tiene que salir en n pasos y la entrada
se lee completa de una vez.