algorithm - Solving yes-no test -
there test n yes or no questions. can write test , professor tell how many of answers correct. fastest way pass test? i.e. give correct answers questions minimum number of trials.
upd solution n+1 trials obvious. on each trial have correct answer single question. 1 bit of information. professor gives number 0 n each time, log2(n + 1) bits of information. that's why best solution has o(n / log(n)) complexity. i'm looking solution sub-linear worst time complexity.
in article carsten's comment, erdös , rényi show example of how problem can formulated finding smallest number of test sequences can generate unique hash unknown sequence. since example shows sequence 5 digits long solved 4 tests, tried come sub-linear number of tests sequences of length 6 , seven.
looking @ erdös , rényi's example , inspired ioannis' mention of "divide , conquer," thought perhaps test sequences kind of divide , subdivide sequence. took few tries working tests sequence length seven.
perhaps 1 way think algorithm asking way generalize / automate generation of these test sequences.
the javascript program below compares test-sequences against sequences of given length, hashing number of coinciding digits. if 2 different sequences generate same hash, program notifies match found, meaning combination of tests not work. if no match found, means hashes unique , tests ought work.
// http://resnet.uoregon.edu/~gurney_j/jmpc/bitwise.html function setbits(i) { = - ((i >> 1) & 0x55555555); = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0f0f0f0f) * 0x01010101) >> 24; } // http://stackoverflow.com/questions/10073699/pad-a-number-with-leading-zeros-in-javascript function pad(n, width, z) { z = z || '0'; n = n + ''; return n.length >= width ? n : new array(width - n.length + 1).join(z) + n; } function numcoincidences(a,b){ var n = 0 (var i=0; i<a.length; i++){ if (a.charat(i) == b.charat(i)){ n ++ } } return n } var sequencelength = 6 var tests = [ "111111", "111000", "010010", "011001", "000100" ] /*** var sequencelength = 7 var tests = [ "1111111", "1111000", "0100100", "0110010", "0110001", "0001000" ] ***/ var hash = {} console.log(" " + tests.join(" ")) (var i=0; i<1<<sequencelength; i++){ if (setbits(i) < math.floor(sequencelength / 2)){ var tmp = pad(i.tostring(2),sequencelength) var h = "" (var j in tests){ h += numcoincidences(tests[j],tmp) } console.log(tmp + " " + h.split("").join(" ")) if (hash[h]){ console.log("found match") } else { hash[h] = true } } } console.log("done") output:
" 111111 111000 010010 011001 000100" <-- test sequences "000000 0 3 4 3 5" "000001 1 2 3 4 4" <-- sequences match, followed "000010 1 2 5 2 4" number of coincidences "000011 2 1 4 3 3" "000100 1 2 3 2 6" "000101 2 1 2 3 5" "000110 2 1 4 1 5" "000111 3 0 3 2 4" "001000 1 4 3 4 4" "001001 2 3 2 5 3" "001010 2 3 4 3 3" "001011 3 2 3 4 2" "001100 2 3 2 3 5" "001101 3 2 1 4 4" "001110 3 2 3 2 4" "010000 1 4 5 4 4" "010001 2 3 4 5 3" "010010 2 3 6 3 3" "010011 3 2 5 4 2" "010100 2 3 4 3 5" "010101 3 2 3 4 4" "010110 3 2 5 2 4" "011000 2 5 4 5 3" "011001 3 4 3 6 2" "011010 3 4 5 4 2" "011100 3 4 3 4 4" "100000 1 4 3 2 4" "100001 2 3 2 3 3" "100010 2 3 4 1 3" "100011 3 2 3 2 2" "100100 2 3 2 1 5" "100101 3 2 1 2 4" "100110 3 2 3 0 4" "101000 2 5 2 3 3" "101001 3 4 1 4 2" "101010 3 4 3 2 2" "101100 3 4 1 2 4" "110000 2 5 4 3 3" "110001 3 4 3 4 2" "110010 3 4 5 2 2" "110100 3 4 3 2 4" "111000 3 6 3 4 2" "done"
Comments
Post a Comment