Упр.190 Часть 2 ГДЗ Рабочая тетрадь Босова 6 класс (Информатика)

Задача

Коля задумывает натуральное число из отрезка от 1 до $$N$$. Петя должен это число отгадать. Он может задавать Коле вопросы, допускающие только ответы «да» или «нет». Петя разработал алгоритм, позволяющий за наименьшее число вопросов отгадать число, задуманное Колей. Восстановите недостающие надписи «да» и «нет» в блок-схеме и с её помощью выясните, сколько вопросов потребуется Пете, чтобы отгадать задуманное Колей число, если оно принадлежит отрезку: 1) от 1 до 32; 2) от 1 до 512; 3) от 1 до 300; 4) от 1 до 1024.
Выполните вычисления по блок-схеме для чисел $$X\in\{33; 42; 75\}$$ (запишите ответы в таблицу).

Подробный ответ

При ответах «да»/«нет» число вопросов в таком алгоритме равно количеству делений отрезка пополам, то есть нужно найти наименьшее число $$n$$, для которого $$2^n \ge N$$.

1) Для отрезка от 1 до 32:

$$2^5 = 32$$

Значит, потребуется 5 вопросов.

2) Для отрезка от 1 до 512:

$$2^9 = 512$$

Значит, потребуется 9 вопросов.

3) Для отрезка от 1 до 300:

$$2^8 = 256 < 300,\quad 2^9 = 512 \ge 300$$

Значит, потребуется 9 вопросов.

4) Для отрезка от 1 до 1024:

$$2^{10} = 1024$$

Значит, потребуется 10 вопросов.