Задача стадиона: предоставить алгоритм для решения проблемы - PullRequest
Новая
       4

Задача стадиона: предоставить алгоритм для решения проблемы

6 голосов
/ 25 марта 2011

На небольшом стадионе на трибунах несколько тысяч человек.Разработайте распределенный алгоритм, позволяющий аудитории считать себя.Не предполагайте какую-либо конкретную геометрию стадиона, за исключением, если хотите, формы чаши.Явно изложите свои предположения, затем представьте свой алгоритм и анализ.

Я предполагал, что участники были связаны списком и добавлял счетчик и свободный (ptr) .. Я могу ошибаться ...предоставить некоторые полезные идеи

Спасибо в Adv ...

Ответы [ 5 ]

11 голосов
/ 25 марта 2011

Если предположить, что каждый может поговорить со своим соседом (возможно, через много пустых мест) и что фанаты команды A готовы поговорить с фанатами команды B, может сработать следующее:

Каждый захватывает его /ее ближайший сосед, которого еще никто не схватил, сформировал группы максимум из двух человек.Теперь все помнят размер группы, в которой они находятся (может быть 1 или 2).Теперь лидер каждой группы выбирается таким образом, чтобы он мог общаться с членом другой группы.Лидеры каждой группы пытаются присоединиться к своей группе друг с другом, и каждый член двух (теперь присоединившихся) групп запоминает сумму членов каждой группы (это можно сделать, передавая новое значение, которое будет добавлено в группу),Этот процесс продолжается до тех пор, пока не останется только одна группа.По окончании этого процесса все знают количество людей на стадионе.

Надеюсь, это поможет.

3 голосов
/ 26 марта 2011

На небольшом стадионе на трибунах несколько тысяч человек.Разработайте распределенный алгоритм, позволяющий аудитории считать себя.

Ответ Фейнмана (см. вопрос о круглых люках ): Пусть все кричат: «Несколько тысяч!»

2 голосов
/ 08 апреля 2011

Вот еще один алгоритм:

  1. Пусть каждый считает себя и других.
  2. Затем, при звуке рога, каждый жетон выкрикивает свой счет.
  3. Сохраняйте наибольшее количество криков.

С помощью этого алгоритма вы можете справиться с ошибками.

2 голосов
/ 08 апреля 2011
  • Каждый бросает свои даки, и на следующий день в местной газете есть «выход», известный как «N человек арестованы во время первого в мире массового инцидента».(т. е. приложение просит систему выполнить работу).
  • Каждый человек выбирает одного другого человека для борьбы и сначала спрашивает, сколько людей он нокаутировал.Победитель находит другого противника, добавляет количество побежденного противника.У последнего стоящего мужчины (или женщины) есть ответ.
  • Все встают, отщипывают волосы, а затем вручают их кому-то поблизости, имеющему как минимум столько же волос, прежде чем снова сесть.Постоянные люди продолжают искать других, чтобы подстричься.Последний подсчитывает волоски.
  • Вы предлагаете людям взять из столовой пакет с мятежниками, а затем вручите их, пока они не найдут никого, у кого его нет, а затем бросьте пакет вцентральная точка.Умножение сумок * количество минут на одну сумку - количество оставшихся в сумке минут.
2 голосов
/ 25 марта 2011

Для каждого столбца выбирается лидер с правилом «человек в ряду, ближайший к полю, является лидером» (эти места обычно заполнены). Лидер инициирует подсчет людей в этом столбце следующим образом:
1. Пожмите руку человеку, сидящему сзади, и спросите: «Вы?»
2. Если позади человека нет никого, ответом должно быть 1, или же выполните шаг 1 с человеком позади, и ответ на один больше, чем ответ от человека позади. 3. Лидер немедленно записывает этот номер на доске и держит его
4. Среди этих лидеров самый молодой человек должен начать собирать эти доски и добавлять их. Если она встречает человека, который моложе ее сборщиков, счет до этого передается другому человеку. Если тот же самый возраст, более высокий человек вступил бы во владение.

...