algorithm - 最少要调用多少电话？

Question

有 'n' 个侦探..每个人都知道一个信息，他们应该至少调用多少次才能让所有侦探都知道所有的 n 个信息？

我的回答:我提出了 2n-3(即 n-1 + n-2)个解决方案，其中一名侦探调用 n-1 名其他侦探并相互共享信息(以这种方式最后一个侦探和第一个侦探拥有所有信息)。然后剩下的 n-2 个没有全部数据的侦探调用第一个或最后一个侦探来获得剩余的信息。

(这是我 friend 问的问题)

Answer 1

2n-3 不正确。

考虑 n=4 的情况，2n-3 将预测需要 2*4-3=5 次调用。

但是，我们可以通过以下方式在 4 个调用中完成:

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