共有 N 道測試題，答案只有是或否，測試完後會告訴你得分，請用儘可能少的測試次數得到每道題的正確答案？
是否能有少於 N 次試驗的方法？或者某種方法試驗次數的期望值盡量小
（註：答對得一分）
-------------------------------------------
補充說一下之所以提到了期望值是因為考慮到可能這 N 道測試題有幾題你十分肯定，或者比較確定，那麼肯定有辦法使得期望值少於 N。 在不考慮概率的情況下，假如真的不存在這樣的方法，又能否通過資訊理論或者其他手段證明這樣的方法不存在呢？
首先這是個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就可以。
首先很顯然複雜度是Θ(n)的。
然後我覺得期望幾乎最優的解法應該是第一次全選否，知道總的是的個數；然後前1/2選否，知道前一半和後一半是的個數，然後再分別每個區間前一半選否。不斷把區間分成兩半。這樣做期望是n。但是在過程中我們會遇到整個區間全選是或者全選否，那這個區間就不用繼續了。這樣算下來期望略小於3/4n，前面那個係數等於1-sum_{i=1}^{log n}1/2^{2^i}
上班路上，推導過程之後再補
寫證明的時候發現了一點問題，然後發現了一個確定的N/2+1的方法：
第一次所有題都填否，然後每兩道題分一組，每次操作一組，這組的第一題不填，第二題填是，所有其他組的題目仍然填否。根據分數差可以確定這兩道題的答案。
證明我再看看有沒有辦法修補得到新的下界。
之前的證明問題在於沒考慮不填的情況。如果不允許不填，下界應該仍然是上面那個，如果允許不填，至少可以做到下面這個解，我有空再考慮一下下面這個是否可以再改進。期望是可以改進的，但是暫時沒想到什麼優雅的證明下界的辦法。
補充一下思路：
假設經過k次嘗試能夠得到所有題目的答案，那麼我們斷定這個問題：
AX=Y
0 &<= xi &<= 1
一定有唯一整數解。其中A為k*N的矩陣，X為N*1的向量，Y為k*1的向量。我為了把這個問題放在線性空間下，a(i,j)的定義是，如果第i次嘗試第j題填了是則為1，否為-1，空著為0。yi的值是第i次嘗試得分減去這次嘗試填否的次數。本質上AX=Y是AX+B(1-X)=Y的一個變形。
如果不允許不填，那麼其實可以限定A每個元素只有兩種取值，然後可以嘗試證明AX=Y這個子空間和0 &<= xi &<= 1這個解空間只有唯一的交點，然後就能把解法局限在數是和否的個數上。但是如果A的取值有3種，那麼有可能出現AX=Y和0 &<= xi &<= 1相交，但是相交得到的單純形只有一個整點，這個就很尷尬了。但是這樣可以利用A中某個值變化1和變化2，至少一次提取2bit信息出來，就得到了第二個解。
武弘勛的回答假設了不能不填，比我的第一個方案更好。他的答案能做到期望是2/3n。
魔改了一下 @李正博 的程序，跑出了N=7的情況，最少需要5次：
5
Guess: 0000000
If: 3
Guess: 0001111
If: 3
Guess: 0111100
If: 3
Guess: 1101101
If: 4
Guess: 1010101
If: 1
Answer: 1101010
If: 3
Answer: 1100110
If: 5
Answer: 1011001
If: 7
Answer: 1010101
If: 2
Guess: 0111011
If: 2
Answer: 1010110
If: 4
Answer: 1011010
If: 6
Answer: 0110011
If: 6
Guess: 1100101
If: 5
Answer: 1101001
If: 7
Answer: 1100101
If: 5
Guess: 1100100
If: 4
Guess: 1011110
If: 2
Answer: 0110101
If: 4
Answer: 0110110
If: 6
Answer: 1011100
If: 2
Guess: 0111001
If: 5
Answer: 0111010
If: 7
Answer: 0111001
If: 6
Answer: 1101100
If: 1
Guess: 1100011
If: 5
Answer: 1010011
If: 7
Answer: 1100011
If: 7
Answer: 0111100
If: 5
Guess: 0011110
If: 3
Guess: 0101101
If: 5
Guess: 0101011
If: 5
Answer: 0100111
If: 3
Answer: 1001101
If: 7
Answer: 0101011
If: 3
Guess: 1001011
If: 5
Answer: 1000111
If: 7
Answer: 1001011
If: 7
Answer: 0101101
If: 5
Guess: 0011101
If: 5
Guess: 0011011
If: 5
Answer: 0010111
If: 7
Answer: 0011011
If: 3
Guess: 0101110
If: 5
Answer: 1001110
If: 7
Answer: 0101110
If: 7
Answer: 0011101
If: 7
Answer: 0011110
If: 1
Guess: 1111100
If: 4
Guess: 1110001
If: 5
Answer: 1110010
If: 7
Answer: 1110001
If: 6
Guess: 1110100
If: 5
Answer: 1111000
If: 7
Answer: 1110100
If: 7
Answer: 0001111
If: 4
Guess: 0000111
If: 3
Guess: 0011100
If: 3
Guess: 0010001
If: 4
Guess: 1010010
If: 1
Answer: 0101001
If: 3
Answer: 1001001
If: 5
Answer: 0110010
If: 7
Answer: 1010010
If: 2
Guess: 0100100
If: 2
Answer: 1001010
If: 4
Answer: 0101010
If: 6
Answer: 1100100
If: 6
Guess: 1010001
If: 5
Answer: 0110001
If: 7
Answer: 1010001
If: 5
Guess: 1011001
If: 4
Guess: 0001010
If: 2
Answer: 1010100
If: 4
Answer: 1001100
If: 6
Answer: 0011010
If: 2
Guess: 0110100
If: 5
Answer: 0101100
If: 7
Answer: 0110100
If: 6
Answer: 0011001
If: 1
Guess: 1100001
If: 5
Answer: 1100010
If: 7
Answer: 1100001
If: 7
Answer: 0011100
If: 5
Guess: 0001110
If: 3
Guess: 0010101
If: 5
Guess: 0100101
If: 5
Answer: 1000101
If: 3
Answer: 0010011
If: 7
Answer: 0100101
If: 3
Guess: 0100011
If: 5
Answer: 1000011
If: 7
Answer: 0100011
If: 7
Answer: 0010101
If: 5
Guess: 0010110
If: 5
Guess: 0100110
If: 5
Answer: 1000110
If: 7
Answer: 0100110
If: 3
Guess: 0001101
If: 5
Answer: 0001011
If: 7
Answer: 0001101
If: 7
Answer: 0010110
If: 7
Answer: 0001110
If: 1
Guess: 0011000
If: 4
Guess: 1110000
If: 5
Answer: 1101000
If: 7
Answer: 1110000
If: 6
Guess: 1011000
If: 5
Answer: 0111000
If: 7
Answer: 1011000
If: 7
Answer: 0000111
If: 2
Guess: 0011111
If: 3
Guess: 1111100
If: 5
Guess: 1111001
If: 5
Guess: 1110101
If: 5
Answer: 1101101
If: 3
Answer: 1111010
If: 7
Answer: 1110101
If: 3
Guess: 1110110
If: 5
Answer: 1101110
If: 7
Answer: 1110110
If: 7
Answer: 1111001
If: 3
Guess: 1110011
If: 5
Guess: 1100111
If: 5
Answer: 1101011
If: 7
Answer: 1100111
If: 7
Answer: 1110011
If: 7
Answer: 1111100
If: 5
Guess: 0111110
If: 5
Guess: 0101101
If: 4
Guess: 0111011
If: 5
Answer: 0110111
If: 7
Answer: 0111011
If: 6
Guess: 0101111
If: 5
Answer: 0111101
If: 7
Answer: 0101111
If: 2
Answer: 1011110
If: 3
Guess: 1001101
If: 4
Guess: 1011011
If: 5
Answer: 1010111
If: 7
Answer: 1011011
If: 6
Guess: 1001111
If: 5
Answer: 1011101
If: 7
Answer: 1001111
If: 7
Answer: 0111110
If: 7
Answer: 0011111
If: 5
Guess: 0000011
If: 3
Guess: 0001100
If: 5
Guess: 0011000
If: 5
Guess: 0101000
If: 5
Answer: 1001000
If: 3
Answer: 0010100
If: 7
Answer: 0101000
If: 3
Guess: 0100100
If: 5
Answer: 1000100
If: 7
Answer: 0100100
If: 7
Answer: 0011000
If: 3
Guess: 0110000
If: 5
Guess: 1100000
If: 5
Answer: 1010000
If: 7
Answer: 1100000
If: 7
Answer: 0110000
If: 7
Answer: 0001100
If: 5
Guess: 0000110
If: 5
Guess: 1001010
If: 4
Guess: 0010010
If: 5
Answer: 0100010
If: 7
Answer: 0010010
If: 6
Guess: 1000010
If: 5
Answer: 0001010
If: 7
Answer: 1000010
If: 2
Answer: 0000101
If: 3
Guess: 1001001
If: 4
Guess: 0010001
If: 5
Answer: 0100001
If: 7
Answer: 0010001
If: 6
Guess: 1000001
If: 5
Answer: 0001001
If: 7
Answer: 1000001
If: 7
Answer: 0000110
If: 7
Answer: 0000011
If: 1
Guess: 0001111
If: 3
Guess: 1110110
If: 4
Guess: 1111101
If: 5
Answer: 1111011
If: 7
Answer: 1111101
If: 6
Guess: 1110111
If: 5
Answer: 1111110
If: 7
Answer: 1110111
If: 5
Guess: 1101111
If: 5
Guess: 1011111
If: 5
Answer: 0111111
If: 7
Answer: 1011111
If: 7
Answer: 1101111
If: 6
Guess: 1100001
If: 3
Guess: 0010010
If: 4
Guess: 0000100
If: 5
Answer: 0001000
If: 7
Answer: 0000100
If: 6
Guess: 0010000
If: 5
Answer: 0000010
If: 7
Answer: 0010000
If: 5
Guess: 0100000
If: 5
Guess: 1000000
If: 5
Answer: 0000001
If: 7
Answer: 1000000
If: 7
Answer: 0100000
If: 0
Answer: 1111111
If: 7
Answer: 0000000
至少證明了N-1也不是上界……
注意這裡假設不允許不回答，如果允許不回答可能會更少。
完整的程序：
#include &
#include &
#include &
#include &
#include &
#include &
#include &
#include &
#include &
using namespace std;
int nQuestion = 5;
int N = 1 &<&< nQuestion;
struct Convert{
int bit_revert;
vector&
int convert(int source) const;
int unconvert(int source) const;
Convert operator*(const Convert b) const;
static Convert identity;
Convert():bit_revert(0),bit_switch(){}
};
Convert Convert::identity;
int operator*(int value, const Convert b){
return b.convert(value);
}
int operator/(int value, const Convert b){
return b.unconvert(value);
}
void dump_bin(int v){
for(int i = 0; i &< nQuestion; i++){
cout&<&<((v&>&>i)1);
}
}
struct ConvertPlan;
struct Plan{
int guess;
vector&
void dump(int padding = 0, const Convert b = Convert::identity) const;
Plan():guess(0),subplans(){}
~Plan();
};
struct ConvertPlan{
const Plan* referred;
Convert convert;
void dump(int padding = 0, const Convert b = Convert::identity) const;
};
Plan::~Plan(){
for(auto k : subplans){
delete k.second;
}
}
int Convert::convert(int source) const{
int result = 0;
source = source ^ bit_revert;
for(int i = 0; i &< bit_switch.size(); i++){
result |= ((source &>&> i) 1) &<&< bit_switch[i];
}
return result;
}
int Convert::unconvert(int source) const{
int result = 0;
for(int i = 0; i &< bit_switch.size(); i++){
result |= ((source &>&> bit_switch[i]) 1) &<&< i;
}
return result ^ bit_revert;
}
Convert Convert::operator*(const Convert b) const{
// v * a * b == v * (a * b)
Convert result;
result.bit_switch.resize(max(bit_switch.size(), b.bit_switch.size()));
for(int i = 0; i &< result.bit_switch.size(); i++){
int tmp = i;
if(i &< bit_switch.size()){
tmp = bit_switch[i];
}
if(tmp &< b.bit_switch.size()){
tmp = b.bit_switch[tmp];
}
result.bit_switch[i] = tmp;
}
// merge bit_revert
result.bit_revert = unconvert(b.bit_revert);
return result;
}
vector&
// result = source * convert
vector&
int bit_revert = source[source.size() - 1];
for(int v : result){
v ^= bit_revert;
}
int max_e = *max_element(result.begin(), result.end());
// Determine bit width
int bit_size = 0;
while(max_e){
max_e &>&>= 1;
bit_size++;
}
convert.bit_switch.resize(bit_size);
pair&
for(int i = 0; i &< bit_size; i++){
bit_counter[i].first = i;
bit_counter[i].second = 0;
}
for(int v: result){
for(int i = 0; i &< bit_size; i++){
if(v (1&<&
return a.second &> b.second || a.second == b.second a.first &< b.first;
});
convert.bit_revert = 0;
for(int i = 0; i &< bit_size; i++){
convert.bit_switch[bit_counter[i].first] = i;
}
for(int v : result){
v = v * convert;
}
convert.bit_revert = bit_revert;
sort(result.begin(), result.end());
/*
cout&<&<"[ ";
for(int v : result){
cout&<&
unordered_map&
for(int answer : answers){
int points = getPoints(answer, guess, nQuestion);
res[points].push_back(answer);
}
auto res2 = vector&
sort(res2.begin(), res2.end(), [](const pair&
const pair&
return a.second.size() &> b.second.size();
});
return res2;
}
struct MyHash{
size_t operator()(const vector&
size_t result;
result = b.size();
for(int i = 0; i &< b.size(); i++){
result |= ((size_t)b[i]) &<&< i;
}
return result;
}
};
struct MyPred{
bool operator()(const vector&
if(a.size() != b.size()){
return false;
}
for(int i = 0; i &< a.size(); i++){
if(a[i] != b[i]){
return false;
}
}
return true;
}
};
const Plan identityPlan;
unordered_map&
int minStep(vector&
// minimum number of further steps needed if we still have these possible answers
if(answers.size() == 1){
plan = new ConvertPlan();
plan-&>referred = identityPlan;
plan-&>convert.bit_revert = answers[0];
return 0;
}
Convert c;
vector&
auto it = stored_result.find(result);
if(it != stored_result.end()){
plan = new ConvertPlan();
plan-&>referred = it-&>second.second;
plan-&>convert = c;
return it-&>second.first;
}
int min = limit;
const Plan *ret = nullptr;
int max_guess = (1 &<&< c.bit_switch.size());
for(int guess = 0; guess &< max_guess; guess++) {
int max = INT_MIN;
auto res = getPartition(result, guess);
Plan *tmp2 = new Plan();
tmp2-&>guess = guess;
for(auto it = res.begin(); it != res.end(); ++it) {
if(it-&>second.size() &< result.size()){
ConvertPlan *tmp;
auto r = minStep(it-&>second, tmp, min);
if(tmp != nullptr){
tmp2-&>subplans.push_back({it-&>first, tmp});
}
if(r &> max){
max = r;
}
if(max &>= min){
break;
}
}else{
max = INT_MAX;
break;
}
}
if(max &>= min){
delete tmp2;
}else{
min = max;
ret = tmp2;
}
}
if(ret == nullptr){
plan = nullptr;
}else{
stored_result[std::move(result)] = pair&
plan = new ConvertPlan();
plan-&>convert = c;
plan-&>referred = ret;
}
return min + 1;
}
void Plan::dump(int padding, const Convert convert) const{
for(int i = 0; i &< padding; i++){
cout&<&<" ";
}
if(subplans.empty()){
cout&<&<"Answer: ";
dump_bin(guess / convert);
cout&<&
}
}
}
void ConvertPlan::dump(int padding, const Convert convert) const{
referred-&>dump(padding, convert * this-&>convert);
}
int main(int argc, const char *argv[]){
if(argc &> 1){
istringstream(argv[1]) &>&> nQuestion;
N = (1&<&
for(int i = 0; i &< N; ++i)
answers.push_back(i);
ConvertPlan *plan;
cout &<&< minStep(answers, plan) &<&< endl;
// Dump plan
plan-&>dump();
delete plan;
return 0;
}
被tpo折磨的間隙答一下大概想法。當然假設是不能不填。
一個naive approach是每次找兩個出來問一下，顯然至少要有1/2概率兩個相等，那麼會直接得到這兩個的答案，否則得到這兩個的異或關係，縮起來不放回去。一輪下來之後，期望還剩n/4對，直接遞歸下去就能得到一個期望2/3的係數了
這個方法改善的餘地在於能不能把幾層並行，就是說我每次給你的是log個bit你只用了第二個是吧，非常低效，如果你能比如說把一個兩組的詢問(對答貢獻是4的倍數)和一個一組的詢問(對答案的貢獻可以為1，如果你只改一個)，並一併可能就可以有更小的係數
順便這個方法能不能derandomize呢。。
直觀上的理解是試驗次數應該小於n的（當n足夠大時），因為測試給出的結果有n個bit的信息，而每次試驗能得到的是分數是1-n之間的一個數，理論上包涵信息（的上界）是log(n),所以一個trivial的lower bound是需要n/log(n)次試驗。
然後我又很暴力的跑了一發，到了n = 1，2，3，4，5的情形：
n = 1時，至少要1次試驗，保證得到正確答案。
n = 2時，至少要2次試驗，保證得到正確答案。
n = 3時，至少要3次試驗，保證得到正確答案。
n = 4時，至少要4次試驗，保證得到正確答案。
n = 5時，至少要4次試驗，保證得到正確答案。
可以十分不優美的證明有少於n次的試驗方法。。。（至少對於n=5的情形，個人猜測對於n&>5也成立，但真的是跑不動了沒加任何優化。。。，經知友提示，易證f（n+1）有upperbound是f（n）+1所以可以說猜測是成立的了）
代碼如下：
#include &
#include &
#include &
#include &
using namespace std;
int nQuestion = 1;
int N = 1 &<&< nQuestion;
int getPoints(int answer, int guess, int nQuestion) {
int sum = 0;
for(int i = 0; i &< nQuestion; ++i)
if((answer (1 &<&< i)) == (guess (1 &<&< i)))
sum++;
return sum;
}
unordered_map&
unordered_map&
for(int answer : answers){
int points = getPoints(answer, guess, nQuestion);
if(res.find(points) == res.end())
res[points] = unordered_set&
res[points].insert(answer);
}
return res;
}
int minStep(unordered_set&
// minimum number of further steps needed if we still have these possible answers
if(answers.size() == 1)
return 0;
int min = INT_MAX;
for(int guess = 0; guess &< N; ++guess) {
int max = INT_MIN;
unordered_map&
for(auto it = res.begin(); it != res.end(); ++it) {
if(it-&>second.size() &< answers.size())
max = std::max(max, minStep(it-&>second));
else
max = INT_MAX;
}
min = std::min(min, max);
}
return min + 1;
}
int main(){ -------------------------------更新--------------------------------
unordered_set&
for(int i = 0; i &< N; ++i)
answers.insert(i);
cout &<&< minStep(answers) &<&< endl;
}
上面代碼跑到很慢是因為嘗試了所有guess和他們對應的partition。如果我們可以empirical的evaluate一個partition（partitionCost函數），並只嘗試那個最好的partition繼續往下做，就可以得到一個upper bound，下面是跑出來的結果，注意都是upper bound。
question num = 1, step num = 1
question num = 2, step num = 2
question num = 3, step num = 3
question num = 4, step num = 4
question num = 5, step num = 5
question num = 6, step num = 5
question num = 7, step num = 6
question num = 8, step num = 6
question num = 9, step num = 7
question num = 10, step num = 7
question num = 11, step num = 8
question num = 12, step num = 8
代碼如下：
#include &
#include &
#include &
#include &
using namespace std;
int nQuestion, N;
int getPoints(int answer, int guess, int nQuestion) {
int sum = 0;
for(int i = 0; i &< nQuestion; ++i)
if((answer (1 &<&< i)) == (guess (1 &<&< i)))
sum++;
return sum;
}
int partitionCost(unordered_map&
// Get the adhoc cost of a partition. Used for pruning.
int maxSize = 0;
for(auto it = partition.begin(); it != partition.end(); ++it) {
maxSize = std::max(maxSize, (int)it-&>second.size());
}
return maxSize;
}
unordered_map&
unordered_map&
for(int answer : answers){
int points = getPoints(answer, guess, nQuestion);
if(res.find(points) == res.end())
res[points] = unordered_set&
res[points].insert(answer);
}
return res;
}
int minStep(unordered_set&
// minimum number of further steps needed if we still have these possible answers
if(answers.size() == 1)
return 0;
// select a good guess based on the ad-hoc evaluation of partition
int optCost = INT_MAX;
int optGuess = -1;
for(int guess = 0; guess &< N; ++guess) {
unordered_map&
int cost = partitionCost(partition);
if(cost &< optCost) {
optCost = cost;
optGuess = guess;
}
}
unordered_map&
// consider the worse case based on this partition
int max = 0;
for(auto it = optPartition.begin(); it != optPartition.end(); ++it) {
max = std::max(minStep(it-&>second), max);
}
return max + 1;
}
int experiment(int nq) {
nQuestion = nq;
N = 1 &<&< nQuestion;
unordered_set&
for(int i = 0; i &< N; ++i)
answers.insert(i);
return minStep(answers);
}
int main(){
for(int nq = 1; nq &<= 20; ++nq) {
cout &<&< "question num = " &<&< nq &<&< ", step num = " &<&< experiment(nq) &<&< endl;
}
}
經過一個晚上的細緻的思考，我認為已經完全解決了這個問題。
問題抽象定義：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的時候，就得到確切答案了。
這種選擇，蒙的次數的期望是最少的。
背書間隙看了一眼只看出來了一個弱智的解法(&>_&<)先寫一下佔個坑，等考完研再解π_π
之前分了好幾次回答，太亂了不好理解，我把整個流程重新理一下。
2n/3+1次，若n&>3且不能整除則進一位，n&<3不進
設「是」為1，「否」為0
1。
每三個數為一組，分為n/3組（不能整除則進位），每組每次答兩題，第一次答1.2題，第二次答2.3題，此為一組；第三次答4.5題，第四次答5.6題，此為第二組。。。以此類推
每次都只回答是，假如n/3=m，則將把所要計算的組之後的n-3m個題，答案全部填否。兩次結果分別為a，b
僅以前三個數舉例，比如:011000100.....（胡亂打的一串數）
每次只回答:是（即1）（1）若第一次得分為1，第二次得分為2，則即可推出前三個答案為011（2）若第一次得分為0，第二次得分為0，則即可推出前三個答案為000（3）若第一次得分為2，第二次得分為2，則即可推出前三個答案為111。。。。。。還有01和10兩種情況省略
此時需要的步驟是2n/3次。
此外還有一種情況需要額外討論，即兩次結果都是1時，即無法分辨前三位順序為101還是010時，需要再加一步。
把前三個答案全部填是，其餘仍是否
若得數小於a或b，則為010若得數大於a或b，則為101所以結果也要變一下，此時不應該是2n/3，應該是（2n/3）+1是有方法可以解決的，原題目等效成一個空間中求離散點的位置。
所以說越來越複雜了……
可以通過n分法劃分空間，不停排除空間中的點求出結論。
給出一個上界（注意：非上確界）
考慮到第一次劃分一定是可以劃分出n+1個空間的（全錯的0和全對的n），而在剩下的劃分中，即便我們採用二分法，也不會劃分的更慘。
而第一次劃分中，空間上的點數目服從二項式係數，則最大次數為
log2（cnn/2）+1
以下原答案，半夜手機打，漏洞多的快成篩子了。感謝指正的同學。
（ps，只是一種解法，未必最優）
用劃分編碼空間的方法來做這道題。考慮到N個題目分別可以由類似於（0,0,1,0...,0）的坐標向量構建一個空間。而答案a坐落在從0000000到1*1*1*1*1*1....的正多面體坐標點上。
共有2^n個點
由於n個題目，答案範圍在0-n之間，則劃分空間則有n+1個，雖然每個劃分空間中包含的點數不一樣，但總比2大，對吧。
極限情況下，採用二分法來劃分坐標空間進行逼近。則2^n個點要n次才分完。
由於n次測量中，得分上限比1大，得分空間｛0,.....｝總比2大，所以總可以實現大於等於2次的空間劃分。
例如n=5，01000
首先使用11111去求，得到1，說明坐標點在距離11111為4的區域內。共有點5個。
10000,01000,00100,00010,00001
然後用00011去分，距離為2，
則距離為2的點共有3個，是
10000，01000，00100，
距離為4的點有剩餘兩個。
此時點剩餘三個。
然後用11000去分，得到4，剩餘兩個。
再來一次，得出結論。
這種分法是最容易想出來的辦法，其最大次數為log2n向上取整+1
即5位的最大次數為log2 5向上取整=3，再加1等於4，也驗證了我們之前給出的測試用例。
假設只考慮分治的方法N道測試題k個錯誤答案可以在f(N,k)的平均時間內找到所有的錯誤，那麼這個函數f(N,k)應該可以用dp求出來（f(N,1)=log(N)）。然後按照這個f(N,k)函數做最佳的partition，感覺應該可以給出一個平均時間的上界。不過還沒有試過。。。
回答n次，每次1個題目，也就是n次肯定能知道全部答案的。如果分成2個題目一組，第一次回答2道題目。第二次回答第一題。第一次回答有二分之一的概率得到正確結果（全對或者全錯），那就一次得到了兩道題答案。從概率上來說，已經小於n次能得到所有答案了
個人拙見，不知道能否滿足題目需求。
同樣的是
首先全答是，知道n道題有m個是。（1）把n道題前m個答是， n-m全答否。
得到x分計算出m個題有q個是，m-q個否。（2）把n道題前m個答否， n-m全答是。
得到x分計算出n-m個題有p個否，n-m-p個是。以此類推，得到最小的是或者否就結束。
結論為N越大，期望值離N越遠。
經知友提示，我發現理解錯題意了，但思路不變。一早上代碼驗算一下，代碼結果結論如下
反覆驗證，我這個延遲時間都比N的要小，徘徊在0.75-0.8之間。
不過還是比其他答主的0.66要大。如果算期望，比如一些特殊情況（答案全是「是」，或者連續「是」比較多）。那期望我肯定要比現在的0.75要小。但沒算出小多少。首先，假設必須全答。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次是可以實現的。可能至少有個N/2+O(logN)的上界吧，比如N=16時前5次（描述起來好麻煩大家體會精神吧）
1111111111111111
1111111100000000
1111000011110000
1100110011001100
1010101010101010
昨晚看了下好像這樣就能把可能情況數控制在2^(N/2)內，又直覺上可以每步使情況數至少減半。不過沒細想……
昨天看錯題還以為是靜態策略……靜態策略找不到什麼好的結論，不過也不是什麼都沒有，像 以及N&>=5時f(N)&
1.常規分治法先全選對得到幾個對幾個錯(1次計算)再確定前一半和後一半幾個對幾個錯(2次計算).........n次後一直到每個小分組只有一個數(2的n-1次方次計算)n次分治需要2的n次方-1次計算對於一個規模為n的數據而言有log2(n)次分治需要2的n的log2n次方–1即2的n次方-1的計算其他的以後再更(資料庫老師有毒)
受評論指正，已重寫。
對於N=4的情況。首答全是。除了0分和4分的情況。接下來無論是1、2還是3分。都應當答是是否否。
根據這種情況猜想。回答應該是不受得分影響的。比如說對於N=4的情況。首答是是是是、次答是是否否、三答是否是否。根據三次的得分可以確定正解。（未細算）
那麼N=8的情況應該是類似的。事先準備幾個回答。全部測試後根據分數確定正解。
不知道其他答案中有沒有對前N項討論的。。。
我怎麼覺得不存在小於n次的方法一定能求出解呢？因為這個問題實際是求一個n維的超立方體，明顯至少要知道n個點才能確定嘛
推薦閱讀：