歡迎來到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁 裝配圖網(wǎng) > 資源分類 > PPT文檔下載  

北京大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽.ppt

  • 資源ID:11492831       資源大?。?span id="n89qiob" class="font-tahoma">337.50KB        全文頁數(shù):23頁
  • 資源格式: PPT        下載積分:9.9積分
快捷下載 游客一鍵下載
會員登錄下載
微信登錄下載
三方登錄下載: 微信開放平臺登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要9.9積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機(jī)號,方便查詢和重復(fù)下載(系統(tǒng)自動(dòng)生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號:
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預(yù)覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說明有答案則都視為沒有答案,請知曉。

北京大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽.ppt

問題求解與程序設(shè)計(jì)第七講搜索,李文新2004.22004.6,內(nèi)容提要,搜索討論1011stick討論1054thetroublesomefrog參考王知昆的冬令營報(bào)告作業(yè),搜索的一般概念,在解空間中嘗試所有可能,找出滿足條件的取值回顧填數(shù)游戲:1-9填在3*3的表格中,使得行、列、對角線的和均為15。方程組搜索逐一嘗試+剪枝,題目討論,1011stick,題目討論,TheTroublesomeFrogIOI2002day1task1,問題,稻田,問題,青蛙從外面跳入稻田,踩過一些禾苗,后,跳出稻田。,問題,蛙路:一個(gè)方向,等間距,大于等于3個(gè)點(diǎn)不同蛙路:可以方向不同,間距不同,問題,許多青蛙跳過稻田,形成多條蛙路,不同蛙路可以踩過同一作物。,問題,青蛙每天早上踩壞稻田,早上人們發(fā)現(xiàn)稻田有若干株作物被踩壞,但不知多少青蛙來過。也有不在蛙路上的被踩壞的作物。,問題,問,給定一塊被踩壞的稻田,求可能的最長的蛙路上被踩壞的作物的數(shù)目。,輸入,第一行整數(shù)R和C,稻田的行數(shù)和列數(shù)第二行整數(shù)N,表示被踩壞的作物總數(shù)。后續(xù)N行,每行兩個(gè)整數(shù)i,j為被踩壞的作物的行和列的位置:1<=i<=R,1,1<=j<=C。每個(gè)被踩壞的作物只出現(xiàn)一次。,輸出,單個(gè)整數(shù)-表示最長可能蛙路上踩壞的作物數(shù)目,樣例,Figure-4,問題的解,這道題目也就是說,在給出的n個(gè)點(diǎn)中找出一些點(diǎn)的序列來,使得每一個(gè)點(diǎn)相對于上一個(gè)點(diǎn)的坐標(biāo)都是一個(gè)相同的向量,且第一個(gè)點(diǎn)減去這個(gè)向量和最后一個(gè)點(diǎn)加上這個(gè)向量后均落在方格的外面。,問題的解,我們先對這些點(diǎn)按照坐標(biāo)排序。然后依次循環(huán)出要求的序列中的第一個(gè)和第二個(gè)點(diǎn),這樣我們就知道后一個(gè)點(diǎn)相對于前一個(gè)點(diǎn)的坐標(biāo)是多少了。然后我們依次用第二個(gè)點(diǎn)加上這個(gè)坐標(biāo)的出第三個(gè)點(diǎn),第三個(gè)點(diǎn)加上這個(gè)坐標(biāo)得出第四個(gè)點(diǎn)等等。當(dāng)然,我們還需要判斷一下這求出來的第三個(gè)、第四個(gè)點(diǎn)是否在給定的點(diǎn)內(nèi)。,問題的解,由于每個(gè)點(diǎn)的上一個(gè)點(diǎn)/下一個(gè)點(diǎn)最多只能有n種選擇,故一個(gè)點(diǎn)最多屬于n條不同的蛙路。這樣,對于某個(gè)確定的點(diǎn)來說,它的所有可能的下一個(gè)需要判斷的點(diǎn)至多有n個(gè)。這樣因?yàn)榕袛嘁粋€(gè)點(diǎn)在不在給定的點(diǎn)內(nèi)只需要O(1)的復(fù)雜度,所以我們只需要O(n2)的時(shí)間就可以得出問題的解答。由于這個(gè)算法需要一個(gè)r*c的表來保存點(diǎn)在方格中的存在狀態(tài),故空間復(fù)雜度為O(n2)。,問題的解,需要注意的是,蛙路中的點(diǎn)數(shù)少于3個(gè)的時(shí)候是不考慮的。所以這個(gè)時(shí)候的蛙路中的點(diǎn)數(shù)應(yīng)該按照0來算。,實(shí)現(xiàn)細(xì)節(jié),Frogvsfrog平面上點(diǎn)的表示Frog20有冗余代碼Frog21去掉冗余Frog22compare判斷Frog23改變表達(dá)式寫法Frog24增加剪枝Frog25不太好的剪枝順序Frog26較好的剪枝順序,測試數(shù)據(jù),No.N,(R*C)DescriptionSolution118,(6*7)Sampledatainthetaskdescription4210,(10*10)Manuallydesigned5325,(50*50)Manuallydesigned13450,(10*10)SeveralLines+randompoints105100,(20*20)modifiedrandompointset106300,(30*30)modifiedrandompointset157500,(55*55)SeveralLines+randompoints288500,(100*100)Specialcasefornosolution091000,(100*100)SeveralLines+randompoints34101000,(1000*1000)SeveralLines+randompoints250112000,(50*50)Random(uniform)points25122000,(100*200)SeveralLines+randompoints33132000,(1000*2000)SeveralLines+randompoints333,測試數(shù)據(jù),143000,(60*60)Uniformlyrandompoints31153000,(500*500)Xshapesandrandompoints500163000,(5000*1)Horizontalline20173000,(5*1000)SeveralLines+randompoints17184000,(100*100)Randompoints(uniformly)34194000,(200*20)Verydensepointsset200204000,(1000*1000)SeveralLines+randompoints500214000,(5000*5000)SeveralLines+randompoints311225000,(100*100)Chessboardstyle100235000,(1000*1000)SeveralLines+randompoints334245000,(3000*3000)Irregularlinearpoints1000255000,(5000*5000)Modifiedrandompoints72,參考資料,王知昆的冬令營報(bào)告,作業(yè),10111054選做,

注意事項(xiàng)

本文(北京大學(xué)ACM國際大學(xué)生程序設(shè)計(jì)競賽.ppt)為本站會員(max****ui)主動(dòng)上傳,裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!