Какие вопросы нужно задать, чтобы за минимальное число вопросов угадать эти числа?

@Nare6ator · Регистрация: 05.06.2018

Author24 — интернет-сервис помощи студентам

Человек загадал 2 различных числа не выше 100. Какие вопросы нужно задать, чтобы за минимальное число вопросов угадать эти числа. Вопросы можно задать только те, на которые можно ответить "да" или "нет"

@tabbols95 · 20.06.2019, 21:45

Nare6ator, если количество ходов не ограничено, то можно задавать вопросы типа: Одно из загаданных чисел больше 50? - Да -Одно из загаданных чисел больше 75?
И так далее

Байт · 20.06.2019, 22:02

tabbols95, этот алгоритм хорош для одного числа. Когда их двое, имхо, все значительно интереснее.
Но задача требует уточнения. Загаданные числа пронумерованы? То есть я могу спросить "Первое число такое-то?" Или такого типа вопросы запрещены?
Второе уточнение. Загаданные числа могут быть одинаковыми?

Добавлено через 1 минуту
И еще вопрос. А при чем здесь Вероятность и Статистика?

Байт · 21.06.2019, 09:33

Сообщение от Байт

Второе уточнение.

Прошу прощения. Не дочел.

Сообщение от Nare6ator

2 различных числа

Добавлено через 16 минут
Однако, как ни крути...
Для ненумерованных чисел возможны X = $https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{100}^2$ = 4950 вариантов
Каждый вопрос разбивает на 2 области. Меньше чем 13 вопросами не обойтись
Точная формула: Наименьшее целое число, большее или равное log₂X
Для нумерованных X надо умножить на 2, к ответу прибавить 1

@Tetroghon · 10.07.2019, 21:42

А вопросы в духе "Первое больше чем второе" разве не сильно упрощают жизнь?

Байт · 10.07.2019, 22:24

Сообщение от Tetroghon

А вопросы в духе "Первое больше чем второе" разве не сильно упрощают жизнь?

Нет.
Если интересно, попробуйте на 8-ми (или на 7-ми) числах.
Для нумерованных чисел вариантов n*(n-1) Соответственно, log₂(n*(n-1)), округленный вверх до ближайшего целого.

@Excalibur921 · 10.07.2019, 22:31

Сообщение от Nare6ator

можно ответить "да" или "нет"

Обычная дихотомия.
https://ru.wikipedia.org/wiki/Дихотомия

Байт · 10.07.2019, 22:41

Не по теме:

Ну, когда в бой вступили такие умы, простым смертным тут делать нечего! Снимаю подписку на тему и самоудаляюсь

@Tetroghon · 10.07.2019, 23:24

А вопросы в духе "Первое больше чем второе" разве не сильно упрощают жизнь?

Сообщение от Байт

Нет.
Если интересно, попробуйте на 8-ми (или на 7-ми) числах.

Так вопрос про 2 числа стоит.

И если числа "плотно прижаты", то может помочь) Например нашли первое -- 80 и вопрос второе больше первого? Ответ: Да. Тогда нам всего-то 20 шишек перебрать)

Это тоже как некоторая эвристика логарифма.

Байт · 11.07.2019, 10:40

Сообщение от Tetroghon

Так вопрос про 2 числа стоит.

из 100. Вот это 100 я и предлагаю заменить на 8 или 7.

Сообщение от Tetroghon

если числа "плотно прижаты"

В задачах такого типа обычно рассчитывается худший вариант. То есть стратегия, гарантирующая успех при любом раскладе.
Конечно, можно спросить - "числа равны 37 и 73?" и случайно угадать за 1 вопрос.

Дело все в том, что любой вопрос разбивает множество допустимых пар на 2 множества.

@Просто_Юлия · 11.07.2019, 15:06

С двумя числами больше свободы по вопросам, за счет того, что можно рассматривать не только взаимодействия между ними и границами, но и между ними самими.

Типа так:
1) Разность чисел больше 50?
Если да, то локализуем одно из них:
2) Меньшее число меньше 25?
В зависимости от этого получаем для меньшего числа интервал от 1 до 24 или от 25 до 48. Если от 25 до 48, то второе автоматически локализуется в 76-99. Дихотомией уточняем первое, потом второе (с учетом положения первого). Худший случай: первое число 1 (выясняем это за 2 приведенных выше вопроса, плюс 4 вопроса), второе еще за 5 вопросов - итого 11.

Байт · 11.07.2019, 17:45

Просто_Юлия, да, исхитряться можно по разному. Но того, что каждый вопрос разбивает множество возможных ответов на 2 множества, как ни крути, обойти не удастся.
Вот я и предлагаю (пост 6) построить дерево вопросов для небольшого количества чисел. И если результат (максимальная высота дерева) будет отличаться от указанного в посте 4

Сообщение от Байт

Точная формула: Наименьшее целое число, большее или равное log2X
Для нумерованных X надо умножить на 2, к ответу прибавить 1

я буду удивлен. И буду проверять а) Ваши построения. б) свои домыслы. Именно в этом порядке
ЗЫ. По поводу "к ответу прибавить 1", тут я мог и лажануться. Ведь округленный до целого логарифм может не подчиняться формуле LOG(A*B) = LOG(A) + LOG(B). Впрочем, тут надо внимательно посмотреть....

@Tetroghon · 11.07.2019, 19:18

А вопросы в духе "Первое больше чем второе" разве не сильно упрощают жизнь?

Сообщение от Байт

Нет.
Если интересно, попробуйте на 8-ми (или на 7-ми) числах.

Так вопрос про 2 числа стоит...!

Сообщение от Байт

Вот это 100 я и предлагаю заменить на 8 или 7.

Не надо сейчас строить общих теорий

Есть конкретная задача. И в этой конкретной задаче жизнь может упроститься.

Добавлено через 9 минут

Сообщение от Байт

В задачах такого типа обычно рассчитывается худший вариант.

Если следовать исходному сообщению о вопросе -- всё сильно зависит от уже имеющихся данных и нужно смотреть будет ли выгоден этот 1 вопрос или нет.

И варианты возможны разные. Ну, асимптотически 1 вопрос погоду не сделает.

Сообщение от Tetroghon

на 8 или 7.

Тогда замените сразу на 2 ,т.е. натуральные числа не большие двух.

@Excalibur921 · 11.07.2019, 19:59

Сообщение от Tetroghon

Есть конкретная задача.

Нет тут ничего. Отсюда поток фантазий и вопросов. Постановка вопроса вида “нарисуйте мне машину“.