¿Cuál es el mínimo número de movimientos para cambiar $a$ a $b$ doblando y reducir a la mitad?

Question

Se nos da enteros $a$$b$, y el deseo de cambiar $a$ $b$el uso de estas operaciones:

(1) Mapa de $a \mapsto \lfloor \frac{a}{2} \rfloor$. (Si $a$ es incluso, reemplácelo con $\frac{a}{2}$. Si $a$ es impar, reemplácelo con $\frac{a − 1}{2}$.)

(2) Mapa de $a \mapsto 2a$ (multiplicar $a$$2$).

¿Cuál es el menor número de operaciones necesarias para conseguir $a$ igual a $b$?

También, $\boldsymbol{b}$ es siempre una potencia de 2.

---

Ejemplos:

• $a = 3$, $b = 8$: la respuesta es $4$.

• $a=4$, $b=1$: la respuesta es $2$.

Answer 1

Escribir $a$ $b$ en sistema binario.

Tenga en cuenta que la operación (1) es para eliminar el último dígito binario, y la operación (2) es para añadir un cero al final.

Así, llegando a $b$ es posible si y sólo si $b$ $a$ comienzan con la misma cadena de $1$'s y $0$'s, y después de esta parte común, $b$ no tiene. Tenga en cuenta que no hay ninguna operación nos permite añadir.

El número de pasos, cuando sea posible, es el número de dígitos que necesitamos quitar de la $a$ más el número de ceros que ha $b$ después de la parte común.

Ejemplo: $a=55$, $b=104$.
En binario: $a=110101$, $b=1101000$. Vemos que la más larga posible de partida común de la cadena de es $11010$, de modo que eliminar el último dígito de $a$, es decir, hacemos la operación (1) una vez. Después de eso, se añaden dos ceros, es decir, hacemos la operación (2) dos veces. Esto hace tres pasos.

Ejemplo: $a=24$, $b=26$.
En binario: $a=11000$, $b=11010$. Este caso es imposible, porque después de la partida común de la cadena ($110$) el número de $b$ tiene uno.

EDIT: Este método se puede aplicar fácilmente en el caso particular de que $b$ es una potencia de dos. Bajo este supuesto, el algoritmo siempre funciona, ya que cualquier par de enteros positivos números común de partida de la cadena cuando se escribe en binario (es decir,$1$) y $b$ sólo tiene ceros después de esta partida.

Answer 2

Hay algunos casos en los que no se puede cambiar la $a$ a $b$ a todos; por ejemplo, $a = 3$ no puede ser cambiado en $b = 5$.

En general, escribir $a$ en binario: $a = a_0 a_1 a_2 \ldots a_k $ donde $a_i \in \{0,1\}$. También escribo $b$ en binario: $b = b_0 b_1 b_2 \ldots b_l$, $b_i \in \{0,1\}$. Entonces:

• El mapa de $a \mapsto \lfloor \frac{a}{2} \rfloor$ elimina el último dígito de la $a$.

• El mapa de $a \mapsto 2a$ agrega un cero al final de la $a$.

Ahora, vamos a $\boldsymbol{i}$ ser el mayor índice tal que $\boldsymbol{b_0 b_1 b_2 \ldots b_i}$ es un segmento inicial de $\boldsymbol{a}$. En particular, $0 \le i \le \min(k,l)$. Tenemos los siguientes casos:

1. Supongamos que $b_{i+1}, b_{i+2}, \ldots, b_l$ no son todos cero. Entonces es imposible cambiar a $a$ a $b$ por cualquier secuencia de movimientos.

2. Supongamos que en el otro lado que $b_{i+1}, b_{i+2}, \ldots, b_l$ son todos ceros. Entonces es posible, y lo mejor que podemos hacer para transformar $a$ a $b$ es para quitar las cosas de la final de la $a$ (hacer la mudanza $a \mapsto \lfloor \frac{a}{2} \rfloor$) hasta que llegamos $b_0 b_1 b_2 \ldots b_i$, y, a continuación, agregar ceros al final (hacer el movimiento $a \mapsto 2a$) hasta que llegamos $b$. Por lo que el menor número de movimientos está dada por $$ \underbrace{(k - i)}_{\text{dígitos eliminado de la final de la $a$}} + \underbrace{(l - i)}_{\text{ceros anexa el resultado para llegar a $b$}} = k + l - 2i. $$

Answer 3

No tiene sentido realizar un doble seguido por reducir a la mitad, debido a que este deja de donde empezó. Así que reducir a la mitad el $a$ hasta es una potencia de dos; a continuación, el doble o la mitad el resultado hasta que es igual a $b$.