CURSOR Блог

Задачка про поширення чуток в HR відділі

В HR відділі однієї ІТ компанії останнім часом відбулося багато цікавих подій, але працюючи на ремоуті під час карантину, співробітники не мають можливості швидко поширювати між собою чутки.

N кількість спеціалістів мають інформацію та знають якісь новини, кожен має різну інфу. Всі вони хочуть швидко поділитися один з одним чутками через повідомлення. Той, хто відправляє повідомлення, може включити всі новини, які чув, але повідомлення може мати тільки одного адресата.

Тож питання: яка мінімальна кількість повідомлень знадобиться HR-ам, щоб кожен дізнався всі чутки відділу?




Розв'язання

Є декілька способів розв'язати цю задачку. Ось, наприклад, можна визначити одну людину — назвімо її Пліткар 1 — якому всі інші працівники відправлять свої чутки.
Після того, як Пліткар 1 дізнається всі чутки, він сформує їх у повідомлення, додасть свою інформацію і розішле це повідомлення кожному з n - 1 учасників.
2n - 2 — це мінімальна кількість повідомлень, тому що, якщо збільшити кількість учасників на 1, потрібно як мінімум 2 додаткових повідомлення — до цього учасника і від нього, що і демонструє алгоритм.

Відповідь

Мінімальна кількість повідомлень — 2n - 2.
Задачки