【閒談】
某個村莊中，每天晚上人們便成對地聚集在一起閒談村里的事。在每次交談中，每個人都將其所知的事告訴對方，請問最少經幾次交談後，村里每個人都知道所有消息？
謝謝幫我解答 感恩~!
2006-12-28 08:40:26 · 3 個解答 · 發問者 萬德 1 in 教育與參考 ➔ 其他：教育
假設村裡有n個人, 每個人都各自有獨家消息, 需要k天可完成訊息交換,
那麼從每個人, 每一次交談後所能得到的最多消息來想會較容易,
每個人在沒有交談下, 只知道自己的消息, 表示如下..
0次交談 => 知道1個人的獨家(2的零次方)
設在第1次交談以後, 每個人都可得到彼此的訊息, 最多2倍,
1次交談 => 最多可知道2個人的獨家(2的1次方)
2次交談 => 最多可知道知道4個人的獨家(2的2次方)
3次交談 => 最多可知道知道8個人的獨家(2的3次方)
依此類推...
所以當2的k次方大於等於n時, 所有人就可知道所有人的訊息.
所以k=(log2(n)無條件進入整數)天.
2006-12-28 14:19:53 補充：
注意log2(n)的2是下標
驗証, 假設有14個人, log2(14)=3.xxx, 無條件進入為4, 至少需4天.
2006-12-28 09:15:27 · answer #1 · answered by 星心相印 6 · 0⤊ 0⤋
簡單的解答是 Log2(X), X 為村莊的人數
方法如下，假設村民共有8人
1. 先將村民編號，1....8
2. 第一天 1和2交談，3和4交談 ....
3. 第二天 12找34談，56找78談 .... 同組內的順序不重要
4. 第四天 1234找5678談 ← 所有訊息交換完成
2006-12-28 14:10:27 補充：
補充一下「證明」
1. 由於村民是成對交換「資訊」，所以最快的「資訊」成長率就是兩倍.
2. 本方法取得的「資訊」以2的倍數向上增加，而且增加的「資訊」不會重複，所以是最有效率的方法。至於其他的方法，只要有觀察到「資訊」重複的狀況，自然就不是最佳的方法。
PS. 使用其他的方式，可能也會有一樣快速的結果。前提仍舊是「不能重複」，可以想想看有什麼不同的作法。
2006-12-28 08:59:54 · answer #2 · answered by Zarathustra 7 · 0⤊ 0⤋
數學與邏輯
【閒談】
某個村莊中，每天晚上人們便成對地聚集在一起閒談村里的事。在每次交談中，每個人都將其所知的事告訴對方，請問最少經幾次交談後，村里每個人都知道所有消息？
請問有給村莊的人數嗎?
不然不能推斷
2006-12-28 08:44:47 · answer #3 · answered by Thomas 3 · 0⤊ 0⤋