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

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

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

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

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

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

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