國(guó)家集訓(xùn)隊(duì)2006論文集 龍凡

《國(guó)家集訓(xùn)隊(duì)2006論文集 龍凡》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、一類猜數(shù)問(wèn)題的研究長(zhǎng)沙市雅禮中學(xué)龍凡猜數(shù)問(wèn)題猜數(shù)問(wèn)題是信息學(xué)競(jìng)賽中一種常見(jiàn)的類似博弈的問(wèn)題?；拘问剑捍嬖谝粋€(gè)被猜數(shù)X。每次可以猜一個(gè)數(shù)Y，之后會(huì)返回X和Y的關(guān)系，你要利用返回的信息來(lái)猜出X。本文著重討論的一類猜數(shù)問(wèn)題是：返回的信息是X和Y的大小關(guān)系?；镜牟聰?shù)問(wèn)題下面就是一個(gè)本文討論范疇內(nèi)的最基本的猜數(shù)問(wèn)題：被猜數(shù)X是1到N范圍內(nèi)的整數(shù)，每次你可以詢問(wèn)一個(gè)整數(shù)Y和X的大小關(guān)系。給出N，請(qǐng)問(wèn)在最壞情況下至少需要幾次才能保證猜出X。上題應(yīng)用大家熟悉的二分的思想可以輕松解決。上面我們總共耗費(fèi)了3次詢問(wèn)。這只是作為一個(gè)二分詢問(wèn)的例子。對(duì)于此題，應(yīng)用二分法，作適當(dāng)?shù)臄?shù)學(xué)分析，就可以得到最少的詢

2、問(wèn)次數(shù)為：基本的猜數(shù)問(wèn)題設(shè)N=7,X=5。應(yīng)用二分的思想詢問(wèn)：12345671.詢問(wèn)Y=42.得到X>Y3.詢問(wèn)Y=64.得到X

3、后才會(huì)得到回答。同時(shí)你和同學(xué)約定，你要盡量避免得到X>Y的回答。（你可以認(rèn)為，X是他的考試成績(jī)之類的?）當(dāng)你累計(jì)得到第K次X>Y的回答的時(shí)候，你就輸了。已知X是1到N之間的整數(shù)?，F(xiàn)在給出N、K，請(qǐng)問(wèn)最少要多少秒才能保證猜出X。問(wèn)題的提出下面是一個(gè)N=6,K=3時(shí)的實(shí)例：詢問(wèn)回答時(shí)間1s2s3s4s5s上面的詢問(wèn)，總共用了5s。期間得到了一次X>Y的回答。K=3沒(méi)有超過(guò)限制。Y=3Y=5Y=4Y=4Y=6X<6X<5X=4X>3…初步分析我們現(xiàn)在的問(wèn)題并不是如何猜，而是在最壞的情況下至少要多少秒才能猜出X來(lái)。本題沿用二分的老思路是行不通的?？梢钥闯觯m然僅僅是在基本猜數(shù)問(wèn)題上進(jìn)行了些許加

4、強(qiáng)，就成了一個(gè)非常棘手的問(wèn)題。為了解決這個(gè)問(wèn)題，讓我們重新從最原始的猜數(shù)問(wèn)題開(kāi)始分析。123當(dāng)N=3，K=1并且X=3時(shí)。詢問(wèn)Y=2，必然得到X>Y回答。不可以二分！前面我們是通過(guò)二分的方法來(lái)解決此題的。至于“二分”這個(gè)思路的來(lái)源，更多的是源自猜測(cè)、及平時(shí)做題的經(jīng)驗(yàn)。下面就來(lái)系統(tǒng)的分析為什么“二分”是正確的。通過(guò)分析，希望能找到一個(gè)更具有普遍性的方法解決前面的題目。讓我們嘗試用遞推的方法來(lái)分析問(wèn)題。被猜數(shù)X是1到N范圍內(nèi)的整數(shù)，每次你可以詢問(wèn)一個(gè)整數(shù)Y和X的大小關(guān)系。給出N，請(qǐng)問(wèn)在最壞情況下至少需要幾次才能保證猜出X。再看基本猜數(shù)問(wèn)題再看基本猜數(shù)問(wèn)題設(shè)f(i)表示i次詢問(wèn)最大能夠處理的

5、區(qū)間長(zhǎng)度。即若N=f(i)，則只需要i次就可以猜出X。根據(jù)上面定義，若f(j)≥N。且f(j-1)Y時(shí)，為了要在剩下的I-1次詢問(wèn)中得到答案，大于Y的區(qū)域長(zhǎng)度不能超過(guò)f(i-1)。Xf(i)=2i-1應(yīng)用遞推的方法間接的證

6、明了前面的結(jié)論，即最少詢問(wèn)的次數(shù)為：更重要的是：對(duì)于這類試題來(lái)說(shuō)，上面這種應(yīng)用遞推的分析問(wèn)題的方法具有很強(qiáng)的推廣性。二次分析通過(guò)上面的分析，基本的猜數(shù)問(wèn)題已經(jīng)完整的解決了?，F(xiàn)在回到原題的研究?，F(xiàn)在直接分析原題仍然有點(diǎn)困難，注意到原題相比基本猜數(shù)問(wèn)題有兩個(gè)加強(qiáng)：不妨先把這道題目拆開(kāi)，分部解決。1.累計(jì)獲得K次X>Y的答案就游戲結(jié)束。2.本次的回答要在下一個(gè)提問(wèn)之后獲得。猜數(shù)問(wèn)題的加強(qiáng)被猜數(shù)X是1到N范圍內(nèi)的整數(shù)，每次你可以詢問(wèn)一個(gè)整數(shù)Y和X的大小關(guān)系。附加上條件：累計(jì)獲得K次X>Y的答案就游戲結(jié)束。給出N、K，請(qǐng)問(wèn)在最壞的情況下至少需要幾次詢問(wèn)才能保證猜出X。對(duì)于這個(gè)問(wèn)題，可以借鑒前面的

7、經(jīng)驗(yàn)，應(yīng)用遞推的方法來(lái)求解。被猜數(shù)X是1到N范圍內(nèi)的整數(shù)，每次你可以詢問(wèn)一個(gè)整數(shù)Y和X的大小關(guān)系。你要盡量避免詢問(wèn)比X小的Y值，因?yàn)槔塾?jì)獲得K次X>Y的答案就游戲結(jié)束。給出N、K，問(wèn)在最壞情況下至少需要詢問(wèn)幾次才能保證猜出X。猜數(shù)問(wèn)題的加強(qiáng)類似的，我們?cè)O(shè)f(i,j)表示用i次詢問(wèn)，在累計(jì)j次X>Y的回答就游戲結(jié)束的情況下，最大能處理的區(qū)間長(zhǎng)度。如果我們能夠快速求出f，問(wèn)題也就容易解決了。找到最小的數(shù)Ans，滿足f(Ans,k)≥N，f(Ans-