1樓:
經過乙個晚上的細緻的思考,我認為已經完全解決了這個問題。
問題抽象定義:N個題目,每個題答案只有是和否,考試僅能知道得分,每次考試必須回答所有題目。對某些題目可能有點兒肯定,如第一題答案為否的概率是0.
9(此處認為答題者估計的概率是可信的),第五題答案為否的概率是0.5(完全不知道,瞎矇),也就是說,輸入為個N維概率向量,每個維度表徵該題目正確答案為是的概率。輸出為一顆瞎矇向量樹,該樹的根節點表示第一次應該蒙的值,第二層有N+1個節點,分別表示這次蒙題得分為0-N。
該樹應使得確定所有問題正確答案所需的蒙題次數的期望最少。
關於該問題的進一步抽象:輸入為一隨機變數X,共2^N個取值,以N等於2為例,該隨機變數取值為00,01,10,11(答案為是取1,答案為否取0)。若答題者認為,第一道題目完全不會,第二道題目答案為是的概論是0.
8,則00,01,10,11的概率分別為
一次蒙題過程的抽象:蒙題前,我們已經知道了X的取值及其分布;每次蒙題有2^N種蒙法可以選擇。對任意一種蒙法,我們可以計算出得分的分布。
仍取之前的例子,如果我們蒙的是00(兩個題目都選否),我們得分的分布為:
類似的,蒙01,10,11也可以得出相應的分布。
最重要的一步來了:究竟選擇蒙哪乙個?
這時候就要請出夏農老爺子和他的資訊熵的概念了。
知道什麼是資訊熵的,請往下看,不知道的,請看一下這個問題下的回答 資訊熵是什麼?
我們要蒙那個在得到得分後可以使得資訊熵的增量的期望最大的答案。
仍取之前的例子,假設蒙的答案是00
先算一下蒙之前的資訊熵:-(0.1*log(0.
1)+0.4*log(0.4)+0.
1*log(0.1)+0.4*log(0.
4))=1.72
對於蒙00的做法,資訊增益的期望是2.36;類似的,我們可以算出其他三種蒙法的資訊增益的期望。
我們每次都選擇使得該值最大的那乙個來蒙,這樣每次蒙完得到分數的時候,我們所得到的資訊增益都是最大的,當最終資訊熵降為0的時候,就得到確切答案了。
這種選擇,蒙的次數的期望是最少的。
2樓:
首先,假設必須全答。1指是,0指否
第一輪,全「1」。
二項式分布。
N=2n時,二項式係數第n+1項最大;
N=2n+1時,二項式係數第n+1項最大;
最多的可能性則需要更多資訊來分辨,而次數越多獲得資訊越多,顯然,需要次數和最多可能性是正相關的。
而當到最後一次,剩餘可能數之間必然不同位必然是偶數個,則得分應是公差為2的等差數列。且經過多次判斷,互補碼在同一集合的概率為0。N題最多有[(N
+1)/2]個分數,最多識別[(N
+1)/2]個。比如,5(135),6(135或024或246),7(1357或0246),8(1357或0246或2468)等。
得分1時,表示只有1個「是」;
得分N-1時,表示只有1個「否」。這兩種情況,
根據二分法,如果2^(k+1)<N≤2^k,則還需要k次即可找出。
N=1,f(1)=1。
N=2,f(2)=2。
N=3,
得分1(或2)時,2^1<3<2^2,還需要2次
f(3)=3;
N=4,
得分2,max=6;
如果下一次猜「1000」,得分3、1;3分,第一位是1,後三位有乙個1,還需要2次;1分,第一位是0,後三位只有1個0,還需要2次。
如果下一次猜「1100」,得4、2、0,對應1、4、1;2分時,4種可能,4/2=2<4,還需要2次。
f(4)=4。
N=5,
得分2(或3),max=10;
如果下一次猜「10000」,得分4、2,對應4,6;max=6,2分,轉化為4題知道「2是2否」的情況,還需要3次能知道結果,共5次。
如果下一次猜「11000」,得分6、4、2,對應1、6、3;
max=6,4分,下一次猜「10010」,得分5、3、1對應1、3、2;
max=3,3分,下一次猜「10010」,得分5、3、1對應1、1、1;共四次猜完。
f(5)=4。
N=6,
得分3,max=20;
max=20,下一次猜「111000」,得分6、4、2、0,對應各1、9、9、1種;
max=9,4分,下一次猜「110100」,得分6、4、2,對應1、4、4;
4分,下一次猜「110111,得分4、2,各2種。5次可找出。
f(6)=5。
N=7,
得分3(或4),max=35;
得分3,下一次猜「1110000」,得分7、5、3、1,對應各1、12、18、4種;
3分,下一次猜「1000011」,得分7、5、3、1,對應1、6、9、2;
3分,下一次猜「1001001」,得分7、5、3,各1、4、4種。
5分,下一次猜「1000101」,得分7、5、3、1;3分,下一次猜「0011100」,得分7、5、3、1。猜完
f(7)=5。
N=8,
得分4,max=70;
下一次猜「11100000」,得分7、5、3、1,對應各5、30、30、5種;
5分,下一次猜「11000011」,得分8、6、4、2,對應1、8、15、6種;
4分,下一次猜「10100101」,得分8、6、4、2,對應1、4、7、3種;
4分,下一次猜「11001110」,得分5、3、1,對應3、3、1種。
8/2=4>3,3種1次可猜出。
f(8)=6。
N=9,
得分4,max=126;
下一次猜「111100000」,得分9、7、5、3、1,對應各5、40、60、20、1種;
5分,下一次猜「110000011」,得分9、7、5、3、1,對應1、10、28、18、3種;
5分,下一次猜「110011010」,得分8、7、6、5、3、1,對應1、4、2、9、10、2種;
3分,下一次猜「101010001」,得分9、7、5、3,對應1、2、4、3種,
4分,下一次猜「101100110」,得分8、6、4、2,各一種。
f(9)=6。
注意,可以看到
當N加1,資訊量增加1倍。在n較小時,如果得分數目加1,可分類也加1,就有可能彌補出這一倍的差距。
4,2^4→6→3→2,4次。
5,2^5→10→6→3,4次。
6,2^6→20→9→4→2,5次。
7,2^7→35→18→9→4,5次。
8,2^8→70→30→15→7→3,6次。
9,2^9→126→60→28→10→4,6次。
10,2^10→252→100→42→17→6→2,7次。
11,7次可完成。(11+1)/2=6,至少可以取到5,倒數第二步的最大估計在17附近。
11,2^11→462→200→82→34→→,34之後沒繼續進行,但根據前面的資料分析,下一次只有34的1/3左右,7次是可以實現的。
3樓:
可能至少有個N/2+O(logN)的上界吧,比如N=16時前5次(描述起來好麻煩大家體會精神吧)
昨晚看了下好像這樣就能把可能情況數控制在2^(N/2)內,又直覺上可以每步使情況數至少減半。不過沒細想……
昨天看錯題還以為是靜態策略……靜態策略找不到什麼好的結論,不過也不是什麼都沒有,像 以及N>=5時f(N) 4樓:Xinran He 首先這是個highly non-trivial的問題第一輪因為對稱性選什麼並不關鍵, 不妨設第一輪選全對, 這時得到1的個數為x。這時問題轉化為從n個位置中選出x個1。這個問題是combinatorial quantiative group testing problem。 定義是給定乙個大小為n的population, 其中有d個是defect的,每次test可以選擇乙個集合 ,test返回這個集合中有多少個defect的item。求在n個items找出d的defect的最少test次數 (https:// arxiv.org/pdf/1407.2283.pdf )原問題就是求 不負責任的猜想最大值應該取在n/2查了一下文獻似乎這個問題還沒有徹底被解決, 一般情況的lower和upper bound都沒有找到。題主要是感興趣可以找相關文獻看看,查combinatorial quantiative group testing problem就可以。 5樓:ramwin 回答n次,每次1個題目,也就是n次肯定能知道全部答案的。如果分成2個題目一組,第一次回答2道題目。第二次回答第一題。 第一次回答有二分之一的概率得到正確結果(全對或者全錯),那就一次得到了兩道題答案。從概率上來說,已經小於n次能得到所有答案了 我16年入的b站,已經是選修題時代了,真感覺不怎麼難。也沒查乙個字。不過我也沒資格得意,畢竟沒經歷過100題的恐懼不是 今天想重新回憶一下那種感覺,拿我爸手機號註冊重答了一下。80分 彈幕禮儀就好比駕照科一,四,怎麼慫,怎麼彬彬有禮就怎麼答。選修題就哪個會整哪個了。我屬於高讚裡面說的非二次元使用者,... 我什麼也不想吃 一定要去正規醫院檢查抑鬱症不光是心裡的疾病它也會伴隨一些軀體症狀到醫院不僅僅是讓你做那些測試題還有一些身體上的檢查比如做心電圖眼動測定還有什麼腦內神經遞質數值的測定總之抑鬱症的診斷並不是單單靠幾道測試題把你的狀況跟醫生說清楚讓醫生給你對症下藥千萬不要因為網上不準確的測試題就給自己造成... Howard mmpi 也叫明尼蘇達多項人格測驗 Howard 專業 篩查心理疾病和精神疾病,MMPI 明尼蘇達多項人格測驗 測試題有原題,但是沒有標準答案,即使有也不可能記住.完整版566題,簡版399題。這樣想記住幾乎不現實的。有些朋友做的是399題的,也有做的是566題的,這個兩個可能性都有。...在b站答會員測試題是什麼樣的體驗?
做了個測試題,輕度抑鬱,怎麼辦?
民航心理測試都包括什麼,有具體的測試題嗎?