版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
C語言基礎,簡單數(shù)據(jù)結(jié)構(gòu),
ACM入門講座
搜索部分Bjut:mark0632010.10.301C語言是什么forwhileif…else…switch,case函數(shù)調(diào)用變量,數(shù)組,結(jié)構(gòu)體聲明&,*,->,||,&&,==,++,+=輸入輸出scanf,printf,freopen(“in.txt”,”r”,stdin);2ACM/ICPCACM-ICPC以團隊的形式代表各學校參賽,每隊由3名隊員組成。每位隊員必須是在校學生,有一定的年齡限制,并且最多可以參加2次全球總決賽和5次區(qū)域選拔賽。比賽期間,每隊使用1臺電腦需要在5個小時內(nèi)使用C、C++或Java中的一種編寫程序解決7到10個問題。程序完成之后提交裁判運行,運行的結(jié)果會判定為正確或錯誤兩種3其他比賽Topcoder,Codeforces平均每周一次,還定期有其他形式的比賽,要求快速準確的構(gòu)造算法寫代碼能力有道難題,百度之星,每年5,6月份數(shù)學建模,校內(nèi)賽4,5月,全國9月4參考書目圖書館有關(guān)acm的書網(wǎng)上OJ5天津賽區(qū)哈爾濱賽區(qū)6POJ2027NoBrainerTimeLimit:1000MSMemoryLimit:30000KTotalSubmissions:15196Accepted:10314DescriptionZombieslovetoeatbrains.Yum.InputThefirstlinecontainsasingleintegernindicatingthenumberofdatasets.
Thefollowingnlineseachrepresentadataset.Eachdatasetwillbeformattedaccordingtothefollowingdescription:
Asingledatasetconsistsofaline"XY",whereXisthenumberofbrainsthezombieeatsandYisthenumberofbrainsthezombierequirestostayalive.OutputForeachdataset,therewillbeexactlyonelineofoutput.Thislinewillbe"MMMBRAINS"ifthenumberofbrainsthezombieeatsisgreaterthanorequaltothenumberofbrainsthezombierequirestostayalive.Otherwise,thelinewillbe"NOBRAINS".SampleInput3453343SampleOutputNOBRAINSMMMBRAINSMMMBRAINS7DescriptionZombieslovetoeatbrains.Yum.InputThefirstlinecontainsasingleintegernindicatingthenumberofdatasets.
Thefollowingnlineseachrepresentadataset.Eachdatasetwillbeformattedaccordingtothefollowingdescription:
Asingledatasetconsistsofaline"XY",whereXisthenumberofbrainsthezombieeatsandYisthenumberofbrainsthezombierequirestostayalive.OutputForeachdataset,therewillbeexactlyonelineofoutput.Thislinewillbe"MMMBRAINS"ifthenumberofbrainsthezombieeatsisgreaterthanorequaltothenumberofbrainsthezombierequirestostayalive.Otherwise,thelinewillbe"NOBRAINS".8ACM題型分類1,基本算法2,圖算法3,數(shù)據(jù)結(jié)構(gòu)4,搜索5,動態(tài)規(guī)劃6,貪心7,數(shù)學8,計算幾何9,模擬9搜索概論搜索被稱為“通用解題法”,在算法和人工智能中占據(jù)重要地位。但由于它巨大的局限性和自身靈活性,也被認為是最難學難用的算法之一。本節(jié)目標:希望同學們對于任意一個問題,
1.很快建立狀態(tài)空間 2.提出一個合理算法 3.簡單估計時空性能10搜索分類盲目搜索:按預定的控制策略進行搜索,在搜索過程中獲得的中間信息不用來改進控制策略。啟發(fā)式搜索:在搜索中加入了與問題有關(guān)的啟發(fā)性信息,用以指導搜索朝著最有希望的方向發(fā)展,加速問題的求解過程并找到最優(yōu)解。11搜索算法盲目搜索:1.廣度優(yōu)先搜索(BreadthFirstSearch)2.深度優(yōu)先搜索(DepthFirstSearch)3.純隨機搜索、重復式搜索、迭代加深搜索、迭代加寬搜索、柱型搜索啟發(fā)式搜索:1.A*算法2.IDA*算法12DFS&BFS深搜例子:走迷宮,你沒有辦法用分身術(shù)來站在每個走過的位置。不撞南山不回頭。廣搜例子:你的眼鏡掉在地上以后,你趴在地板上找。你總是先摸最接近你的地方,如果沒有,再摸遠一點的地方……13狀態(tài)空間明確以下概念:狀態(tài):問題在某一時刻進展狀況的數(shù)學描述。狀態(tài)轉(zhuǎn)移:問題從一種狀態(tài)到另一種或幾種狀態(tài)的操作。狀態(tài)空間:一個“圖”,圖結(jié)點對應于狀態(tài),點之間的邊對應于狀態(tài)轉(zhuǎn)移。搜索:尋找一種可行的操作序列,從起始狀態(tài)經(jīng)過一系列狀態(tài)轉(zhuǎn)移,達到目標狀態(tài)。14搜索基礎搜索是常人最容易想到的解題辦法,可以說所有題都可以用搜索解決,但是沒有剪枝搜索可以看成是窮舉法,時間上無法忍受158皇后問題給定8*8棋盤,要在上邊放子,要求各棋子在同一行,同一列,同
一斜邊上不能有兩個或兩個以上的子,找到所有的放子方法,并輸出放子過程與種類數(shù)。16深搜:可運行代碼在備注中17
一個從起始狀態(tài)到達目標狀態(tài)包含多步操作,而每一步操作又有幾種可能,只有正確的操作才能達到目標(如八皇后問題),這樣的問題可以看做是一個樹。
如果按照1-2-4-5-3-6-7的順序,叫深度優(yōu)先(DFS)
如果按照1-2-3-4-5-6-7的順序,叫廣度優(yōu)先(BFS)1234567概述18voidDFS(intk)//處理第k步{if(k==n)//已經(jīng)處理到第n步,到達目的狀態(tài)
輸出結(jié)果
else//處理第k步
for(inti=1;i<=m;i++)//第k步中有m種可能
{處理第k步
DFS(k+1);//進入第k+1步
}}深度優(yōu)先(DFS)模板:19幫助小明小明參加一個搶東西的電視節(jié)目。這個節(jié)目很有意思,一共有n個東西可以拿(n<50)每個參加活動的人不能拿重量超過m(m<2000)的東西,而每個東西都有它的價值v,有的高有的低,幫助小明安排要拿的東西,使總價值最高。輸入 512
35 46 53 89 108 00樣例輸出:1520幫助小明這是一個0-1背包問題。對于每件物品,有兩種選擇:1)拿這件物品(條件是最大重量不超過m)2)不拿這件物品下面程序給出0-1背包的dfs解法,效率無法忍受,但是理解簡單。下一次會介紹動態(tài)規(guī)劃的0-1背包解法效率會提升很大(備注中給出0-1背包動態(tài)規(guī)劃解法)。2122POJ1088滑雪Michael喜歡滑雪百這并不奇怪,因為滑雪的確很刺激。可是為了獲得速度,滑的區(qū)域必須向下傾斜,而且當你滑到坡底,你不得不再次走上坡或者等待升降機來載你。Michael想知道載一個區(qū)域中最長底滑坡。區(qū)域由一個二維數(shù)組給出。數(shù)組的每個數(shù)字代表點的高度。下面是一個例子
12345
161718196
152425207
142322218
131211109
一個人可以從某個點滑向上下左右相鄰四個點之一,當且僅當高度減小。在上面的例子中,一條可滑行的滑坡為24-17-16-1。當然25-24-23-...-3-2-1更長。事實上,這是最長的一條。23POJ1088滑雪Input輸入的第一行表示區(qū)域的行數(shù)R和列數(shù)C(1<=R,C<=100)。下面是R行,每行有C個整數(shù),代表高度h,0<=h<=10000。Output輸出最長區(qū)域的長度。24這個搜的重復的過程太多了,交到OJ上給個TLE25記憶化搜索26BFS廣搜例子:你的眼鏡掉在地上以后,你趴在地板上找。你總是先摸最接近你的地方,如果沒有,再摸遠一點的地方……27BFS程序基本結(jié)構(gòu)定義一個隊列;起始點加入隊列;while(隊列不空){取出隊頭結(jié)點;若它是所求的目標狀態(tài),跳出循環(huán);否則,從它擴展出子結(jié)點,全都添到隊尾;}若循環(huán)中找到目標,輸出結(jié)果;否則輸出無解;28POJ2243KnightMoves國際象棋棋盤上有一個馬,要從起點跳到指定目標,最少跳幾步?輸入:a1h8輸出:Togetfroma1toh8takes6knightmoves.
abcdefgh12345678h8a129跳馬規(guī)則abcdefgh12345678在2×3的矩形里:30例如:從a1到e4當目標出現(xiàn)在所擴展出的結(jié)點里,結(jié)果就找到了。Togetfroma1toe4takes3knightmoves.
abcdefgh1234567803321322312332233323333333233332313233雙向BFSabcdefgh123456780212212122211112012從起點、終點同時開始雙向BFS,有效地提高了時空效率。從起點找2步能跳到的點從終點找1步能跳到的點34POJ1745Divisibility輸入N、K,然后輸入N個整數(shù),N個整數(shù)可列出若干加減運算式;若存在一個算式,它的值能被K整除,輸出“Divisible”,否則輸出“Notdivisible”.輸入:247
175-211545
175-2115輸出:Divisible
Notdivisible35{17,5,-21,15}1755-21-21-21-211515151515151515+++17+5+-21+15++++-------17-5+-21-1536最壞情況N=10000,二叉樹有10000層,結(jié)點總數(shù)210000-1。不可能枚舉所有表達式本題的目標:判斷葉子結(jié)點上是否有值能被k整除=>判斷是否有值,除以k的余數(shù)為零。計算中間值取余,不影響結(jié)果。
(a+b)%k=(a%k+b%k)%k因此只需記錄對k的余數(shù)。2<=k<=100,每層結(jié)點最多100個,不是指數(shù)級增加。3747175-2115每層最多7個結(jié)點(定義數(shù)組):首先加入起點,17%7=3擴展第2層結(jié)點(3+5)%7=1(3–5+7)%7=51234560+-擴展第3層結(jié)點(1+-21)%7=1(1–-21)%7=1(5+-21)%7=5(5–
-21)%7=51234560擴展
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 孕期濕疹的健康宣教
- 地震勘探數(shù)據(jù)處理系統(tǒng)相關(guān)行業(yè)投資方案范本
- 水務工作全員參與的機制建設計劃
- 嗜酸性粒細胞增多癥的診斷、風險分層和治療
- 《設施農(nóng)業(yè)》課件
- 衛(wèi)生監(jiān)督信息報告系統(tǒng)試點培訓課件職業(yè)衛(wèi)生
- 《信息資源優(yōu)化配置》課件
- 《設備管理培訓教材》課件
- 創(chuàng)建社團參考計劃書范文5篇
- 八年級政治上冊單元評價檢測課件
- 2024年廣東省深圳市中考英語適應性試卷
- 公共事業(yè)管理概論試卷6套含答案(大學期末復習資料)
- 《AIGC與新媒體運營技能實戰(zhàn)(慕課版)》-教學大綱
- 垃圾分類小學生課件
- 掘進機檢修工理論知識考試卷及答案
- 市政道路維修改造工程施工設計方案
- 一年級科學上冊評價方案宮艷春
- 《戒了吧-拖延癥》課件
- 對話大國工匠 致敬勞動模范學習通超星期末考試答案章節(jié)答案2024年
- 5.1 中國外交政策的形成與發(fā)展 課件高中政治統(tǒng)編版選擇性必修一當代國際政治與經(jīng)濟
- 2024年年度采購工作計劃范文(三篇)
評論
0/150
提交評論