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

北京大學ACM國際大學生程序設計競賽.ppt

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

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

北京大學ACM國際大學生程序設計競賽.ppt

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

注意事項

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

溫馨提示:如果因為網速或其他原因下載失敗請重新下載,重復下載不扣分。




關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服 - 聯系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網版權所有   聯系電話:18123376007

備案號:ICP2024067431-1 川公網安備51140202000466號


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