2011-03-25 39 views
6

En un estadio pequeño hay varios miles de personas en las gradas. Diseñe un algoritmo distribuido que permita a la audiencia contar solo. No asuma ninguna geometría particular del estadio excepto, si lo desea, que tiene forma de cuenco. Indique explícitamente sus suposiciones, luego presente su algoritmo y análisisproblema del estadio: Proporcione un algoritmo para resolver el problema

Estaba asumiendo que los miembros son una lista enlazada y anexando el contador y libre (ptr) .. Puedo estar equivocado ... Por favor proporcione algunas ideas útiles

Gracias de adv ...

+0

¿Qué * específicamente * es su pregunta aquí? –

+0

qué algoritmo me ayudaría a resolver el problema anterior con min complejidad – garima

+0

No creo que sea posible en general. Por ejemplo, ¿qué ocurre si se trata de un estadio grande con solo 2 personas y no se encuentran dentro del radio de comunicación entre ellos? – mbeckish

Respuesta

11

Suponiendo que todo el mundo puede hablar con su/su vecina (posiblemente durante muchos asientos vacíos) y que los aficionados del equipo a están dispuestos a hablar con los aficionados del equipo B, el siguiente podría funcionar :

Todo el mundo agarra a su vecino más cercano, que ya no es capturado por otra persona, para formar grupos de como máximo dos personas. Ahora todos recuerdan el tamaño del grupo en el que se encuentran (puede ser 1 o 2). Ahora el líder de cada grupo se elige de forma que pueda comunicarse con un miembro de otro grupo. Los líderes de cada grupo intentan unirse a su grupo con otro y cada miembro de los dos grupos (ahora unidos) recuerda la suma de los miembros de cada grupo (esto se puede hacer transmitiendo el nuevo valor que se agregará al grupo) . Este proceso continúa hasta que solo queda un grupo. Al finalizar este proceso, todos conocen la cantidad de personas en el estadio.

Espero que esto ayude.

+0

muchas gracias ... – garima

+0

+1, su solución no necesita demasiada ruptura de simetría, y tampoco posibilidad de conteo duplicado. Puede modificar para permitir una estrategia de elección de líder. – CMR

2

Para cada columna, un líder se elige con la regla "la persona en la fila más cercana al campo es la líder" (estos asientos generalmente están llenos). El líder inicia un recuento de las personas en esa columna de la siguiente manera:
1. Agite la mano con la persona sentada directamente detrás y pregunte: "¿usted?"
2. Si no hay nadie detrás de la persona, la respuesta debe ser 1, o bien haga el paso 1 con la persona detrás, y la respuesta es una más que la respuesta de la persona detrás.
3. El líder escribe inmediatamente este número en un tablero, y lo sostiene
4. Entre estos líderes, la persona más joven debe comenzar a recoger estos tableros y agregarlos. Si se encuentra con una persona más joven que sus paneles colectores, la cuenta se entregará a la otra persona. Si tuviera la misma edad, la persona más alta tomaría el control.

3

En un estadio pequeño hay varias personas en las gradas. Diseñe un algoritmo distribuido que permite que el público se contabilice.

Feynman answer (vea round manhole question): Haga que todos griten "¡Varios miles!"

+0

+1, la respuesta está en la pregunta ... Clase de lo budista 'mu' – CMR

2
  • Todo el mundo deja caer sus dacks, y la "salida" está disponible en el periódico local al día siguiente ala "N personas arrestadas en el primer incidente de streaker masivo del mundo". (es decir, la aplicación le pide al sistema que haga el trabajo).
  • Cada persona elige a otra persona para pelear, y primero pregunta cuántas personas han noqueado. El ganador encuentra otro oponente, suma el conteo del oponente derrotado. El último hombre (o mujer) de pie tiene la respuesta.
  • Todos se ponen de pie, arrancan un cabello, luego se lo dan a alguien cercano con al menos tantos pelos antes de volver a sentarse. Las personas de pie continúan buscando a otros para darles pelos también.La última persona cuenta los pelos.
  • Invitas a la gente a agarrar una bolsa de minties de la cantimplora, luego les das la vuelta hasta que no puedan encontrar a nadie que no la haya tenido, y luego la dejas caer en un punto central. Multiplicar bolsas * cantidad de miniaturas por bolsa - cantidad de miniaturas-izquierda-en-bolsas.
+0

+1 para 'último hombre de pie'! – CMR

2

Aquí hay otro algoritmo:

  1. Que cada uno cuente los demás y consigo mismo.
  2. Luego, al sonido de un cuerno, cada contador grita su cuenta.
  3. Mantenga el mayor número de gritos.

Con este algoritmo puede hacer frente a los errores.

+0

Su solución podría funcionar, pero no parece distribuir la carga. – CMR

+0

Tienes razón. Este es un extremo de la computación paralela (o multi agentes en general): cada agente computa toda la tarea. Esto es extremadamente tolerante a fallas. El otro extremo es: cada agente escribe "+1" en un papel y le da este papel a un agente controlador. – Jason

Cuestiones relacionadas