Помогите сплетникам как можно эффективнее распространить слухи
Нужно найти алгоритм, который поможет n сплетникам распространить слухи за минимальное количество сообщений.
n сплетников знают слухи, каждый знает о чём-то своём. Они хотят поделиться друг с другом слухами через сообщения. Тот, кто отправляет сообщение, включает в него все слухи, которые слышал, но сообщение может иметь только одного адресата.
Какое минимальное количество сообщений им понадобится, чтобы каждый узнал все слухи?
Ответ
Минимальное количество сообщений — 2n – 2.
Почему?
Есть несколько способов решить эту задачу. Например, можно определить одного человека — назовём его Сплетник 1 — которому все остальные отправят свои слухи. После того, как Сплетник 1 узнает все слухи, он запишет их в сообщение, добавит свой слух и разошлёт это сообщение каждому из n – 1 участников.
2n – 2 — минимальное количество сообщений, потому что если увеличить количество участников на 1, потребуется как минимум 2 дополнительных сообщения — к этом сплетнику и от него, что и демонстрирует алгоритм.
5К открытий5К показов
Держите Java задачи с ответами для начинающих разработчиков: подойдут как для практики, так и для подготовки к собеседованию.
Попросили ChatGPT и Yandex GPT придумать несколько задач, которые зайдут программистам. Сумеете решить?
История о том, как я решил 600 задач на Leetcode и прошел несколько coding сессий в таких компаниях как Booking, Careem и Avito.
Собрали самые каверзные задачи на тему программирования по Go, C# и QA, которые удивили инженеров Ozon Tech, и делимся решениями.