算法合集之一類稱球問題的解法-文庫吧資料
2024-10-22 20:29本頁面
【正文】 重的次品混入其中 ? 你有一架天平，用最少的次數(shù)找出這個次品。 N = 3 1 2 3 1 2 ① 是次品 1 2 ② 是次品 1 2 ③ 是次品 N=3時稱 1次就可以找出次品 N = 9 1 2 3 4 5 6 7 8 9 A B C A B 次品在 A中 次品在 B中 A B ? 通過一次稱量，可以把次品可能存在的范圍從 9個，縮小到 3個 ? N = 3的時候一次就能稱出次品 N = 9時稱 2次 次品在 C中 A B 更一般的情況 N = 3k 1 2 k …… 1 2 k …… 1 2 k …… A B C 更一般的情況 A B A B A B 次品在 A中 次品在 B中 次品在 C中 范圍縮小到原來的1/3 更一般的情況 ? n = 3k+1, n = 3k+2和 n=3k類似，也是均分成三堆 ? 每次稱量把范圍大致縮小到原來的 1/3 ? 因此：從 n個球中找次品至多要稱 [log3n]次。 最優(yōu)性 為什么三分？ 因為天平只有三種可能：左偏、右偏、平衡 判定樹 稱 (1, 2) = 1 3 2 ? 葉子代表結(jié)果 ? 非葉子代表一次稱量 ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1