Минимальное количество звонков?

Есть «n» количество детективов. Каждый знает информацию, сколько минимальных звонков они должны делать, чтобы все детективы знали все n количество информации?Минимальное количество звонков?

Мой ответ: я придумал 2n-3 (то есть, п-1 + п-2) решение, в котором детектив называет п-1 других детективов и делится информацией взаимно (в этом случае последний детектив и первая имеет всю информацию). Затем оставшиеся n-2 детективы, у которых нет всех данных, звонят либо первому детектору, либо последнему, чтобы получить оставшуюся информацию.

(Это вопрос, заданный моим другом).

источник

2013-09-28 saikiranboga

@ Vaughn Катон >> да я имею в виду это 2n-3, как уже упоминалось в моем ответе (извините за письма, если вы сделали не понимаю). Я задаюсь вопросом, есть ли какой-либо оптимальный алгоритм или какой-то метод, благодаря которому мы можем уменьшить количество вызовов. – saikiranboga

Ах да, я неправильно понял круглые скобки. Я отредактировал вопрос, чтобы сделать его более ясным. –

Вопросы мне непонятно. Делекты рассказывают друг другу только свой секрет в разговоре или во всех секретах, которые они знают. – goldenmean

2n-3 неверен.

Рассмотрим случай n = 4, 2n-3 будет прогнозировать, что требуется 2 * 4-3 = 5 вызовов.

Однако, мы можем сделать это в 4-х звонков через:

A calls B 
C calls D 
A calls C 
B calls D

источник

2013-09-28 18:17:16

Доказательство того, что 2n-4 является оптимальным в [«R. Bumby, проблема с телефонами»] (http://www.math.rutgers.edu/~bumby/telephone.pdf) –

Можете ли вы вкратце дать обзор того, как бумага идет или может указывать на некоторые другие источники, которые могут объяснить эту статью? – saikiranboga

Минимальное количество звонков?

ответ

Смежные вопросы