Hay n estudiantes en una clase, cada uno en posesión de un atributo de personalidad diferente. Como son nuevos en la escuela, quieren saber el uno del otro. Para ayudar a los alumnos, el profesor decide realizar una actividad. La regla para la actividad es que los estudiantes compartirán los atributos de personalidad de cada uno a través de una serie de conversaciones bilaterales (por ejemplo, por teléfono). Suponga que en cada conversación ambas partes intercambian todos los atributos de personalidad que conocen en ese momento. ¿Cuál es el número mínimo de conversaciones que necesitan para garantizar que todos obtengan todos los atributos de personalidad?
Solución:
Denotemos a los n estudiantes como S1, S2, S3, ………, Sn.
Cuando el Número de estudiantes (n) = 1, entonces el número de conversaciones requeridas es 0 ya que no es posible una conversación bilateral.
Para n = 2, el número de conversaciones requeridas es 1, es decir, entre S1 y S2.
Para n = 3, se necesitan tres conversaciones que son como (S1 con S2), (S2 con S3), (S1 con S3)).
Para n = 4, se necesitan cuatro conversaciones.
Para n = 5, se necesitan seis conversaciones.
Para n = 6, se necesitan ocho conversaciones.
Las cifras anteriores muestran el intercambio óptimo de atributos de personalidad a través de conversaciones bilaterales. El orden secuencial de las conversaciones está indicado por las etiquetas en los bordes que conectan los vértices, que representan a las partes conversando. El orden de las conversaciones puede variar.
La lógica se puede extender aún más a n = 7, 8 y así sucesivamente. Si se observa, se puede ver que el número total de conversaciones en este algoritmo es igual a 2(n – 4) + 4 = 2n – 4 donde n >= 4.
¿Cuál es la mejor manera de entablar conversaciones asegurando la minimalidad?
Para n > 4, la solución para n = 4 puede extenderse haciendo que cada uno de los estudiantes sea S5, S6, . . ., Sn habla con la persona S1 antes de que S1 hable con S2, S3 con S4, S1 con S4 y S2 con S3 y luego haciendo que S1 hable con cada uno de los estudiantes S5, S6, . . ., Sn por segunda vez.
Nota: El orden de las conversaciones puede variar, pero el número total de conversaciones mínimas seguirá siendo el mismo, lo que se puede ver claramente en las imágenes para n = 6.
Referencia: Rompecabezas algorítmicos – Anany Levitin, Maria Levitin
Publicación traducida automáticamente
Artículo escrito por bansal_rtk_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA