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

125

417

Посмотреть ответы 2

Ответы на вопрос:

данилдунаев

Информатика

4,4(59 оценок)

1) 52) 93) 94) 10алгоритм простой, представим число n-1 (т.к. ноль не учитывается) в качестве двойчной последовательности, для числа n=32 это будет 11111 дальнейший алгоритм прост, рассмотрим его на примере, задумано число 26: 1) проверяем правый регист (*0000 = 16), задаем вопрос "задуманое число больше 16? ", ответ "да", значит первы регистр 12) проверяем следующий (1*000=24), задаем вопрос "задуманое число больше 24? ", ответ "да", значит регистр 13) проверяем следующий (11*00=28), задаем вопрос "задуманое число больше 28? ", ответ "нет", значит регистр 04)проверяем следующий (110*0=26), задаем вопрос "задуманое число больше 26? ", ответ "нет", значит регистр 0 5) проверяем следующий (1100*=25), задаем вопрос "задуманое число больше 25? ", ответ "да", значит регистр 1итого получаем задуманное число в двоичной форме 11001 = 25, но т.к. мы не учитываем 0, то к этому числу надо прибавить 1, итого задусманное число 26