算法合集之猜數(shù)問(wèn)題的研究

1、上海市復(fù)旦附中張寧猜數(shù)問(wèn)題的研究ioi2003國(guó)家集訓(xùn)隊(duì)論文近年來(lái)，信息學(xué)奧賽的試題涵蓋面越來(lái)越廣，不僅在程序設(shè)計(jì)方面對(duì)選手掌握算法與數(shù)據(jù)結(jié)構(gòu)的要求越來(lái)越高，對(duì)選手的數(shù)學(xué)水平也提出更高的要求。我個(gè)人對(duì)這個(gè)有趣的問(wèn)題比較感興趣，對(duì)題目進(jìn)行了深入的思考，并將其推廣到一般情形。下面將主要從數(shù)學(xué)證明的角度來(lái)分析問(wèn)題，由于時(shí)間關(guān)系，我將略過(guò)原問(wèn)題的證明，以及第一種簡(jiǎn)單的推廣，選擇第二種推廣的部分證明進(jìn)行講解。（論文中有詳細(xì)證明）而數(shù)學(xué)類問(wèn)題的難度，并不在于編程，而在于思想。其中也不乏一些比較另類的數(shù)學(xué)題，如ctsc2001聰明的學(xué)生這樣一道邏輯推理問(wèn)題與競(jìng)賽中常考的組合數(shù)學(xué)題目不同，它并不要求選手掌握任

2、何高深的數(shù)學(xué)知識(shí)，但對(duì)選手的抽象思維能力提出了挑戰(zhàn)。ioi2003國(guó)家集訓(xùn)隊(duì)論文猜數(shù)問(wèn)題的研究w 問(wèn)題描述w 兩個(gè)例子的分析w 問(wèn)題分析w 一些定義w 思路分析w “終結(jié)情形”的條件w “一類情形”能否轉(zhuǎn)化為“終結(jié)情形”w “二類情形”能否轉(zhuǎn)化為“終結(jié)情形”w 編程實(shí)現(xiàn)中的若干問(wèn)題w 結(jié)束語(yǔ)問(wèn)題描述：一位邏輯學(xué)教授有n名非常善于推理且精于心算的學(xué)生。有一天,教授給他們n人出了一道題：教授在每個(gè)人腦門上貼了一張紙條并告訴他們，每個(gè)人的紙條上都寫了一個(gè)大于0的整數(shù)，并將他們分成了兩組（一組學(xué)生有m人，mn/2，學(xué)生并不知道如何分組），兩組學(xué)生頭上數(shù)的和相等。于是，每個(gè)學(xué)生都能看見貼在另外n-1個(gè)同

3、學(xué)頭上的整數(shù)，但卻看不見自己的數(shù)。教授輪流向n位學(xué)生發(fā)問(wèn)：是否能夠猜出自己頭上的數(shù)。經(jīng)過(guò)若干次的提問(wèn)之后，當(dāng)教授再次詢問(wèn)某人時(shí)，此人突然露出了得意的笑容，把貼在自己頭上的那個(gè)數(shù)準(zhǔn)確無(wú)誤的報(bào)了出來(lái)。猜數(shù)問(wèn)題的研究ioi2003國(guó)家集訓(xùn)隊(duì)論文我們的問(wèn)題就是：證明是否一定有人能夠猜出自己頭上的數(shù)，若有人能夠猜出，則計(jì)算最早在第幾次提問(wèn)時(shí)有人先猜出頭上的數(shù)，分析整個(gè)推理的過(guò)程，并總結(jié)出結(jié)論。由于當(dāng)n=3時(shí)，m只能為2，即為聰明的學(xué)生的問(wèn)題原形，在論文中第一部分給出了證明。而對(duì)于m=n-1時(shí)的情況，作為原題的第一種推廣情形，在論文中第二部分給出證明。下面著重討論n3，mn-1時(shí)的情況。猜數(shù)問(wèn)題的研究io

