算法合集之一類(lèi)稱球問(wèn)題的解法(編輯修改稿)
2024-11-12 20:29 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 。 次品若在②中，則它偏輕。 引理的提出 ?已知兩堆球，第一堆有 a個(gè)、第二堆有 b個(gè)。 ?若次品在第一堆，必是重球 ?若次品在第二堆，必是輕球 分析 ? 總共 a+b個(gè)球 ? 每個(gè)球都有可能是次品 ? 判定樹(shù)至少 a+b個(gè)葉子 ? 樹(shù)的深度 h = [log3(a+b)] ?只要稱 [log3(a+b)]次就能找到次品 引理的分析 a = 3p …… p 個(gè) …… p 個(gè) …… p 個(gè) A1 A2 A3 b = 3q …… p 個(gè) B1 B2 B3 …… p 個(gè) …… p 個(gè) 引理的分析 A1 B1 A2 B2 A3 B3 次品在 A1 或者 B2 范圍被縮小到 p+q個(gè)球里面 引理的分析 A1 B1 A2 B2 A3 B3 次品在 B1 或者 A2 范圍被縮小到 p+q個(gè)球里面 引理的分析 A3 B3 次品在 A3 或者 B3 范圍被縮小到 p+q個(gè)球里面 A1 B1 A2 B2 子問(wèn)題的分析 ? 總共 a+b=3(p+q)個(gè)球 ? 無(wú)論天平怎么偏，都可以把范圍縮小到p+q個(gè)球中，即原來(lái)的 1/3 ? 根據(jù) a, b mod 3的余數(shù)分類(lèi)，上面討論的是 a mod 3 = b mod 3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1