Cambalache 3,14 - La vidriera irrespetuosa

Uisssssssss, justo cuando iba a clicar en enviar, he leido la ultima frase...

Pues nada, no respondo...

¿?

¿y la mentira?

Aunque lo primero que pensé fue algo parecido a #2, diría que el número de preguntas necesarias para adivinar la respuesta es 1 (ya que, teóricamente sería posible acertar por pura suerte, y el enunciado no lo descarta), y el número mínimo si el que pensó el número puede mentir una vez es dos (una para la mentira y la otra, preguntando por el mismo número, en un nuevo alarde de suerte, a la cual no puede mentir de nuevo). En cualquier caso, parece que el número de posibles respuestas no influiría en el número mínimo de preguntas, sino en la probabilidad estadística de que se dé ese afortunado éxito.

¿Gallifante? :P Prometo que no sé si he respondido correctamente.

Pero tú has respondido a cuantas preguntas son posibles (mejor caso) no a cuantas necesita (peor caso).

Malambo: te he borrado el comentario porque habías reventao la platilla de la página.

¿Algun <div> de menos?

*plantilla

No, había sido un inocente link a:

http://zifra.blogalia.com/historias/43959

:)

Bueno si usamos el algoritmo de busqueda binaria ( creo que asi se llamaba... ) jajajja no digo nada mejor que si no me linchan :)

A ver mita y mita de la mita y la mita y despues la siguiente mita no me sale la mita por que la tengo desconchavadita X'D ya ya le me callo ese estuvo fatal

No, si la primera parte está cara. Pero ¿y si miente?

¿Se puede usar recursividad?

sips

A ver, sin mentiras son lg base2 de n preguntas y con una mentira, de media, salen
(1+2+...+n)/n + (log base2 de n)

El primer sumando se podrá simplificar seguramente, pero para ser sábado por la mañana ya he pensado bastante.

Si esa es la respuesta explico el razonamiento, si no lo es, no lo explico ;P

¿de media?

queremos el peor caso

El peor caso sería preguntar dos veces cada pregunta.
Es decir:
-¿Es menor que n/2?
-Sí.
-¿Es menor que n/2? (por si había mentido)
etc.

El peor caso es que mienta sólo al final o que no mienta con lo que tendríamos el doble de preguntas que en el caso en que no se pueda mentir, es decir: 2 log base 2 de n.

En mi respuesta anterior intentaba promediar el hecho de que puede mentir en la primera pregunta, o en la segunda o.... hasta la última.

¿Hay algún método más eficiente que repetir las preguntas?

Sí

Creo :)

A ver cómo nos portamos los de letra.
¿Se trata de usar recursividad, no?
Parto de que se use el algoritmo de búsqueda binaria.
La captura de la respuesta se puede hacer con preguntas de validación tipo "¿en qué punto has mentido?".

Llamemos n el número máximo de preguntas necesario en caso de no mentir y m al ordinal de preguntas de validación. ¿Es el punto óptimo de intercalación de las preguntas de validación es n/2^m? O sea, la primera pregunta de validación se produce en n/2, la segunda a n/4, etc.

En ese caso el número de preguntas sería.
{Log base 2 de (log base 2 de n)}+{log base 2 de n)
(Recordad que soy de letras, no me pidáis que simplifique la expresión)
¿Hay gallifante?

Vas bien, pero pienso que es mejorable. Me parecen que son demasiadas preguntas de validación :)

Después de la última pregunta, la que te da la solución, ya no hace falta hacer validación.
Por cierto es una pena usar sólo si/no. Si pudieses utilizar una característica y comparación la solución aparecería más rápido. Ejemplo en un acertijo popular: Tienes 9 perlas, una de ellas es falsa y se nota porque pesa menos. ¿Cuántas mediciones tienes que hacer en una balanza de platillos para encontrar la falsa? Eso va más rápido que el algoritmo de búsqueda binaria.

Va a ser que no.

Pero ¿y si miente?

Eha eso no es valido, esa es de cabrones y asi yo no me llevo, encima que hay que adivinarle el numero puede que me mienta :P

¿que tal si me miente?
anda tu...
¿Que tal si le meto una golpiza si llego al millon y sale que no?

Ademas recordemos la propiedad de densidad ( creo que va asi... ) un numero entre 1 y un millon podria ser un 3.1415... y entonces de que me sirve, las posibilidades son infinitas, pero ese seria el peor caso, el mejor seria que solo pensara en enteros...

un número entero, hombre.

No se me ocurre como solucionar eso. Mi idea va por establecer preguntas de control cruzadas, tipo CRC, que permitan reconstruir la información a partir del punto en el que se descubra el error. Pero no se me ocurre un algoritmo que optimice eso.

A ver si anda esto:

Supongamos que el número elegido es el 37.

Caso 1
...
¿

bué. Juro que esta vez no he hecho nada, sólo texto puro... ah! y el símbolo 'menor'!

Número elegido: 37

Caso 1
...
¿menor igual 50?
Sí
¿me has mentido?
Sí
¿menor igual 50?
Sí
... (no hace falta seguir preguntando si ha mentido)


Caso 2
...
¿menor igual 50?
No
¿me has mentido?
Sí
¿menor igual 50?
Sí
... (no hace falta seguir preguntando si ha mentido)

Lo lamento, no puedo responder cuántas preguntas hacen falta. El procedimiento depende de cuándo el otro decide mentir. Esperemos que suba sin error. (Al menos no he reventado la plantilla.)