10 votos

Honesto y Engañosa de los Profesores Problema

He encontrado esto en Una Introducción a la Bioinformática Algoritmos. Yo he parafraseado para mayor claridad.

Hay 100 profesores. Algunos son honestos, mientras que otros son deshonestos. Hay más honesto profesores que son deshonestos. Honesto profesores siempre dicen la verdad, pero los deshonestos, a veces decir la verdad y a veces mienten. Usted puede pedir cualquier profesor la siguiente pregunta acerca de cualquier otro profesor, "el Profesor Y, es el Profesor X honesto?" a lo que él/ella va a responder sí o no. Diseñar un algoritmo que permite averiguar cuál de los profesores son honestos con no más de 198 preguntas.

La parte en negrita es el trampolín. Si los mentirosos siempre mintió, entonces el problema es trivial - pregunte a 99 personas acerca de un chico. La mayoría sería el veraz contestar, así que usted sabe que su honestos chicos y su mentirosos.

Así que, ¿algún consejo? Si te dan la respuesta por favor ponerlo en spoiler tags ya que estoy buscando la dirección.

8voto

Alex Bolotov Puntos 249

Spoiler

Al azar par de los profesores, para cada par de pedir tanto a los profesores, la opinión de cada uno de los otros. Elegir uno de cada uno de los pares que se traducen en la respuesta de (sincero, Honesto). Enjuague, Repita.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X