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

尋找問有n（n≥3）個硬幣，其中一個是，已知的重量比其他的要重一些，你有一架天平?，F(xiàn)在要稱出哪個來。1。為了方便敘述，把n1,2,…,nn=3，把一號硬幣放在天平左邊、二號硬幣放在天平右邊。如果天平：右偏，二號重，是保持平衡，那么一、二都是正常的硬幣，因此就只有可能三號硬幣是了。因此n=3，至多一次就能稱出哪個是。記作f(3)=1。n=9。把所有的硬幣分成三組：A{1,2,3},B{4,5,6},C{7,8,9}。AB左偏，則在A組里面。右偏，則在B組里面。保持平衡，在C組里面。無論在哪個組里面，我們已經(jīng)把的范圍從“9”縮小到了“3”，也就是減少到原來的1/3。之前我們已經(jīng)研究過，3個硬幣1次就能f(9)=2。1.1f(3n)=n。證明：n=1,2n=kf(3k)=kn=k+13k+1A,B,C，使得|A|=|B|=|C|=3kAB左偏，在A右偏，在平衡，在無論哪種結(jié)果，我們都把的范圍縮小到了3k個硬幣里面。而f(3k)=k，故而f(3k+1)=k+1。1.11.2f(n)=log31.1nmod30,1,2須注意到log3n我們采取的方案是每次將硬幣盡量均勻的三分，這樣做的根據(jù)就是天平只有三種結(jié)果：左偏、右偏、平衡。于是就能保證無論在哪1/3log3n應(yīng)該就是最優(yōu)解了。為了更加嚴(yán)格的證明log3n的最優(yōu)性，我們引進(jìn)判定樹的概念。n=9>><<>>=>

