6
votes

Problème de stade: fournir un algorithme pour résoudre le problème

dans un petit stade, il y a plusieurs milliers de personnes dans les stands. Concevoir un algorithme distribué permettant au public de se compter. Ne présumez pas une géométrie particulière du stade, sauf si vous voulez, que c'est en forme de bol. Indiquez explicitement vos hypothèses, puis présentez votre algorithme et votre analyse

J'avais supposé que les membres soient une liste liée et à ajouter le compteur et gratuitement (PTR). Je me trompe peut-être ... offrez-vous à des idées utiles

merci à ...

c algorithm puzzle

3 commentaires

Qu'est-ce que spécialement est votre question ici?

Quel algorithme m'aiderait-il à résoudre le problème ci-dessus avec la complexité min

Je ne pense pas que cela soit possible en général. Par exemple, et si c'est un grand stade avec seulement 2 personnes, et ils ne sont pas dans la plage de communication les uns des autres?

5 Réponses :

11
votes

En supposant que tout le monde puisse parler à son voisin (éventuellement sur de nombreux sièges vides) et que les fans d'équipe A sont disposés à parler aux fans de l'équipe B, ce qui suit pourrait fonctionner:
Tout le monde attrape son voisin le plus proche, qui n'est pas déjà attrapé par quelqu'un d'autre, de former des groupes d'au plus deux personnes. Maintenant, tout le monde se souvient de la taille du groupe dans lequel ils se trouvent (peuvent être 1 ou 2). Maintenant qu'un chef de chaque groupe est choisi de manière à pouvoir communiquer à un membre d'un autre groupe. Les dirigeants de chaque groupe tentent de rejoindre leur groupe avec un autre et chaque membre des deux groupes (maintenant rejoints) se souvient de la somme des membres de chaque groupe (cela peut être fait en diffusant la nouvelle valeur à ajouter au groupe) . Ce processus continue jusqu'à ce qu'il ne reste qu'un seul groupe. Lors de la résiliation de ce processus, tout le monde connaît le nombre de personnes du stade.
J'espère que cela aide.

1 commentaires

+1, votre solution n'a pas besoin de trop de dégusage de symétrie et aucune possibilité de compter en double. Vous pouvez modifier pour permettre une stratégie d'élection de leader.

2
votes

Pour chaque colonne, un leader est choisi avec la règle "La personne de la rangée la plus proche du champ est le leader" (ces sièges sont généralement remplis). Le chef initie un nombre de personnes dans cette colonne de la manière suivante:
1. Sermez la main avec la personne directement assis derrière, et demandez-vous: "Vous?"
2. Si personne n'est derrière la personne, la réponse doit être 1 , ou bien faire l'étape 1 avec la personne derrière, et la réponse est une autre que la réponse de la personne derrière. 3. Le chef écrit immédiatement ce numéro sur une planche et la maintient de la part de 4. Parmi ces dirigeants, la plus jeune personne devrait commencer à collecter ces conseils et les ajouter. Si elle rencontre une personne plus jeune que ses conseils de collecte, le comte jusqu'à ce qu'il soit remis à l'autre personne. Si le même âge, la personne la plus grande prendrait la relève.
0 commentaires
3 votes Dans un petit stade, il y a plusieurs mille personnes dans les stands. Concevoir un algorithme distribué permettant à la audience à compter elle-même. Feynman réponse (voir Round Manhole Question ): Est-ce que tout le monde crie "plusieurs milliers!" < / p> 1 commentaires +1, la réponse est dans la question ... Sorte du bouddhiste mu chose 2 votes Tout le monde goutte leurs draps et la "sortie" est disponible dans le journal local le lendemain ala "N peuple arrêté au premier incident de masse de masse au monde". (C'est-à-dire que l'application demande au système de faire le travail). Chaque personne choisit une autre personne à se battre et demande d'abord combien de personnes ils ont assommé. Le gagnant trouve un autre adversaire, ajoute le compte de l'adversaire vaincu. Dernier homme (ou femme) debout a la réponse. Tout le monde se lève, cueille un cheveu, puis le lui remet à quelqu'un à proximité avec au moins autant de poils avant de rester assis à nouveau. Les gens debout continuent à chercher les autres à donner des cheveux aussi. La dernière personne compte les cheveux. Vous invitez les personnes à saisir un sac de toilettes de la cantine, puis de les remettre jusqu'à ce qu'ils ne trouvent personne qui n'en a pas eu, puis déposez le sac à un point central. Multiplier des sacs * Nombre de Minties-Per-Sac - Nombre de Minties-Gauche-in-Sacs. 0 commentaires 2 votes Voici un autre algorithme: Laissez tout le monde compter les autres et lui-même. Puis, au son d'une corne, chaque comptoir crier son compte. garder le plus crié. Avec cet algorithme, vous pouvez faire face à des erreurs. 2 commentaires Votre solution pourrait fonctionner, mais ne semble pas distribuer la charge. Vous avez raison. C'est une extrême extrême de calcul parallèle (ou plusieurs agents en général): chaque agent calcula toute la tâche. C'est extrêmement tolérant à une faute. L'autre extrême est: chaque agent écrit "+1" sur un papier et donne à cet article à un agent de contrôleur.

Articles qui pourrait vous intéresser : Que puis-je utiliser pour la conversion d'entrée au lieu de scanf? Comment puis-je calculer a * b / c lorsque a et b sont tous deux plus petits que c, mais que a * b déborde? Comment vérifier si un pointeur void (void *) est l'un des deux types de données? L'écran LCD affiche des caractères aléatoires (MPLAB)