3.13. Simulación: la patata caliente¶
Una de las aplicaciones típicas para mostrar una cola en acción es simular una situación real que requiere que los datos se gestionen de una manera FIFO. Para empezar, vamos a considerar el juego infantil de la patata caliente. En este juego los niños se alinean en un círculo y pasan un ítem de vecino a vecino lo más rápido que pueden. En un cierto punto del juego, la acción se detiene y el niño que tiene el ítem (la patata) es retirado del círculo. El juego continúa hasta que solo queda un niño.
Figura 2: Un juego de la patata caliente de seis personas¶
Figura 2: Un juego de la patata caliente de seis personas
Este juego es un equivalente moderno del famoso problema de Josefo. Con base en una leyenda sobre el famoso historiador del primer siglo Flavio Josefo, se cuenta que en la revuelta judía contra Roma, Josefo y 39 de sus camaradas se mantuvieron en contra de los romanos en una cueva. Con la derrota inminente, decidieron que preferirían morir antes que ser esclavos de los romanos. Se organizaron en un círculo. Un hombre fue designado como número uno, y procediendo en el sentido de las agujas del reloj mataron a cada séptimo hombre. Josefo, según la leyenda, era entre otras cosas un consumado matemático. Al instante descubrió dónde debía sentarse para ser el último en ser eliminado. Cuando llegó el momento, en lugar de suicidarse, se unió a los romanos. Usted puede encontrar muchas versiones diferentes de esta historia. Algunos cuentan cada tercer hombre y algunos permiten que el último hombre escape en un caballo. En cualquier caso, la idea es la misma.
Implementaremos una simulación general de la patata caliente. A nuestro programa se ingresará una lista de nombres y una constante, digamos “N”, que se usará para contar. El programa devolverá el nombre de la última persona que queda después del conteo repetitivo por N. Lo que suceda en ese momento depende de usted.
Para simular el círculo, usaremos una cola (ver la Figura 3). Suponga que el niño que sostiene la papata estará en el frente de la cola. Al pasar la patata, la simulación simplemente invocará el método avanzar y luego inmediatamente agregará a ese niño, poniéndolo al final de la cola. A continuación, esperará hasta que todos los demás hayan estado en el frente antes de que sea su turno nuevamente. Después de las N operaciones avanzar/agregar, el niño en el frente se quitará permanentemente y comenzará otro ciclo. Este proceso continuará hasta que sólo quede un nombre (hasta que el tamaño de la cola sea 1).
Figura 3: Implementación del juego de la patata caliente usando una cola¶
Figura 3: Implementación del juego de la patata caliente usando una cola
El programa se muestra en el ActiveCode 1. Una llamada a la función papaCaliente usando 7 como la constante de conteo devuelve Susan.
Note que en este ejemplo el valor de la constante de conteo es mayor que el número de nombres de la lista. Esto no es un problema ya que la cola actúa como un círculo y el conteo continúa de nuevo al principio hasta que se alcanza el valor. Además, observe que la lista se carga en la cola de manera que el primer nombre de la lista esté en el frente de la cola. Bill en este caso es el primer ítem de la lista y por lo tanto se mueve al frente de la cola. Una variación de esta implementación, descrita en los ejercicios, permite tener un conteo aleatorio.