Подтвердить что ты не робот

Решение теста yes-no

Существует тест с вопросами N YES или NO. Вы можете написать тест, и профессор расскажет вам, сколько из ваших ответов верно. Каков самый быстрый способ пройти тест? То есть дать правильные ответы на все вопросы с минимальным количеством испытаний.

UPD Решение с испытаниями N+1 очевидно. На каждом испытании мы получим правильный ответ на один вопрос. Это 1 бит информации. Но профессор дает нам число от 0 до N каждый раз, это log 2 (N + 1) бит информации. Поэтому лучшее решение имеет сложность O(N / log(N)). Я ищу любое решение с сублинейной худшей сложностью.

4b9b3361

ОТВЕТЫ

Ответ 1

В статье статьи из комментария Карстена Erdös и Rényi показывают пример того, как проблема может быть сформулирована как поиск наименьшего числа тестовых последовательностей которые вместе могут генерировать уникальный хеш для неизвестной последовательности. Поскольку в их примере показана последовательность, состоящая из пяти цифр, которые были решены четырьмя тестами, я попытался выработать сублинейное число тестов для последовательностей длиной шесть и семь.

Взглянув на пример Эрдеша и Рэнни и вдохновленный упоминанием Иоанни "разделяй и побеждай", я подумал, что, пожалуй, тестовые последовательности делятся, а затем подразделяют последовательность. Потребовалось несколько попыток получить рабочие тесты для длины последовательности семь.

Возможно, один из способов подумать о запрошенном вами алгоритме может быть способом обобщения/автоматизации генерации этих тестовых последовательностей.

В приведенной ниже программе JavaScript сравниваются тестовые последовательности со всеми последовательностями заданной длины, хешируя количество совпадающих цифр. Если две разные последовательности генерируют один и тот же хэш, программа сообщает, что совпадение найдено, что означает, что эта комбинация тестов не будет работать. Если совпадение не найдено, это означает, что хеши уникальны и тесты должны работать.

// http://resnet.uoregon.edu/~gurney_j/jmpc/bitwise.html
function setBits(i)
{
     i = i - ((i >> 1) & 0x55555555);
     i = (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
    for (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(" "))

for (var i=0; i<1<<sequenceLength; i++){
    if (setBits(i) < Math.floor(sequenceLength / 2)){
      var tmp = pad(i.toString(2),sequenceLength)
      var h = ""
      for (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")

Вывод:

"       111111 111000 010010 011001 000100" <-- test sequences
"000000   0      3      4      3      5"
"000001   1      2      3      4      4"    <-- sequences to match, followed by
"000010   1      2      5      2      4"             the 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"

Ответ 2

Очевидное улучшение над решением N + 1:

Начните со всех ответов Y.

Затем мы точно знаем, сколько да/нет.

Пусть p - вероятность наличия да в любой заданной позиции. p >= 1/2 без потери общности.

Затем я открою два первых ответа в среднем 2 - p^2 try.

Я меняю свой ответ на два первых вопроса. По крайней мере, p^2 того времени я буду знать точный ответ для них обоих. Если нет - тогда я, по крайней мере, знаю, что один из них - Y, а другой - N, и мне нужно задать еще один вопрос.

Итак, в худшем случае p = 1/2 мне нужно 1 + N * 7/8.

Ответ 3

Отказ от ответственности: я не знаю, является ли это самым быстрым способом. Я уверен, что в конкретных сценариях вы можете уйти с меньшим количеством проб, но это может быть строгая верхняя граница (худший сценарий).

Заполните первый пробный раунд, как вам нравится, просто запомните свой выбор. Если вы предпочитаете, вы можете выбрать Нет для всех из них.

В следующем испытании измените только первый ответ (следуя примеру: выберите Да). Основываясь на изменении ответа, вы будете знать правильный ответ для первого вопроса (если результат увеличивается, вы дали правильный ответ, если нет, неверный).

Теперь измените только второй и т.д.

Вам нужны N + 1 трейлы.

Ответ 4

Вот еще один подход (делить и побеждать). для простоты я буду ссылаться на конкретное значение N, но обобщение прост.

Пусть N=10 и предположим, что в первом раунде (trial=1) мы правильно отвечаем на вопросы 5. Это наиболее вероятный результат, и тот, который показывает меньше информации, как было замечено.

Тогда следующая логика позволяет не проверять каждое число:

  • Разделите список ответов в двух наборах, 1...5, 6...10. Учитывая, что у нас есть 5 правильных ответов, возможные правильные ответы для каждого набора:

    (0,5)
(1,4)
(2,3)
(3,2)
(4,1)
(5,0)

Теперь, для следующего пробного флип ответит 1...5. Тогда указанные состояния изменяются следующим образом:

    (0,5)--> (5,5)   -- 10 correct
    (1,4)--> (4,4)   -- 8 correct
    (2,3)--> (3,3)   -- 6 correct
    (3,2)--> (2,2)   -- 4 correct
    (4,1)--> (1,1)   -- 2 correct
    (5,0)--> (0,0)   -- 0 correct

Если учитель говорит 10 или 0, мы закончили или нам нужно еще одно испытание соответственно. В любом случае, в зависимости от числа, которое говорит учитель, мы можем знать, сколько правильных ответов мы имеем в каждом интервале. Тогда мы можем решить.

  • 2 Правильно. Мы откидываем назад (назад) первые 5 ответов, и мы знаем, что мы имеем (4,1) правильно в ответах 1...5 и 6...10 соответственно. Таким образом, мы также переворачиваем 6...10 и получаем 8 правильных значений, см. Ниже.
  • 4 Правильно. Как и в 2 правильных, мы отбрасываем первые 5 ответов, а также переворачиваем 6...10 и получаем 6 правильных значений, см. ниже.
  • 6 Правильно. Нам нужно еще разделить и повторить. Нам нужно не более трех шагов для каждого из 1...5 и 6..10, поэтому всего 8 шагов, включая первые два шага.
  • 8 Правильно. Мы снова применяем двоичный поиск. мы делим каждый из двух исходных множеств (например, 1...5 делится на 1...3, 4...5) и ищет неправильный ответ. Если он находится в 4...5, нам нужны два шага, иначе нам понадобятся три шага. Таким образом, снова в общей сложности 8 шагов.

Ответ 5

Наивное решение будет включать попытки O (N): начните со всех ответов YES, затем в каждом i th попробуйте перевернуть ответ i th. Если ваш счет увеличился, сохраните его; если нет, откиньте его назад. Приращение i, повторите.

Более эффективное решение может включать очень простой генетический алгоритм, в котором эвристика является ответом профессора, а мутация может быть эквивалентна простому переводу всех ответов. Вероятно, это приблизилось бы к попыткам O (log N), но, конечно, мультипликативная константа была бы больше (по крайней мере, на порядок, если бы я должен был догадываться), поэтому это было бы возможно только при больших N.

Ответ 6

Некоторые коды Python для тривиального алгоритма O (n):

import random

def ask_prof(A, M): return sum(x == y for x, y in zip(M, A)) 

N = 10
A = [ random.randint(0, 1) for x in range(N) ]
K, s = [], 0
for trial in range(N):
    M = K + [ 0 for x in range(N - len(K)) ]
    s1 = ask_prof(A, M)
    M[len(K)] = 1 
    s2 = ask_prof(A, M)
    if s1 < s2: K.append(1)
    else: K.append(0)
print 'answers are', K