Question

Миша загадал целое число от 0 до 7 включительно. Коля должен это число угадать. Коля задавать вопросы типа: "число 5( или любое другое число) больше (меньше) задуманного числа или рано ему?", а Миша может отвечать только "да" или "нет". Сколько вопросов достаточно задать, чтобы угадать число, при правильной стратегии игры? а) не более 3; б) не более 4; в) не более 6; г) не более 8.

Answer 1

Легко ! - Я уверен что правильный ответ (В)...-не более 6

Answer 2

Не больше 6 у меня тоже было такое задание

Answer 3

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

Для чисел от 0 до 7 включительно требуется всего 3 бита для их представления в двоичной системе. Воспользуемся этим свойством для разделения возможных чисел пополам с каждым вопросом.

Представим возможные числа от 0 до 7 в двоичной системе:

0 = 000 1 = 001 2 = 010 3 = 011 4 = 100 5 = 101 6 = 110 7 = 111

Сначала Коля спрашивает о бите на самом значимом месте (самый левый бит), например: "Число 4 больше задуманного числа?"

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

Далее Коля спрашивает о следующем бите, который разделит оставшиеся числа пополам. Например, если ответ "нет" на вопрос "Число 6 больше задуманного числа?", значит, оставшиеся варианты - 4 и 5.

Теперь мы имеем два оставшихся варианта. Для их различия требуется всего один вопрос, чтобы узнать загаданное число. Например, Коля может спросить: "Число 5 больше задуманного числа?"

Таким образом, правильная стратегия игры позволяет угадать число от 0 до 7 за не более чем 3 вопроса.

Ответ: а) не более 3.