4、i2003國(guó)家集訓(xùn)隊(duì)論文猜數(shù)問(wèn)題的研究ioi2003國(guó)家集訓(xùn)隊(duì)論文1第一位學(xué)生1第二位學(xué)生2第四位學(xué)生2第三位學(xué)生有4位學(xué)生，且每組有2人我與第二位學(xué)生一組，頭上是2+2-1=3我與第三位學(xué)生一組，頭上是1+2-2=1我與第四位學(xué)生一組，頭上是1+2-2=1不能判斷是1還是3，回答：“猜不出”若我與第一位學(xué)生一組，則我頭上是2+2-1=3，第一位學(xué)生將看到三個(gè)數(shù)為3,2,1，第一位學(xué)生不能確定自己頭上是4還是2，因此他猜不出，我也無(wú)法排除這種情況。若我與第三位學(xué)生一組，若我與第四位學(xué)生一組， 不能判斷是1還是3，回答：“猜不出”若我與第一位學(xué)生一組，則我頭上是2+1-1=2，若我與第二位學(xué)生一

5、組，則我頭上是2+1-1=2， 若我與第四位學(xué)生一組，則我頭上是1+1-2=0，不可能頭上只可能為2回答：“我頭上的數(shù)是2”1第一位學(xué)生2第二位學(xué)生2第四位學(xué)生3第三位學(xué)生有4位學(xué)生，且每組有2人若我與第一位學(xué)生一組，則我頭上是3+2-1=4，第一位學(xué)生將看到三個(gè)數(shù)為4,3,2，第一位學(xué)生不能確定自己頭上是5,3,1中哪一種，因此他猜不出，我也無(wú)法排除這種情況。若我與第三位學(xué)生一組，若我與第四位學(xué)生一組， 不能判斷是還是，回答：“猜不出”猜數(shù)問(wèn)題的研究ioi2003國(guó)家集訓(xùn)隊(duì)論文我與第二位學(xué)生一組，頭上是3+2-2=3我與第三位學(xué)生一組，頭上是2+2-3=1我與第四位學(xué)生一組，頭上是3+2-2

6、=3不能判斷是1還是3，回答：“猜不出”若我與第一位學(xué)生一組，則我頭上是2+2-1=3，若我與第二位學(xué)生一組，則我頭上是2+1-2=1， 若我頭上的數(shù)是，則第二位學(xué)生將看見三個(gè)數(shù)，1,1,2三個(gè)數(shù)，則他可以斷定自己頭上的數(shù)是2，但他并沒有在我之前猜出，因此我頭上一定不是1頭上只可能為3回答：“我頭上的數(shù)是3”ioi2003國(guó)家集訓(xùn)隊(duì)論文猜數(shù)問(wèn)題的研究我們先來(lái)分析一下，如何能夠猜出自己頭上的數(shù)。當(dāng)某位學(xué)生假設(shè)自己頭上是某數(shù)，并通過(guò)推理發(fā)現(xiàn)別人理應(yīng)能夠在前n-1次提問(wèn)中最先猜出頭上的數(shù)，就可以根據(jù)實(shí)際上別人并沒有在他之前猜出這一矛盾來(lái)排除頭上是某數(shù)的情況。 而當(dāng)某位學(xué)生能夠排除所有不同于實(shí)際的可能

