Rompecabezas | Adivina la string de bits

Rompecabezas: tu amigo piensa en una string de N bits que se referirá a ella como un código. La tarea es adivinar el código haciéndole a tu amigo una serie de consultas. En cada consulta, puede proporcionarle a su amigo una string de N bits de su elección, y su amigo le dirá la cantidad de bits en su string que coincide con los bits correspondientes en el código. Por ejemplo, si el código es 01011 y su string de consulta es 11001 , entonces la respuesta será tres porque las dos strings tienen los mismos bits en la segunda, tercera y quinta posición. Diseñe un algoritmo que pueda identificar cualquier código de N bits en no más de N consultas.

Solución:

• Sea la string de código binario de N bits b ₁ b ₂ ….b _n , se puede identificar mediante las siguientes N consultas:
  

  Consulta 1 – 000…00
  Consulta 2 – 100…00
  Consulta 3 – 110…00
  ………………
  ………………
  ………………
  Consulta N – 11….10

• La respuesta a la primera consulta , un ₁ , da el número total de ceros en la string de código que se está identificando. Sea un ₂ el resultado de la segunda pregunta.
• Dado que las strings de bits de consulta en las dos primeras preguntas difieren solo en un bit, por lo tanto, la cantidad de bits correctos en ellos también diferirá en uno, eso ayudará a identificar el primer bit b ₁ del código para nosotros de la siguiente manera:
  • Si un ₁ < un ₂ , b ₁ = 1
  • Si a ₁ > a ₂ , b ₁ = 0

  Por ejemplo, para el código 01011 , a1 = 2 y a2 = 1 , por lo tanto, b1 = 0 .

• La repetición del mismo argumento para los siguientes N – 2 bits de la string permite identificar los bits, b ₂ , …, b _{N – 1} del código.
• El último bit b _N se puede encontrar usando el número total de 0 en el código determinado por la primera consulta: si este número es igual al número de ceros en los primeros N – 1 bits del código , que ahora se conocen, entonces bn = 1 , si no bn = 0 .

Ejemplo: Sea N = 3 y el código que su amigo pensó que era “110”.
El código se puede adivinar en 3 consultas.

1. Consulta 1 = «000»: la respuesta a la consulta es 1, ya que solo el tercer bit coincide en la string «110» y «000» . La string de bits de código resultante tiene un total de 1 cero .
2. Consulta 2 = «100»: la respuesta a la consulta es 2 ya que solo hay coincidencias de dos bits en la string «100» y «110» . Dado que en esta consulta se cambia solo el primer bit de la última consulta y el bit de código resultante aumentó, el primer bit de la string de código será ‘1’ .
3. Consulta 3 = “110”: La respuesta a la consulta es como coincidencias de tres bits. Entonces, dado que cambiamos solo el primer bit de la última consulta y la respuesta aumentó, el segundo bit de la string de código será ‘1’.

De lo anterior, sabemos que dos de los bits son ‘1’ . Y tenemos 1 cero en la string de código, por lo que el tercer bit será un ‘0’. Por lo tanto, string de código = «110»