← Volver a los ejercicios

El código en la posición k sin construir la lista

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:
rangokmitadmitad elegidabitnuevo rangonueva 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).