acm基礎(chǔ)算法入門(mén)講述-全文預(yù)覽
【正文】 b)=gcd(b,a mod b)。 設(shè) ab。 1= a , b =10^9 輸入： 4,11 輸出： 3001,第二十七頁(yè)，共三十五頁(yè)。,輾轉(zhuǎn)相除法,擴(kuò)展歐幾里得 雙六 一個(gè)雙六上面有向前向后無(wú)限延續(xù)的格子，每個(gè)格子都寫(xiě)有整數(shù)。,數(shù)論那些事,數(shù)學(xué)，特別是數(shù)論與計(jì)算機(jī)科學(xué)有著密切的聯(lián)系，所以也常被選作題材。因此，直到圖中不再存在39。連接的39。的出發(fā)，將這點(diǎn)的坐標(biāo)上下左右全部用39。,例題：,水池?cái)?shù)目 南陽(yáng)理工學(xué)院校園里有一些小河和一些湖泊，現(xiàn)在，我們把它們通一看成水池，假設(shè)有一張我們學(xué)校的某處的地圖，這個(gè)地圖上僅標(biāo)識(shí)了此處是否是水池，現(xiàn)在，你的任務(wù)來(lái)了，請(qǐng)用計(jì)算機(jī)算出該地圖中共有幾個(gè)水池。 與深度優(yōu)先搜索的不同在于搜索的順序，寬度優(yōu)先搜索總是先搜索距離初始狀態(tài)近的狀態(tài)，也就是說(shuō)它是按照開(kāi)始狀態(tài)只需1次轉(zhuǎn)移就可到達(dá)的所有狀態(tài)只需2次轉(zhuǎn)移就可到達(dá)的狀態(tài)，這樣的順序進(jìn)行搜索。,解題過(guò)程,i=3 sum=2,i=1 sum=1,i=1 sum=0,i=2 sum=0,i=0 sum=0,i=3 sum=6,i=2 sum=2,+1,+4,+2,從a1開(kāi)始按順序決定每個(gè)數(shù)加或不加，在全部n個(gè)數(shù)決定后在判斷他們的和是不是k即可。 根據(jù)深度優(yōu)先搜索的特點(diǎn)，采用遞歸函數(shù)實(shí)現(xiàn)比較簡(jiǎn)單。,窮竭搜索是指將所有的可能性羅列出來(lái)，在其中尋找答案的方法。雖然貪心策略比上面的題 復(fù)雜，但是仍然只需要一次掃描。,第十六頁(yè)，共三十五頁(yè)。,【分析】 本題的突破口仍然是區(qū)間包含和排序掃描，不過(guò)要先 進(jìn)行一次預(yù)處理。如果第一個(gè)區(qū)間不選最后一個(gè)點(diǎn)， 而是去中間的，如灰色點(diǎn)，那么把它移動(dòng)到最后一個(gè)點(diǎn)后， 被滿(mǎn)足的區(qū)間增加了，而且原先被滿(mǎn)足的區(qū)間現(xiàn)在一定被滿(mǎn) 足。第一個(gè)區(qū)間應(yīng)該選取哪一個(gè)點(diǎn)呢？正確的貪心策略 是：取最后一個(gè)點(diǎn)。受上一題的啟發(fā)，我們先討論區(qū)間包含的情況。,第十三頁(yè)，共三十五頁(yè)。,第十二頁(yè)，共三十五頁(yè)。,選擇不相交區(qū)間,數(shù)軸上有n個(gè)開(kāi)區(qū)間（ai,bi），選擇盡量多個(gè)區(qū)間， 使得這些區(qū)間兩兩沒(méi)有公共點(diǎn)。,第八頁(yè)，共三十五頁(yè)。,解題思路,列狀態(tài) v [ I ] [ j ]表示走到第i層的第j個(gè)節(jié)點(diǎn)的最大值 分階段 每一個(gè)層就是一個(gè)階段 狀態(tài)轉(zhuǎn)移方程（決策） V [ i1 ] [ j ] += V [ I ] [ j ] v [ I ] [ j + 1 ] ? V [ I ] [ j ] : v [ I ] [ j + 1 ]。,基礎(chǔ)動(dòng)態(tài)規(guī)劃,多階段決策過(guò)程最優(yōu)化的數(shù)學(xué)方法 三要素： 階段 決策 狀態(tài),第三頁(yè)，共三十五頁(yè)。,引言,算法簡(jiǎn)單但思想及其重要 介紹的算法都堪稱(chēng)為經(jīng)典中的
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1