7、值時(shí)他便猜出自己頭上的數(shù)了。這樣我們能夠設(shè)計(jì)出最基本的算法，在每一次提問(wèn)時(shí)，站在被提問(wèn)的學(xué)生的角度去考慮問(wèn)題，逐一考慮每個(gè)學(xué)生想法，直至某位學(xué)生能夠猜出頭上的數(shù)。讓我們來(lái)分析一下這樣做的時(shí)間復(fù)雜度：由于考慮可能的分組情況不同，頭上的數(shù)就有可能不同。因此對(duì)于每位學(xué)生頭上的數(shù)最多有 種不同情況。因此對(duì)第n次提問(wèn)，分析的復(fù)雜度為：可見，這樣是不可能很好的解決問(wèn)題的，我們必須從根本上去優(yōu)化算法，唯一的途徑就是從問(wèn)題的本質(zhì)去研究其中的聯(lián)系，從而避開表面上繁瑣的“思維嵌套”，即：在c的腦海中要考慮b是如何思考a的想法。mnc)(nmncoioi2003國(guó)家集訓(xùn)隊(duì)論文猜數(shù)問(wèn)題的研究猜數(shù)問(wèn)題的研究1122第一

8、位學(xué)生第二位學(xué)生第三位學(xué)生第四位學(xué)生用n+1元組 來(lái)描述推理過(guò)程中的一種情形，其中n個(gè)人頭上數(shù)分別為 ,從第一位學(xué)生開始提問(wèn)，且當(dāng)前的被提問(wèn)者為第k位學(xué)生。 對(duì)于n+1元組 ，第k位學(xué)生可以不依靠別人的回答進(jìn)行推理，能夠直接判斷出自己頭上數(shù)，稱n+1元組描述的情形為“終結(jié)情形”。對(duì)于n+1元組 ，ak n/2，則沒有人能夠猜出頭上的數(shù)v若有兩個(gè)最大數(shù)若n=4，則必然是頭上數(shù)最大的人猜出頭上的數(shù)，但需要通過(guò)推理才能確定由哪一人若n4，則沒有人能夠猜出頭上的數(shù)v若只有一個(gè)最大數(shù)，則需進(jìn)行推理若推理過(guò)程中出現(xiàn)“終結(jié)情形”，則可以直接得到結(jié)果，否則需要考慮每一種可能的分組情況，對(duì)有可能猜出頭上數(shù)的學(xué)生

9、，必然要滿足如下條件： 任意可能分組c符合 ，滿足mtgak)(2)()(bgcg1atak且推理過(guò)程中，n個(gè)學(xué)生頭上的數(shù)始終在減小ioi2003國(guó)家集訓(xùn)隊(duì)論文猜數(shù)問(wèn)題的研究雖然我們對(duì)問(wèn)題進(jìn)行了深入的分析，對(duì)推理加強(qiáng)了判定，對(duì)算法本質(zhì)進(jìn)行了優(yōu)化，將解決問(wèn)題的時(shí)間復(fù)雜度大幅度下降，但依然可能出現(xiàn)多種考慮情況。所以推理已不像聰明的學(xué)生那樣是一個(gè)線性結(jié)構(gòu)的推理，整個(gè)推理過(guò)程將成為樹狀結(jié)構(gòu)。因此我們除了在算法本質(zhì)上進(jìn)行優(yōu)化的同時(shí)，加強(qiáng)在編程實(shí)現(xiàn)的優(yōu)化，由于考慮到我們總結(jié)出的推理方式中，n個(gè)學(xué)生頭上的數(shù)始終在減小，因此我們可以采用紀(jì)錄搜索的方式解決問(wèn)題，為了加快檢索速度，可以采用hash表，并且我們?yōu)榱朔奖忝枋鲆粋€(gè)情形，即n位學(xué)生頭上的數(shù)，可以采用一個(gè)n位p進(jìn)制數(shù)來(lái)描述。綜合兩方面的優(yōu)化，我們已經(jīng)較為圓滿的解決了這個(gè)問(wèn)題。我們深入地分析了一個(gè)邏輯推理問(wèn)題，從綜觀全局的角度來(lái)考慮問(wèn)題的本質(zhì)聯(lián)系，而非一味單純地從每個(gè)人的思想出發(fā)，簡(jiǎn)化了最煩瑣的“思維嵌套”，因此避免了問(wèn)題規(guī)模隨著推理次數(shù)急劇增長(zhǎng)，有效地