Question

Коля предложил Пете более сложную игру, чем изложенная в задании 40. Коля задумывает натуральное число из интервала от 1 до n. Петя должен это число отгадать. Он может задавать вопросы коле, допускающие только ответы да или нет. Петя разработал алгоритм, позволяющий за наименьшее число вопросов отгадать число, задуманное Колей. Выясните сколько вопросв потребуется Пете, чтобы отгадать задуманное число , если оно принадлежит интервалу: 1) от 1 до 32 2) от 1 до 512 3) от 1 до 300 4) от 1 до 1024 Плз помогите срочно надо!!!!!!!!!!!!

Answer 1

1) 5

2) 9

3) 9

4) 10

 

 

алгоритм простой, представим число n-1 (т.к. ноль не учитывается) в качестве двойчной последовательности, для числа n=32 это будет 11111 дальнейший алгоритм прост, рассмотрим его на примере, задумано число 26:

1) проверяем правый регист (*0000 = 16), задаем вопрос "задуманое число больше 16?", ответ "да", значит первы регистр 1

2) проверяем следующий (1*000=24), задаем вопрос "задуманое число больше 24?", ответ "да", значит регистр 1

3) проверяем следующий (11*00=28), задаем вопрос "задуманое число больше 28?", ответ "нет", значит регистр 0

4)проверяем следующий (110*0=26), задаем вопрос "задуманое число больше 26?", ответ "нет", значит регистр 0

 

 5) проверяем следующий (1100*=25), задаем вопрос "задуманое число больше 25?", ответ "да", значит регистр 1

итого получаем задуманное число в двоичной форме 11001 = 25, но т.к. мы не учитываем 0, то к этому числу надо прибавить 1, итого задусманное число 26

 

 

Answer 2

Постановка задачи

Коля предложил Пете более сложную игру, чем изложенная в задании 40. Коля задумывает натуральное число из интервала от 1 до n. Петя должен это число отгадать, задавая вопросы Коле, на которые можно получить только ответы "да" или "нет". Петя разработал алгоритм, позволяющий за наименьшее число вопросов отгадать число, задуманное Колей. Наша задача - выяснить, сколько вопросов потребуется Пете, чтобы отгадать задуманное число, если оно принадлежит интервалу:

1) от 1 до 32 2) от 1 до 512 3) от 1 до 300 4) от 1 до 1024

Решение

Для решения этой задачи мы можем использовать метод деления пополам. Этот метод позволяет сокращать интервал возможных чисел в два раза с каждым заданным вопросом.

Начнем с первого интервала от 1 до 32. Первый вопрос Пети может быть: "Число, которое ты задумал, больше 16?". Если Коля ответит "да", то Петя может исключить все числа от 1 до 16 и продолжить делить оставшийся интервал пополам. Если Коля ответит "нет", то Петя может исключить все числа от 17 до 32 и также продолжить делить интервал пополам.

Продолжая задавать вопросы в форме "Число, которое ты задумал, больше половины текущего интервала?", Петя сможет сократить интервал возможных чисел до одного. Таким образом, Пете потребуется 5 вопросов, чтобы отгадать число, задуманное Колей, в интервале от 1 до 32.

Аналогично, для остальных интервалов:

2) от 1 до 512: Пете потребуется 9 вопросов. 3) от 1 до 300: Пете потребуется 9 вопросов. 4) от 1 до 1024: Пете потребуется 10 вопросов.

Таким образом, Пете потребуется разное количество вопросов в зависимости от интервала, но максимальное количество вопросов составляет 10.

Ответ

Пете потребуется следующее количество вопросов, чтобы отгадать задуманное число, если оно принадлежит указанным интервалам:

1) от 1 до 32: 5 вопросов. 2) от 1 до 512: 9 вопросов. 3) от 1 до 300: 9 вопросов. 4) от 1 до 1024: 10 вопросов.