В детской игре угадай число первом участник загадала число в интервале от одного до 18 какое минимальное число попыток должна сделать второй участник чтобы наверняка отгадать число если первого участник на заявление числа второго должен только отвечать моё число больше моё число меньше или угадано
У нас есть интервал чисел от одного до 18, и второй участник должен угадать число, загаданное первым участником. Первый участник может только отвечать на каждую попытку второго участника, говоря "моё число больше", "моё число меньше" или "угадано".
Чтобы найти минимальное количество попыток, необходимо использовать тактику бинарного поиска. Первый участник загадал число в интервале от одного до 18. Для второго участника, чтобы максимально сократить количество попыток, самое оптимальное – начать с середины интервала (9) и задавать вопросы в соответствии с ответами первого участника.
1. Первый шаг: Второй участник предполагает, что загаданное число – 9, и сообщает это первому участнику. Первый участник отвечает, что его число больше или меньше или угадано.
- Если первый участник говорит "моё число больше", значит, загаданное число находится в верхней половине интервала от 10 до 18. Второй участник теперь знает, что его следующая попытка должна быть числом между 10 и 18. Разница снизилась до 9 чисел: 10, 11, 12, 13, 14, 15, 16, 17, 18.
- Если первый участник говорит "моё число меньше", значит, загаданное число находится в нижней половине интервала от 1 до 8. Второй участник теперь знает, что его следующая попытка должна быть числом между 1 и 8. Разница снизилась до 8 чисел: 1, 2, 3, 4, 5, 6, 7, 8.
- Если первый участник говорит "угадано", значит, второй участник отгадал число со всего первой попытки. Задача решена!
2. Второй шаг: Пусть первый участник ответил, что его число меньше. Второй участник затем делает свою следующую попытку в соответствии с новым интервалом от 1 до 8. Опять же, второй делит этот интервал пополам, и предполагает число в середине этого нового интервала, т.е., 4.
3. Третий шаг: Предположим, что первый участник говорит, что его число больше. Второй участник теперь знает, что число находится в интервале от 5 до 8. Второй делит этот интервал пополам и предполагает число на средней позиции, т.е., 6.
4. Четвёртый шаг: Предположим, что первый участник говорит, что его число меньше. Второй участник теперь знает, что загаданное число находится в интервале от 5 до 6. Он делит этот интервал пополам и предполагает число на средней позиции, т.е., 5.
5. Пятый шаг: Предположим, что первый участник говорит, что его число меньше. Второй участник теперь знает, что загаданное число находится в интервале от 5 до 5. Второй делит этот интервал пополам и предполагает число на средней позиции, т.е., 5.
Вот и весь процесс. За 5 попыток второй участник сможет наверняка отгадать число, которое загадал первый участник, используя стратегию бинарного поиска.
Эта стратегия работает, потому что с каждой новой попыткой второй участник делит интервал пополам, сокращая количество возможных чисел наполовину. Таким образом, каждая попытка увеличивает вероятность отгадать число.