Существует ли формула или теория описывающая угадывание числа с нескольких попыток?

Question

[eegmak]

К примеру, если угадывать с одной попытки число в диапазоне от 1 до 100, то вероятность угадать такое число 1/100 или 1 процент, а если попытки 2 то как подсчитать вероятность с двух попыток угадать это число?
Есть ли формулы или теории которые описывают каким образом минимизировать количество попыток для того чтобы угадать число от 1 до 100?

Answer 1

[Василий Банников]

Бинарный поиск
Если попытки две и не даётся информации больше/меньше, то считается простым умножением (1/100)*2

Если информация даётся, то можно делением отрезков пополам:
Допустим, загадали число 68
Делим 0..100 пополам
50 - Меньше
Делим 50..100 пополам
75 - Больше
Делим 50..75 пополам
62 - Меньше
Делим 62..75 пополам
68 - Угадали.
Таким образом получаем логарифм от количества возможных чисел по основанию 2 (количество попыток, необходимое на угадывание)

Comments

[eegmak]

информации о том больше или меньше нет, только "угадал" или "не угадал". мне кажется, вы не правильно посчитали, (вероятность угадать с одной попытки)*количество попыток не подходит

[Василий Банников]

eegmak, А, да, ошибся. Тут же есть зависимость между событиями
Вероятность угадать с первой попытки = 1/100
Вероятность не угадать с первой попытки = 1 - вероятность угадать с первой попытки
Вероятность угадать со второй попытки = вероятность не угадать с первой попытки * 1/99
Суммарная вероятность угадать = вероятность угадать с первой попытки + вероятность угадать со второй попытки.

https://ru.wikipedia.org/wiki/Теорема_Байеса
тоесть будет 0.02, если я ничего не пропустил
0.01 + (0.99*(1/99))