Re: [請益] 找出假幣
※ 引述《H45 (!H45)》之銘言：
: 深究：k個錢幣中有一袋假幣(與真幣重量不同)，請利用天平秤秤n次找出假幣
: ，並說出假幣的重量較輕還是重。請問Minimum of n？
: 如何以一個演算法算出這個Minimum of n?
我找到方向了
用 三元樹 (3-ary tree) 模擬
往左的 child 是天平往左傾
往右的 child 是天平往右傾
往中的 child 是天平不傾斜
而樹的高，就是天平要秤的次數 n
樹葉 (leaf) 的數量，就是錢幣的數量 k
設 f(x) 表以 3 為底的 logx
upper(x) 表 x 無條件進入至整數
則 n >= upper(f(k))
也就是說 n 的 lower bound 是 upper(f(k))
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.85
討論串 (同標題文章)
本文引述了以下文章的的內容：
請益
2
2
完整討論串 (本文為第 14 之 14 篇)：
請益
2
2
請益
2
3
請益
2
3
請益
1
2
請益
6
13
請益
1
4
請益
1
1
請益
2
4