acm基礎(chǔ)算法入門(mén)講述(編輯修改稿)
2024-11-19 05:01 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 現(xiàn)比較簡(jiǎn)單。,第十九頁(yè)，共三十五頁(yè)。,例題,給定整數(shù) a1,a2,a3,an, 判斷是否可以從中選出若干個(gè)數(shù)，使他們的和恰好為k。 限制條件： 1=n20 10^8=ai=10^8 10^8=k=10^8 輸入： 4 1,2,4,7 13 輸出： Yes,輸入： 4 1,2,4,7 15 輸出： No,第二十頁(yè)，共三十五頁(yè)。,解題過(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即可。,第二十一頁(yè)，共三十五頁(yè)。,寬度優(yōu)先搜索,寬度優(yōu)先搜索（BFS，BreadthFirst Search）也是搜索的手段之一。與深度優(yōu)先搜索類(lèi)似，從某個(gè)狀態(tài)出發(fā)探索所有可以到達(dá)的狀態(tài)。 與深度優(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)行搜索。對(duì)于同一狀態(tài)，寬度優(yōu)先搜索只經(jīng)過(guò)一次，因此復(fù)雜度為O（狀態(tài)數(shù)*轉(zhuǎn)移的方式）。 根據(jù)寬度優(yōu)先搜索的特點(diǎn)，采用隊(duì)列進(jìn)行實(shí)現(xiàn)。,第二十二頁(yè)，共三十五頁(yè)。,例題：,水池?cái)?shù)目 南陽(yáng)理工學(xué)院校園里有一些小河和一些湖泊，現(xiàn)在，我們把它們通一看成水池，假設(shè)有一張我們學(xué)校的某處的地圖，這個(gè)地圖上僅標(biāo)識(shí)了此處是否是水池，現(xiàn)在，你的任務(wù)來(lái)了，請(qǐng)用計(jì)算機(jī)算出該地圖中共有幾個(gè)水池。 輸入m行每行輸入n個(gè)數(shù)，表示此處有水還是沒(méi)水 （1表示此處是水池，0表示此處是地面） 0m100 0n100 輸入： 3 4 1 0 0 0 0 0 1 1 1 1 1 0 輸出： 2,輸入： 5 5 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 輸出： 3,第二十三頁(yè)，共三十五頁(yè)。,解題過(guò)程,本題是簡(jiǎn)單的搜索問(wèn)題，采用深度優(yōu)先遍歷可以解決，根據(jù)題目要求，假設(shè)從任意一點(diǎn)值為39。139。的出發(fā)，將這點(diǎn)的坐標(biāo)上下左右全部用39。039。替換，1次DFS后與初始動(dòng)這個(gè)39。139。連接的39。139。全部被替換成39。039。，因此，直到圖中不再存在39。139。為至，總共進(jìn)行的DFS的次數(shù)就是最后的結(jié)果咯！那么，根據(jù)題目要求，有4個(gè)方向，時(shí)間復(fù)雜度為O(4*n*m)。,第二十四頁(yè)，共三十五頁(yè)。,數(shù)論那些事,數(shù)學(xué)，特別是數(shù)論與計(jì)算機(jī)科學(xué)有著密切的聯(lián)系，所以也常被選作題材。雖然數(shù)學(xué)問(wèn)題大多需要使用特定方法求解，但其中有幾個(gè)基
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1