Помогите пожалуйста с задачей(Прошу, как можно подробнее) В компьютерной школе учатся 560...

Question

Помогите пожалуйста с задачей(Прошу, как можно подробнее)
В компьютерной школе учатся 560 учеников в классах с 1-11 однажды директор поймал прогульщика который отвечает только на вопросы да и нет. У директора в распоряжении список учеников школы(560 человек, но класс не указан) Ему нужно узнать что за ученик перед ним стоит (фамилию, имя и отчество, полных тезок в школе нет) и в каком классе учится(только параллель, без буквы).

Comments

И в чем вопрос?

---

Дописать забыла: "Сколько вопросов, на которые следует ответить да/нет, необходимо задать?"

Answer 1

1. Определить ученика (фамилию, имя и отчество из списка).
Делим список на две части и задаем вопрос: "Ты в первой части списка?". По ответу выбираем нужную часть списка и повторяем до тех пор, пока не останутся две строки. После этого спрашиваем: "Ты верхний?". И по ответу устанавливаем ученика.
Такой метод при N вариантах позволяет найти ответ за k=㏒₂N вопросов.
Или, иначе, k≤2ⁿ
2⁹<560<2¹⁰ ⇒ k=10, т.е. нужно задать 10 вопросов.<br>
2. Количество классов у нас 11. Поступаем аналогично. Разбиваем номера классов на две части, например, с 1 по 6 и с 7 по 11. И спрашиваем: "Ты учишься в классе большем, чем шестой?" По ответу выбираем группу и снова разбиваем её на две части. Например, если ответ "да", то новое разбиение будет на группы 7-9 и 10-11. Повторяем, пока не найдем ответ.
И здесь расчет идет по той же схеме.
2³<11<2⁴ ⇒ k=4, т.е. потребуется задать 4 вопроса.<br>
Общее количество вопросов составит 10+4=14

Ответ: 14 вопросов