版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
NOIP考前沖刺
--枚舉、搜索武森MAZE現(xiàn)在有一個6×6的迷宮。每個格子可能是空地或者是洞穴。每個格子的四周有可能是墻,如果一個格子的左邊有墻,那么它不能從這個格子往左面的格子走。迷宮中有且只有一個起點〔圓點〕和重點〔星型〕,起點和重點有可能是屬于同一個格子?,F(xiàn)在可以往上〔U〕、下〔D〕、左〔L〕和右(R)四個方向走。先要求用最短的步數(shù)從起點走到終點〔當(dāng)走洞穴是,那么算失敗〕。解法BFS狀態(tài)表示DIST[X,Y]狀態(tài)轉(zhuǎn)移DIST[X,Y]=MIN{DIST[X+DIRX[I],Y+DIRY[I]]}+1轉(zhuǎn)移條件:轉(zhuǎn)到格子是否在范圍內(nèi)轉(zhuǎn)移格子是否有墻轉(zhuǎn)移格子是否似乎洞穴DOUBLE
MAZE現(xiàn)在有兩個6×6的迷宮每個格子可能是空地或者是洞穴。每個格子的四周有可能是墻,如果一個格子的左邊有墻,那么它不能從這個格子往左面的格子走。迷宮中有且只有一個起點〔圓點〕和重點〔星型〕,起點和重點有可能是屬于同一個格子?,F(xiàn)在可以往上〔U〕、下〔D〕、左〔L〕和右(R)四個方向走?,F(xiàn)在同時控制兩個格子的走法〔一個命令兩個迷宮同時走〕,如果有個一個迷宮走到了洞穴,那么失敗。如果有一個格子的要走的方向有墻,那么待在原位置的不動。先要求用最短的步數(shù)〔步數(shù)相同要求字典序最小〕從起點走到終點〔當(dāng)走洞穴是,那么算失敗〕。解法BFS?解法BFS狀態(tài)表示DIST[X1,Y1,X2,Y2]狀態(tài)表示DIST[X1Y1,X2Y2]哪個比較好?解法BFS狀態(tài)表示DIST[X1Y1,X2Y2]狀態(tài)轉(zhuǎn)移DIST[X1Y1,X2Y2]
=MIN{DIST[X1Y1+WAYX[I],X2Y2+WAYY[I]]}+1DIST[X1Y1+WAYX[I],X2Y2+WAYY[I]]表示
能到達[X1Y1,X2Y2]的格子轉(zhuǎn)移條件:轉(zhuǎn)到格子是否在范圍內(nèi)轉(zhuǎn)移格子是否有墻轉(zhuǎn)移格子是否似乎洞穴注意那些有一個格子的路上有墻,留在原地的格解法求出了最短距離。怎么求得字典序最小的方案?方法1每次按字典序有小到大的走路方式〔D,L,R,U〕枚舉走路的格子,判斷DIST’是否等于當(dāng)前格子的DIST-1.方法特點優(yōu)點:容易想到,簡單易寫不容犯錯.缺點:算法復(fù)雜度高,方法2根據(jù)上面的方法,我們易知枚舉是否要走路的格子,如果是,那么DIST’是否等于當(dāng)前格子的DIST-1.那個能否從終點到起點進行BFS,直接計算出路徑最短并且字典序最小的方案?算法實現(xiàn)本卷須知:在倒向BFS的時候,我們要注意的是現(xiàn)在的BFS是對原本實踐的回放,和原本的BFS方式不同。對于一個左邊有墻格子,如果他在原本的BFS的過程當(dāng)中是向左走的,那么我們現(xiàn)在就要向右走,這點毋庸置疑!但是,他有可能是向左走的時候,發(fā)現(xiàn)左邊有墻而停留在原味的結(jié)果,所以對于這種情況,我們要考慮兩種不同的情況,當(dāng)然如果兩個迷宮同時出像這種情況,那么要考慮2×2=4種情況。方法特點優(yōu)點:便于根據(jù)題目要求,得到最短且字典序最小的解。時間復(fù)雜度低缺點:細節(jié)考慮較多編程復(fù)雜度高不易實現(xiàn)考點選手的正向思維和逆向思維思維的嚴謹性智慧珠游戲智慧珠游戲拼盤由一個三角形盤件和12個形態(tài)各異的零件組成。12個零件按珠子數(shù)分3大類第1大類:有三個珠子符號為A第2大類:有四個珠子符號為B符號為C符號為D第3大類:有五個珠子符號為E 符號為I符號為F 符號為J符號為G 符號為K符號為H 符號為L舉例說明字符化B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF條件&要求對于由珠子構(gòu)成的零件,可以放到盤件的任一位置,條件是能有地方放,且尺寸適宜,所有的零件都允許旋轉(zhuǎn)(0o、90o、180o、270o)和翻轉(zhuǎn)(水平、豎直)。
現(xiàn)給出一個盤件的初始布局,求一種可行的智慧珠擺放方案,使所有的零件都能放進盤件中。樣例輸入文件一共有10行,第i行有i個字符。如果第i行的第j個字符是字母”A”至”L”中的一個,那么表示第i行第j列的格子上已經(jīng)放了零件,零件的編號為對應(yīng)的字母。如果第i行的第j個字符是”.”,那么表示第i行第j列的格子上沒有放零件。輸入保證預(yù)放的零件已擺放在盤件中。。
。。
。。。
。。。。
。。。。。
。。。。。C
。。。CCC。
EEEHH。。。
E。HHH。。。。
E。。。。。。。。。輸出樣例如果能找到解,輸出10行,為放完全部12個零件后的布局。其中,第i行應(yīng)包含i個字符,第i行的第j個字符表示第i行第j列的格子上放的是哪個零件。如果無解,輸出單獨的一個字符串”Nosolution”(不要引號,請注意大小寫)。所有的數(shù)據(jù)保證最多只有一組解。B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF解法BFSorDFS解法BFS不好記錄狀態(tài),解最多為一個,不存在深度較淺的解DFSNOSOLUTION輸入數(shù)據(jù)中“.”的個數(shù)與實際需要填的形狀的柱子總數(shù)不符。。。預(yù)處理對于每個珠子,將其的構(gòu)造形式量化,便于搜索時使用方法1最簡單的思路從第一行的第一個位置開始搜索,嘗試將當(dāng)前情況下的沒有放過的珠子,放在個這個位置上〔這個位置為珠子的某一個角而不是其中任意一個點〕依次搜索每一個沒有放東西的位置,直至最終沒有格子沒有放下并且所有的珠子都已經(jīng)放完了如果滿足要求,那么輸出解如果不滿足要求,那么屬于Nosolution方法特點優(yōu)點:思路簡單,清晰代碼易寫缺點:根本沒有優(yōu)化的可能性時間復(fù)雜度較高方法2通過觀察題目中的不同珠子我們發(fā)現(xiàn),對有有些珠子,如:G,J,K等珠子,由于形狀比較特殊,所以可能與其有連接的珠子的形式比較單一,可以預(yù)處理出來,在搜索的時候,可以從這里入手。觀察輸入文件為一個三角形,那么對于斜邊上的位置,會造成有一些格子不能被放置,這一點也可以預(yù)先處理出來,可以有效地進行優(yōu)化算法特點優(yōu)點:改變搜索的順序,可以有效的減少搜索的次數(shù)對于一些特殊的情況,事先預(yù)處理出來,可以有效的減枝時間復(fù)雜度較方法1有一定的優(yōu)勢缺點:算法要預(yù)處理的內(nèi)容有些復(fù)雜編程復(fù)雜度較高BFSORDFS探險隊得到了一張古老藏寶的地圖,圖中包含n神秘的地點,并且知道這些神秘的地點之間是有一些隧道連接的,并且探險隊知道藏寶圖中包含了m條隧道,〔m<n〕,經(jīng)過探險的觀察這個藏寶圖中不包含什么回路〔即任意兩點之間最多存在一條路徑使其相連〕,藏寶圖中當(dāng)中可能包含很多區(qū)域,任意兩個區(qū)域是不相通的,現(xiàn)在藏寶圖和探險隊走過藏寶圖中的某些神秘的地點,又知道探險隊只能采取深度優(yōu)先搜索或者寬度優(yōu)先搜索的方式來對藏寶地點進行探險,請問探險隊可能使用哪種方式進行探險的?輸入數(shù)據(jù)第一行兩個數(shù)字n、m和k表示藏寶圖中有多少個神秘地點由1到n表示這個n個神秘地點和藏寶圖中的道路和探險隊已經(jīng)探過的神秘地點數(shù)目。接下來的m行每行兩個數(shù)ai,bi表示神秘地點ai和神秘地點bi有道路相連。在接下來的k行每行一個數(shù)字表示那些神秘地點被探過。輸出數(shù)據(jù)輸出有種情況DFS 表示是深度優(yōu)先搜索的BFS 表示是寬度優(yōu)先搜索的BOTH 表示兩種情況都有可能NEITHER 表示兩種情況都不可能題目模型抽象給定一個無向圖,并且其中一些點被遍歷,現(xiàn)在詢問你這些點是怎么遍歷的?思路首先對于圖進行遍歷。由于不同的聯(lián)通分支之間互不影響所以進行處理。判斷是哪種方法?思路什么情況下無解?
如果有兩個或兩個以上聯(lián)通分支沒有被完全遍歷到對于這種情況是不不可能存在某一種算法,能便利成那個樣子的。
所以Nosolution思路那么這道題目,就簡化成了對以某一聯(lián)通分支進行檢查,判斷其遍歷方式。思路BFS: 一直對于某一聯(lián)通分支〔題目中已經(jīng)給出圖中沒有環(huán)〕,所以這是一棵樹,如果我們確定了這棵樹的樹根,那么就很好判斷這棵樹是否是用BFS遍歷得了。 怎么求得這棵樹的樹根呢?思路不妨枚舉樹根易知寬度優(yōu)先搜索的最深深度與最淺深度相差為一那么對于圖中的各個不同的遍歷路徑,我們都可以計算深度,從而判斷,是否為BFS思路DFS: 白板聰明的火車司機一輛有n個門的火車駛進了一座長len的火車站,火車的n個門在火車上的位置分別為di(1≤i≤n,且d1=0,di≤len)。火車站有m個乘客,第i個乘客位于火車站的pi(pi≤len)位置,一個乘客會選擇離他最近的門上車?;疖嚨拿總€門都必須停在火車站內(nèi),為了讓所有乘客上車時走的距離和最長,火車司機應(yīng)該讓火車的第一個門停在火車站的什么位置,最長距離和又是多少。輸入樣例第一行一個數(shù)len第二行一個數(shù)m第三行m個遞增的非負整數(shù)p1,p2,……pm第四行一個數(shù)n第五行n-1個遞增的正整數(shù)d2,d3,……dn45012344123輸出數(shù)據(jù)一行兩個數(shù)分別表示最優(yōu)位置和最長距離和,答案保存3位小數(shù)0.5002.500思路枚舉枚舉什么?車??康奈恢????思路最簡單的方法是以0.001為步長枚舉時間復(fù)雜度為O(1000l(n+m))優(yōu)化策略用反證法容易證明最優(yōu)情況下至少有一個人位于兩個門的中點,以此為根據(jù)可將步長調(diào)整為0.5再枚舉復(fù)雜度為O(l(n+m))誤差曲線小紅是個聰明的女孩,最近沉迷于機器學(xué)習(xí)。她非常喜歡的方法稱為線性判別分析,其中有許多有趣的性質(zhì)。為了檢驗該算法的效率,她收集很多的數(shù)據(jù)集。更重要的是,每個數(shù)據(jù)分為兩局部:訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)。她得到的訓(xùn)練數(shù)據(jù)模型的參數(shù)和測試的測試數(shù)據(jù)模型。令她驚訝的是,她發(fā)現(xiàn)每個數(shù)據(jù)集的測試誤差曲線只是一個拋物曲線。一個拋物曲線對應(yīng)一個二次函數(shù)。在數(shù)學(xué)中,二次函數(shù)的形式是多項式函數(shù)f(x)=ax^2+bx+c.如果只有一個測試誤差曲線的最小誤差值很容易計算。然而,有幾個數(shù)據(jù)集,這意味著小紅將獲得許多拋物曲線。小紅希望得到,使所有數(shù)據(jù)集上的最正確性能優(yōu)化的參數(shù)。所以她應(yīng)該考慮到,即所有誤差曲線,她要面對許多二次函數(shù),并作出新的錯誤定義,將其總誤差?,F(xiàn)在,她著重于以下新的功能的最小二次其中涉及到多個職能。新的函數(shù)F〔x〕的定義如下: F(x)=max(Si(x)),i=1...n.,xis[0,1000].Si(x)isaquadricfunction現(xiàn)在小紅想要知道函數(shù)F〔x〕的最小值是多少?輸入數(shù)據(jù)輸入數(shù)據(jù)包含兩局部。第一局部是一個整數(shù)n表示有多少個測試誤差曲線第二局部由n行組成,每行有三個數(shù)字a,b,c,表示測試誤差曲線的三個參數(shù)a(0≤a≤100),b(|b|≤5000),c(|c|≤5000)。2200
2-42輸出數(shù)據(jù)輸出小紅想要的最小值0.5000思路對于這道題目,我們可以看到這個曲線有一下特殊情況:直線頂點這些情況要特殊處理。方法1由于我們要尋找一個點,使得函數(shù)F〔x〕的最小,我們最初的想法和上一道題目一樣,能不能枚舉我們選取的那個點,然后以此計算這個點上的函數(shù)F〔x〕的值。最終得到答案。算法特點有點:思路簡單,通俗易懂缺點:算法時間復(fù)雜度很高
方法2既然枚舉選取的值不行,那么這道題是不是不是枚舉呢?枚舉答案?方法2如果枚舉答案,我們就要怎么計算這個答案,能不能在答案范圍內(nèi)找到呢?見白板有趣的樓道小明在漆黑的光棍節(jié)晚上還要悲催的去上一節(jié)政治課,他心里越想越
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024數(shù)據(jù)采集技術(shù)服務(wù)合同-醫(yī)療健康信息采集3篇
- 2024年鋅錠回收利用項目合作協(xié)議3篇
- 2024旅游度假區(qū)開發(fā)建設(shè)合同
- 勞務(wù)派遣期限協(xié)議書
- 勞務(wù)派遣的業(yè)務(wù)范圍協(xié)議書
- 2025年度XX市政工程污水處理廠建設(shè)項目合同
- 2024版居間合同管轄權(quán)的規(guī)定
- 2024版一件代發(fā)商品服務(wù)協(xié)議范例版B版
- 2025版高科技產(chǎn)業(yè)園區(qū)建筑工程技術(shù)員聘用合同范本2篇
- 2024汽車信用卡分期擔(dān)保合同
- 2024-2030年中國高密度聚乙烯管道行業(yè)發(fā)展展望與投資策略建議報告
- 2024-2030年中國醋酸乙烯行業(yè)運營狀況與發(fā)展風(fēng)險評估報告
- 企業(yè)文化塑造與員工激勵方案
- 2024年01月22504學(xué)前兒童科學(xué)教育活動指導(dǎo)期末試題答案
- 多發(fā)性神經(jīng)病護理
- 【MOOC】線性代數(shù)-浙江大學(xué) 中國大學(xué)慕課MOOC答案
- 開門紅包費用申請
- 區(qū)塊鏈原理與實踐全套完整教學(xué)課件
- 運動神經(jīng)元病小講課
- 工會的財務(wù)管理制度〔13篇〕
- 新版醫(yī)務(wù)人員法律法規(guī)知識培訓(xùn)課件
評論
0/150
提交評論