淺談二分策略的應(yīng)用-預(yù)覽頁(yè)
【正文】 最終獲勝，那么 排名在 X前 的選手 Y也可以獲勝。 例如 N=8， K=2， X=6 6?7 5?3 4?8 2?1 6?5 4?2 6?4 可以！ 5/19/2023 15 WinterCamp 2023 小結(jié) ?算法的根本 —— 在一個(gè) 隱含的退化了的 有序序列中進(jìn)行二 分查找 0 0 0 0 0 0 0 0 1 1 1 1 1 1 XAns X≥Ans ?我們所尋找的 —— 兩種值的 分界點(diǎn) 。 5/19/2023 17 WinterCamp 2023 類型三：二分搜索 —— 應(yīng)用于無(wú)序序列 二分策略 有序 序列 無(wú)序 序列 5/19/2023 18 WinterCamp 2023 例三：推銷員的旅行 ? [問(wèn)題轉(zhuǎn)述 ] 這是一個(gè)交互式問(wèn)題： 在一個(gè)未知的競(jìng)賽圖（即有 N頂點(diǎn)，兩點(diǎn)間恰只含一條邊的有向圖）中，通過(guò)不斷詢問(wèn)任意兩點(diǎn)之間邊的方向，尋找一條哈密爾頓路 。 1 2 5/19/2023 20 WinterCamp 2023 初步分析 ?假設(shè)我們已設(shè)計(jì)了一條含有前 i個(gè)點(diǎn)、長(zhǎng)度為i1的線路 A1?A2?… ?Ai，我們希望再加入點(diǎn) i+1，將其變成長(zhǎng)度為 i的線路。且已知 A1?i+1， i+1?Ai。 i+1 i+1 A1 A[i/2] Ai i+1 O P ? 5/19/2023 25 WinterCamp 2023 總結(jié) ?在這里我僅簡(jiǎn)單地介紹了三個(gè)二分策略應(yīng)用的例子，要涵蓋二分策略的所有應(yīng)用甚至是大部分應(yīng)用都是困難的。 ?這就要求我們能有 ? 扎實(shí)的基本功 ? 豐富的解題經(jīng)驗(yàn) ? 大膽合理的猜測(cè) ? 活躍的創(chuàng)造思維 ?方可? 以不變應(yīng)萬(wàn)變 ?！ 5/19/2023 27 WinterCamp 2023 5/19/2023 28 WinterCamp 2023
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1