<>< <><nh≥log3n，故而可以證明，f(n)=log3n我們的結(jié)論是：有n（n≥3）個硬幣，其中一個是 同時還必須注意一點，我們在三分的時候有兩個字很講究：“均勻”。實際上hlog3n中的“=”當(dāng)且僅當(dāng)硬幣被均勻的分配時才練習(xí)：第12屆青少年信息學(xué)聯(lián)賽初賽題現(xiàn)有80枚硬幣，其中有一枚是，其重量稍重，所有真幣的重量都相同，如果使用不帶砝碼的天平稱重，最少需要稱幾次，就可以找出？你還要第1次的稱重方法。請寫出你的結(jié)果： 答案：4：27，27，262有若干堆任意數(shù)目的小石子{a1，a2，…，am}(m≥11、2、3k(1≤k≤min{a1，a2，…，am})顆石子，把石子取完的人為勝者。個分量ai(1≤i≤m)ai′，即{a1，a2，…，ai，…，am；k}—→{a1，a2，…，ai′，…，am；k}(0≤ai′<ai)，我們把這種取一次石子使數(shù)組發(fā)生的變換稱為T變換根據(jù)現(xiàn)成論先驅(qū)馮(Vonann)“完全確定信息游戲必定存在一種確定的獲勝策略”的經(jīng)典理論，要么對先取者存在某種取法，即某個T1100110取勝策略的一方在{a1，a2，…，am；k}中也有取勝策略。證明在{a1′，a2′，…，am′；k}中有獲勝策略的一方，對于大于k的分量ai(i=1，2，…，mai≡ai′(modk+1a(1≤≤k)k+1-ak+1in(n≥1ai=ai′+n(k+1)ai′，故在{a1′，a2′，…，am′；k}中有取勝策略的一方在{a1，a2，…，am；m{a1，a2，…，am}(m≥1Tai(1≤i≤m)減小ai′，即{a1，a2，…，ai，…，am}T{a1，a2，…，ai′，…，am}(0≤ai′<ai)。元數(shù)組nj(1≤j≤lmnj(1≤j≤l)，中有一個數(shù)為奇數(shù)，則稱之為非偶數(shù)組。32010301151012n2n1=1，所以{2，3，5}是非偶數(shù)組。32，3，1}：2103111012nj(j=1，2)為偶數(shù)，則{2，3，1}為偶數(shù)組。偶數(shù)組與非偶數(shù)組在T偶數(shù)組經(jīng)過一次T對于非偶數(shù)組，一定可以找到某一個Tmm因為給定的m22、3、6，兩人輪流取，取完的人為勝者，若甲先乙后，誰取勝？2010301161101n1n22}或{1，1}，乙再取后，甲總能確保獲勝。例3：第12屆青少年信息學(xué)聯(lián)賽初賽題現(xiàn)有5堆石子,石子數(shù)依次為3，5，7，19，50，甲乙兩人輪流從任一堆中任（每次只能取自一堆，不能不?。?取最后一顆石子的一方獲勝。甲先取，問甲有沒有獲勝策略（即無論乙怎樣取，甲只要不，都能獲勝）？如果有，甲第一步應(yīng)該在哪一堆里取多少？請寫出你的結(jié)果： 15323243×25a、b、c15abc25≡7(mod6)，根據(jù)游戲Ⅰ的策略{25，25，25；5}中有獲勝策略的一方在{7，7，7；5}中也有獲勝方法，又把石子由圖中所示{3，“屜最是由19紀(jì)德數(shù)家萊Dirhle）用解數(shù)問的所又“萊理也稱鴿1091、如果把n+1n證明：（用反證法）1nnn+11313122224330123335153（襪子無左、右之6224261，236＋2＋2=10342，只要取出的球數(shù)多于（4-1）×3=9104（同一顏色）里的球?！纠?】.現(xiàn)有64只乒乓球，18個乒乓球盒，每個盒子里最多可以放6只乒乓球，至少有 球，32…36，18抽屜原理還可以反過來理解：假如把n＋1n22（2或2個以上的蘋果”相反），那么，每個抽屜最多只放1個蘋果，n個抽屜最多有n個蘋果，與“n+1個蘋果”的條件。運用抽屜原理的關(guān)鍵是“制造抽屜”。通常，可采用把n123319A={0，1，2，3，……，90，1，2，…9為A并集：由所有屬于集合ABA，BA∪B，記號“∪”讀作“并”。A∪BAB”，用圖表示為圖中陰影部分表示集合A，BA∪B。6A={1，2，3，6}，10B={1，2，5，10交集：A、BA，又屬于BAB“A∩B”，讀作“A交B”，如圖陰影表示：6A={1，2，3，6}，10B={1，2，5，10A∩B={1，2}。原理一：給定兩個集合AB，要計算A∪B第一步：先求出∣A∣+∣B∣（或者說把A，B）；總結(jié)為：|A∪B|=∣A∣+∣B∣-原理二：給定三個集合A，B，C。要計算A∪B∪C即有以下∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣B∩C|C∩A|+|A∩B∩C∣s集新詞概多如合元、限、限、法描法子、子、集非集、集補交、集等新系符多如于不于包、含、含真含、等不等相、并互補∈、 、N、N、、QR∩∪、C、I＝≠…等這新念關(guān)，而象在千萬中應(yīng)抓“素個鍵，因集是元確的“、、、、、”合都通元來義。合元的征“定，互異s12023A={202B={20323∣A∪BB={3，6，9，…186|B|=62：本題可直觀地用圖示法解答如圖,其中,圓A202B2036,12,1823A∩BA∪B2902590219038解：設(shè)A90B={90那么，集合A∪B90點評：解決本題首先要根據(jù)題意，設(shè)出集合A，B，并且會表示A∪B，A∩B339，3725解：設(shè)A={打籃球的同學(xué)}；B={跑步的同學(xué)}A∩B={既打籃球又跑步的同學(xué)}423271：設(shè)A={數(shù)學(xué)小組的同學(xué)}，B={語文小組的同學(xué)}，C={外語小組的同學(xué)}，A∩B={數(shù)學(xué)、語文小組的同學(xué)}，A∩C={參加數(shù)學(xué)、外語小=54（人2：設(shè)A、B、CⅦ（即A∩B∩C）表示三個小組都24-2=2（人）。區(qū)域Ⅵ表示僅參加數(shù)學(xué)7-2=5（人）5-2=3（人）。區(qū)域Ⅰ表2例5學(xué)校教導(dǎo)處對100名同 ，結(jié)果有58人喜歡看球賽，有38人喜歡看戲劇，有52人喜歡 賽又喜歡看戲?。ǖ幌矚g看）的有6人，既喜歡看 又喜歡看戲?。ǖ幌矚g看球賽）的有4人，三種都喜歡的有12人。問有多少同學(xué)只喜歡看？有多少同學(xué)既喜歡看球賽又喜歡看 解法1：畫三個圓圈使它們兩兩相交，彼此分成7部分（如圖）這三個圓圈分別表示三種不同 12人，把12填在三個圓圈的公共部分內(nèi)（圖中陰影部分），其它6部分填上題目中所給出的不同 人數(shù)要經(jīng)過簡單的計算）其中設(shè)既喜歡看又喜歡看球賽的人數(shù)為χ，這樣，全班同學(xué)人數(shù)就是這7部分人數(shù)的和，即只喜歡看的人數(shù)36-解法2：設(shè)A={喜歡看球賽的人}，B={喜歡看戲劇的人}，C={喜歡看的人}，依題目的條件有|A∪B∪C|=100，|A∩B|=6+12=18（這里12），|B∩C|=4+12=16，|A∩B∩C|=12，再設(shè)|A∩C|=12+χ由容斥原理二：|A∪B∪C所以既喜歡看又喜歡看球賽的人數(shù)為14，只喜歡看的人數(shù)為221nm1m2m法，……，在第n

Nm1

nmm2種不同的方法，……，做第步有m種不同的方法，那么完成這件事有Nm1m2 mn種不同的方排列的概念：從nm（mn）個元素（這里的被取元素各不相同）按照一定的順序排成一列，叫做從n個不m個元素的一個排列排列數(shù)的定義：從nm（mn）個元素的所有排列的個數(shù)叫做從nmAmAnnn

Amn(n1)(n (nm

m,nN6

1nn0

Anm(nAn

組合數(shù)的概念：從nmmCm

符號n

n(nn(n1)(n (nmCmnA A組合數(shù) nCmn或

m!(nm(nmN且mCm

C011組合數(shù)的性質(zhì)1： ．規(guī)定： CmC2：n1

CCn+CCAa1a2a3,an}nr個元素排在一個圓環(huán)上，叫做一個圓排列（或叫環(huán)狀排列圓排列有三個特點：（i）無頭；（ii）按照同一方向轉(zhuǎn)換后仍是同一排列；（iii）兩個圓排列只有在元素不同或者元素雖然相 Aa1

,

,,

Pr}nrnrmmnmnnp1p2ps個元素相同（p1p2psn），這n

np個元素，允許所取的元素重復(fù)出現(xiàn)1,2,pnpnpHpCr n(11344C3abcd12解：兩個元素排在一起的問題可用“”法解決，先將甲乙二人看作一個元素與其他五人進(jìn)行排列，并考慮甲乙二人的順序，所以共 練習(xí)：5個男生3個排成一排,3個要排在一起,有多少種不同的排法PP分析此題涉及到的是排隊問題,對于有特殊的限制,因此,是特殊元素,并且要求她們要相鄰,因此可以將她們看成是一個元素來PP 因為要排在一起,所以可以將3個看成是一個人,與5個男生作全排列,P6

內(nèi)部也有

6 27 種排法練習(xí)：學(xué)校組織老師學(xué)生一起看，同一排票12張。8個學(xué)生，4個老師，要求老師在學(xué)生中間，且老師互不相鄰，共有多少解

P874PP8

P7種選法.根據(jù)乘法原理P

87有些問題直接法考慮比較難比較復(fù)雜，或分類不清或多種時，而它的往往比較簡捷，可考慮用“排除法”，先求出它的,再從整 個解：從7個點中取3個點的取法有 種，但其中正六邊形的對角線所含的中心和頂點三點共線不能組成三角形，有3條，所以滿足 －3＝32個.練習(xí)435CCCC解435

43

401

C C例4．1名老師和4名獲獎學(xué)生排成一排照像留念，若老師不排在兩端，則共有不同的排 種 ＝72種不同的排法. 種 種排法，而其余7名隊員選出2名安排在第二、四位置，有 法，所以不同的出場安排共有＝252種.例6．某班新年聯(lián)歡會原定的5個已排成單，開演前又增加了兩個新.如果將這兩個插入原單中，那么不同插法的種數(shù)為（A） 22262A種。故不同插法的種數(shù)為626+A2A1=42，故選A26例7．12名同學(xué)分別到三個不同的路口進(jìn)行車流量的，若每個路口4人，則不同的分配方案共有 解：本試題屬于均分組問題。則12名同學(xué)均分成3組共有 種，故選A。8．43有（） D．6解C2A1·A2,故不同的種植方法共有A1·C2·A2=12

9101、2、3書之間的6個“空檔”內(nèi)插入兩個相同“I”（一般可視為“隔板”）共有 種插法，即有15種分法。108121分析此題若直接去考慮的話,就會比較復(fù)雜.但如果其轉(zhuǎn)換為等價的其他問題,就會顯得比較清楚,方法簡單,結(jié)果容易理解1281211777相同的黑球,每個空檔最多放一個,即可將白球分成8份,顯然有 種不同的放法,所以名額分配方案有 種77輯推理問題，處理這類問題，要從一些關(guān)聯(lián)的條件出發(fā)，應(yīng)用某些數(shù)學(xué)知識，甚至日常生活，依據(jù)一定的思維規(guī)律（機(jī)智靈活、準(zhǔn)邏輯推理問題條件撲朔迷離，層次紛紜，沒有一定的定理可以依據(jù)，無現(xiàn)成可用，無模式可循，靠的是邏輯推理?？僧嬁驁D、住在某個旅館的同一房間的四個人A、B、C、D正在聽一組流行音樂，她們當(dāng)中有一個人在修指甲，一個人在寫信，一個人躺在，另B不躺在，也不在修指甲如果A不躺在，那么D不在修指甲D不在看書，也不躺在。由1、2、4、5知，既不是A、B在修指甲，也不是C在修指甲，因此修指甲的應(yīng)該是D；但這與3的結(jié)論相，所以3的前提肯定不成立，即A應(yīng)該是躺在；在4中C既不看書又不修指甲，由前面分析，C又不可能躺在，所以C是在寫信；而B則是在看書。5.A、B、C、D C：是ABD：是B由表可知，若是A3B54、3、2、1由多到少排列著五名學(xué)生，A、B、C、D、EA24CE35D4講解:先從五人的總分入手，再扣掉AB、C、D、EE55×(1+2+3+4+5)=75因A24B、C、D、E75－24=51又E8E（還有三科）11 E811E1C132135A、EC31E3C13D12485A、E3C、E1C、E，D2顯然，B421【例9】趙、錢、孫、人，一個是教師，一個是售貨員，一個是工人，一個是機(jī)關(guān)。試根據(jù)以下條件，判斷這四人的職業(yè)。錢比孫大教太極拳；售貨員的鄰居不是機(jī)關(guān)機(jī)關(guān)和工人互不相識；（7）機(jī)關(guān)比售貨員和工人都大【分析】由條件（4）和條件（1）可知趙、錢都不是教師。由條件（2）和條件（7），可推知孫不是。如果是的話，錢不是工人或售貨員，錢又不是教師。于是，錢也是，。這樣我們得到下表。下面幾步推理也用表格說明。A、B、C、D、E（每兩支球隊間都要進(jìn)行一場比賽），當(dāng)比賽進(jìn)行到一定階段時，統(tǒng)計A、B、C、D經(jīng)賽過的場數(shù)，依次為A4，B3，C2，D1，E（）A. B. C. D.解：用五個點分別表示A、B、C、D、E1A4AB、C、D、E1；D1AB3不可能與D隊比賽，是與A、C、E1；C2場，是與A、B，E2前和關(guān)系即說某現(xiàn)的化果緊它面化一或些果密聯(lián)所三看的是個道理一理正現(xiàn)遞的想遞關(guān)幾在有數(shù)分中有要用一更高強齊的信息學(xué)賽更簡高而示其具的推系揮要用今入究性點成件分要的事情。本就將繞著遞關(guān)系三大基問題的如何遞推關(guān)系開論，并通例題明遞推系在信息賽中的應(yīng)1】給定一個數(shù)的序列H0,H1,…,Hnn0，使當(dāng)nn0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hn(0第n數(shù)列沒有研究價值，恰恰相反，一些此類的題目還是能給的啟發(fā)的。問題的提出：有雌雄一對兔子，假定過兩個月便可繁殖雌雄各一的一對小兔子。問過n解：設(shè)滿xFx對，其中當(dāng)月新生的兔子數(shù)目為Nx對。第x-1Ox Nx=Ox-1=Fx-2(即第x-2x 問題的提出：Hanoina,b,cna1 要求把anc問將這nac解：設(shè)hn為n個盤子從acn=1ach1=1柱上；再借助a柱把b柱上的n-1個盤子移動到c柱上；總共移動hn-1+1+hn-1個盤次。 問題的提出：設(shè)有n1 1 16119847151 圖一共有an-1+2(n-1an=an-1+2(n-1)a1=1。CatalanEulernCatalan6-4)h5=5nhnCn表示凸nnP1Pn也不例外，再根據(jù)“不在同一直線上的三點可以確定一個三角形”，只要在P2，P3，……，Pn-1點中找一個點Pk(1<k<nP1、Pn共同構(gòu)成一個kn-k+1CkCn-k1，故包含△P1PkPnn邊形的拆分方案數(shù)為-k1PkP2，