冬令營解題報告猜數guess_第1頁
冬令營解題報告猜數guess_第2頁
冬令營解題報告猜數guess_第3頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、猜數解題浙江問題簡述本題是一個交互式的題目，會有重復的數字。的目標是猜若干個長度為 Len 的數，并且保證這個數不可以與庫進行交互，每次可以猜一個各位不同的數，庫會將猜的數與進行比較，并以整數 P 和整數 Q 來回答，其中 P 表示所猜的數字和位置都是對的數的個數，Q表示不管位置對還是不對，所猜的數字與被猜的數字有幾個數字是相同的。的目標就是用最少的次數猜出設定的。題目中給出了 10 個測試點的信息：算法分析這個問題在冬令營師的課上已經有了相當詳細的，那么這里直接師課上的成果。算法即為篩法。假設要猜的數的長度為 Len，則有測試點12345678910Len234567891010被猜數的數目

2、100100100100100202020120可以發(fā)現(xiàn)，僅僅隨機猜數就可以得到 95100 的高分。二、估價函數法的目標是使得猜了這個數之后候選的規(guī)模收斂的盡量快。用函數猜測次數1532521543587666220得分情況9109109109109101010101010將 Y 附值給 X。通過若干次調整，就可以得到一個 P = Len 的 X，也就是直接這么做需要猜的次數相當大，這里有兩個優(yōu)化：了。優(yōu)化一：針對第一步：如果位置 p 上的數字 Xp換成了 k 之后得到的 Q，如果滿足 Q = Q + 1，則 Xp必然不出現(xiàn)在中，而 k 必然出現(xiàn)在中。同樣，如果滿足 Q = Q 1，則 Xp

3、必然在中，而 k 肯定不在。這樣一來就可以得到一些信息，以后隨機位置的時候就不需要選擇位置 k 了，隨機數字也不用去隨機那些被確定為肯定不在中的數字，這樣便減少了猜測次數。優(yōu)化二：針對第二步：跟優(yōu)化一是一樣的，就是把那些能確定的位置就確定下來。不妨設當前交換了 i 位置和 j 位置后得到 P。如果 P = P + 2，那么交換后 i 位置和 j 位置上的數字都與吻合；同樣，如果 P = P 2，則交換前的i 位置和 j 位置都與吻合。其中的原因是顯而易見的。這樣就確定了 i 位置和 j 位置，以后就不需要選擇這些位置了，也減少了猜測次數。本算法時間復雜度不好估計，但經測試，實際運行速度相當快。小結篩選，是解決問題的一種。在本題中，應用這一，不斷將候選的規(guī)?？s小，從而猜得目標。對問題進行拓

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論