信息學(xué)競(jìng)賽中問題求解題常見考查題型分析

1、信息學(xué)競(jìng)賽中問題求解題常見考查題型分析信息學(xué)競(jìng)賽中問題求解題常見考查題型分析問題求解是信息技術(shù)競(jìng)賽初賽中常見題型，它共兩題，每題5分，共10分。諸如尋找假幣、博弈原理、抽屜原理、容斥問題、排列組合問題、邏輯推理、遞推關(guān)系等問題出現(xiàn)在問題求解中，但是在實(shí)際的競(jìng)賽中，問題求解得分率往往是不高的，下面我對(duì)問題求解的題型進(jìn)行了一下探索。一、尋找假幣問題一、尋找假幣問題有n（n≥3）個(gè)硬幣，其中一個(gè)是假幣，已知假幣的重量比其他的要重一些，你有一架

2、天平?，F(xiàn)在要稱出哪個(gè)假幣來(lái)。解析：解析：首先我們先來(lái)考慮最簡(jiǎn)單的問題1。為了方便敘述，把n個(gè)硬幣按12…n順次編號(hào)。若n=3，把一號(hào)硬幣放在天平左邊、二號(hào)硬幣放在天平右邊。如果天平：1、左偏，一號(hào)重，是假幣。2、右偏，二號(hào)重，是假幣。3、保持平衡，那么一、二都是正常的硬幣，因此就只有可能三號(hào)硬幣是假幣了。因此n=3，至多一次就能稱出哪個(gè)是假幣。記作f(3)=1。下面考慮n=9。把所有的硬幣分成三組：A123B456C789。A組的硬幣放

3、在左邊、B組放在右邊。如果天平：1、左偏，則假幣在A組里面。2、右偏，則假幣在B組里面。3、保持平衡，假幣在C組里面。無(wú)論在哪個(gè)組里面，我們已經(jīng)把假幣的范圍從“9”縮小到了“3”，也就是減少到原來(lái)的13。之前我們已經(jīng)研究過，3個(gè)硬幣1次就能稱出來(lái)，故而f(9)=2。此題的判定樹是這樣一棵樹：1、葉子節(jié)點(diǎn)代表一種可能的結(jié)果。2、非葉子節(jié)點(diǎn)代表一次稱量。3、非葉子節(jié)點(diǎn)至多有三個(gè)兒子，分別代表天平的左偏、右偏、平衡三種情況。任意一種稱量方案都

4、能唯一的表示成一棵判定樹；反過來(lái)一棵判定樹也唯一對(duì)應(yīng)一種稱量方案。容易看出判定樹的深度就是稱量次數(shù)。這就是我們之所以引進(jìn)它的原因。做出判斷之前，誰(shuí)也無(wú)法預(yù)知哪個(gè)硬幣是假幣，每個(gè)都有可能是我們的目標(biāo)；因此一個(gè)有意義的判定樹應(yīng)該具有至少n個(gè)葉子節(jié)點(diǎn)。n個(gè)葉子節(jié)點(diǎn)的樹的深度h≥，故而可以證明，f(n)=是最??n3log??n3log優(yōu)的。我們的結(jié)論是：有我們的結(jié)論是：有n（n≥3）個(gè)硬幣，其中一個(gè)是假幣，假幣的重量比其）個(gè)硬幣，其中一個(gè)是假

5、幣，假幣的重量比其他的要重一些。給一架天平，至少稱他的要重一些。給一架天平，至少稱次，就能找出那個(gè)假幣。次，就能找出那個(gè)假幣。??n3log具體的方案是將硬幣每次都盡量均勻的三分。讓我們總結(jié)一下?！叭帧笔钦麄€(gè)解法的核心。我們選擇三分，而不是二分或者四分是有原因的，它的本質(zhì)是由判定樹的特殊結(jié)構(gòu)——三叉樹——所決定的。同時(shí)還必須注意一點(diǎn)，我們?cè)谌值臅r(shí)候有兩個(gè)字很講究：“均勻”。實(shí)際上h≥中的“=”當(dāng)且僅當(dāng)硬幣被均勻的分配時(shí)才能達(dá)到。??

6、n3log這里說的“均勻”是指“在最壞情況下獲得最好的效果”。因?yàn)橐豢脴涞纳疃仁怯伤?jié)點(diǎn)兒子中深度最大的兒子決定的，為了使得整個(gè)樹深度最小，我們就要?jiǎng)?wù)必使得深度最大的兒子深度最小，這就是“均勻”分配的理論根據(jù)。練習(xí)：練習(xí)：第12屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽題屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽題現(xiàn)有80枚硬幣，其中有一枚是假幣，其重量稍重，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出假幣？你還要指出