Задачка про поширення чуток в HR відділі
Кажуть, що HR-и завжди в курсі всіх новин, чи так це насправді?
Student_Rostik_Laba
Умова

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

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


Питання


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

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

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

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

Відповідь

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

Сподобалась стаття? Оціни її!
Отримуйте корисну інформацію першими!
Сподобалась стаття? Підписуйтесь та отримуйте корисну інформацію першими!
Ми гарантуємо кожному нашому читачу відсутність спаму, нав'язливої реклами та вторинної інформації.

Отримуйте корисну інформацію першими!