El menor costo para adivinar un número entre 0 ~ 100

Question

Aquí está el problema. Hay un número elegido al azar entre 1~100. El jugador intenta adivinar que. Si la conjetura es mayor que cierto valor, el jugador es castigado por 'un' dólar. Si la conjetura es menor que cierto valor, el jugador es castigado por 'b' dólar. Cuánto dinero el juego debe prepararse con el fin de golpear el número en el peor de los casos? 1) a = 1, b = 1; 2) a = 2, b = 1; 3) a = 1.5, b = 1;

Aquí es donde yo estoy tan lejos. Para el primer sub-pregunta, el jugador podría usar árbol binario y el peor de los casos sería de 7 de adivinanzas veces (6 equivocado y 1 a la derecha). Por lo tanto, el castigar el dinero sería de 6*1 = 6 dólares. Para el segundo sub-pregunta, en lugar de separar el intervalo por la mitad, el jugador va a separar el rango de acuerdo a la importancia dada por a y b, es decir, en este caso el jugador elija 33 de la primera supongo que en lugar de 50. En esta estrategia, el peor de los casos, el costo sería el jugador 11 de dólares(según mis cálculos), mientras que el método binario, el costo sería el jugador 12 de dólares. A la tercera pregunta, la metodología es la misma que la segunda.

Mi duda es: ¿hay otro método que es mejor? La duda viene de este hecho: mi método aplicado mismo a la sub-pregunta 2 y sub-pregunta 3, que significa la existencia de sub-pregunta 3 no tiene sentido. Claramente el autor de un problema de no poner ese tipo de sub-pregunta.

apéndice: no estoy seguro de que el problema en el siguiente enlace dará algún indicio, pero que tienen algo en común. http://datagenetics.com/blog/july22012/index.html

Answer 1

La estrategia para la ampliación de los rangos deben ser para adivinar un número que es cierta proporción $p$ hacia abajo desde la parte superior de la gama actual. Para el caso de $2,$ le gustaría tener el mismo rango restante después de pasar $\$2,$ whether that comes from one high guess or two low ones. You guess low with probability $p$ and high with probability $1-p$. The chance of two low guesses in a row is $p^2.$ That means $p^2=1-p$, which says $p=\frac12(\sqrt 5-1) \aprox 0.618$ so your first guess should be $100-0.618*99$ or $39$. I would have to think some more about how the granularity of the numbers impacts this, but if $39$ is too high the second guess seems like it should be $ 38 - 0.618\cdot 37$ which is close to $15$. Then $6, 3, 1$ gets you there for $\$9$ si el objetivo es $2$. Os dejo el resto de los casos para que compruebe que usted no gaste más. Para el caso de $3$, la misma lógica dice que no importa si usted consigue tres puntos bajos o dos máximos, por lo $p^3=(1-p)^2$. Alfa resuelve esto exactamente, dando un lío que es acerca de $0.57$, de modo que su primer supongo que debe ser $100-0.57*99$ o $44$

Answer 2

Dado $n$ dólares, se puede resolver un intervalo sólo si podemos hacer una conjetura tal que el intervalo menor que la conjetura es solucionable con $n - a$ dólares y el intervalo mayor que la conjetura es solucionable con $n - b$ dólares. Por lo tanto, vamos a $f(n)$ ser el tamaño de la mayor intervalo de solucionable con $n$ dólares. Entonces tenemos

$$ f(n) = f(n - a) + f(n - b) + 1 $$

y el intervalo de $1$ $f(n)$puede ser resuelto con una estimación de $f(n - a) + 1$. El caso base es$f(n) = 0$$n < 0$. Esto puede ser fácilmente resuelto por el lado de los números en cuestión, o una técnica general para la resolución de recurrencias pueden ser aplicadas. En el caso 2, cada una de las $f(n)$ es uno menos que un número Fibonacci.