| Автор | Математикам) |
|---|
Я загадал число от 1 до 1000.
Чтобы отгадать число, можно задать вопросы. Но, вместо ответа на вопрос, после трёх вопросов, я называю только суммарное количество вопросов, на которые ответ "да" и суммарное количество вопросов на которые ответ "нет.
Если число после первого ответа не известно, то можно задать ещё три вопроса. И так далее, пока не будет известно загаданное число.
Какое минимальное количество моих ответов потребуется, чтобы узнать число, которое я загадал? |
| Ты скажи сколько заплатишь за верный ответ! |
| 42 |
Метод половинного деления, 10 шагов и мы находим число. Но надо удвоить, так как придётся на каждом шаге узнавать сначала равно ли число половине, а потом меньше оно половины или нет, так что максимум 20 вопросов.
Типа:
1) это 500?
2) это меньше 500?
3) это 250?
4) это меньше 250?
Понятно что меньше и больше в зависимости от да/нет будут появляться в четных вопросах |
для Эникейщик:
Не)
Например:
первые три вопроса.
Число равно 1?
Число равно 2?
Число равно 3?
Я пишу: число верных ответов - 0. Число неверных ответов - 3.
Сколько минимум моих ответов потребуется, чтобы точно узнать число при любых раскладах (какое бы я число не загадал). |
для Я_Недобитый:
Я пишу: число верных ответов - 0. Число неверных ответов - 3.
Тогда я угадаю это мелодию за 60 вопросов
1) это 500?
2) это 500?
3) это 500?
0 верных
4) это меньше 500?
5) это меньше 500?
6) это меньше 500?
0 верных
И так далее как в 4 посте, но с утроением в связи с правилами |
Просто это гарантированно рабочий алгоритм, 60 шагов не много
Лень изобретать велосипед |
Делим не три, т.е.
1) меньше или равен 333?
2) меньше или равен 666?
3) меньше или равен 999?
Если 3 верных ответа то ответ от 1 до 333, если 2 верных то от 334 до 666, если 1 то 667-999 и 0 это 1000
Каждый следующий шаг то же самое в сокращенном кол-ве чисел (1-111, 112-222, 223-333)
Если не ошибся то за 6 шагов находим число. Скорее всего можно быстрее но Лень изобретать велосипед |
Хотя ладно, оптимизация. Можно раз 3 вопроса то задавать 2 раза 1 и 1 раз второй
Тогда
1) это 500?
2) это 500?
3) это меньше 500?
По ответу понятно что сыграло что нет
Таких троек надо 10,значит 30 вопросов максимум |
| С делением на 3 да, быстрее |
А нет, на 4 нчдо делить, так как есть 4 варианта ответа (3 верных, 2 верных, 1 верный, 0 верных) и для оптимизации все 4 должны быть задействованны.
И того 4 шага или 12 вопросов |
Какое минимальное количество моих ответов потребуется
Минимальное число ответов - 1. если число угадать сразу и все три первых вопроса будут именно про него. Вот только причем тут математика?
Максимальное число ответов может стремиться к безконечности, при условии, что первый месяц будем упорно спрашивать, а не 140 ли ты загадал.
Если что тут и считать, то оптимальное количество ответов, да считать лень.
0 шаг - 1000 вариантов
1 шаг - 250 вариантов (1. >250?, 2. >500?, 3. >750?) - узнаем диапазон из 250 чисел
2 шаг - 63 варианта
3 шаг - 16 вариантов
4 шаг - 4 варианта
5 шаг - 2 варианта
6 шаг - число найдено
Итого 6 ответов |
| хотя не, 6 шаг не нужен. на 5 шагу число найдется. значит 5 ответов |
| 666 |
<= 501?
<= 251?
<= 126?
0 да -> 501-1000
1 да -> 251-500
2 да -> 126-251
3 да -> 63-126
и т.д.
Какое минимальное количество моих ответов потребуется, чтобы узнать число, которое я загадал?
ceiling(log2(1024)) = 10
ответ задается на 3 вопроса
ceiling(10 / 3) = 4
ответ 4 |
ceiling(10 / 3) = 4
ошибка
3 ответа подразумевают 4 диапазона чисел
правильно будет ceiling(10 / 4) = 3
ответ 3 |
ceiling(log2(1024)) = 10
опечатка) но всеравно
ceiling(log2(1000)) = 10 |
Есть версия, но недодумал про третий вопрос.
Первые два такие:
1.Это трёхзначное число?
2. Это простое число? |
| Второй вопрос задаётся в случае отрицательного ответа на первый. |
| 1 ответ. 1 раз спроси "число 1?", 2 раза "число 2?" ... 1000 раз "число 1000?". Победа. |
