Загадано число из промежутка от 1 до 64.какое кол-во информации нужно для угадывания промежутка?

Самая оптимальная стратегия угадывания - дихотомия, то есть деление отрезка пополам и задавание вопроса больше? (или меньше?)

Например, загадано 50

Последовательность

32   64/2            больше

48   (32+64)/2   больше

56   (48+64)/2   меньше

52   (48+56)/2   меньше

50   (48+52)/2   попал

 

Теперь о задаче. Вопрос очень некорректный, если бы он звучал, как сколько попыток нужно сделать, чтобы угадать? , то решение простое

64 = 2^6, поэтому нужно 6 попыток 6 = 110b, значит 3 бит достаточно, чтобы в них разместить это количество попыток.

НО в задаче вопрос-то другой! Потому что в процессе отгадывания на каждом шаге нужно знать 1. Концы отрезка, 2. ответ

Концы это 6 бит и 6 бит +ответ 1 бит, итого 13 бит на шаг *6 = 78 бит. Можно ещё сократить немного, так как в последующем вопросе используется информация из предыдущего(один из концов интервала).

Уточни, что имеется в виду под фразой "какое количество информации", иначе задача неопределена и допускает многочисленные толкования.

62=2^6
Значит,любое загаданное число можно отгадать за 6 раз.

1. F(x) = x^2. 
Что происходит в программе? Сначала i = 0, затем, пока F(i) = i^2 меньше K, i увеличивается на 1, и в конце выводится i.
Цикл прерывается тогда, когда i^2 станет не меньше K.

Итого, программа выводит наименьшее число, квадрат которого не меньше K.
При K = 18 это происходит при i = 5. Такой же результат будет для всех 16 < K <= 25, это 25 - 16 = 9 чисел.

2. Тут начало похожее: в i появляется наименьшее число, для которого f(i) не меньше k. Затем, если f(i) - k <= f(i - 1), выводится i, иначе i - 1.
Это условие не очень удобное, перепишем так: если k >= f(i) -  f(i - 1), то выводим i, иначе i - 1.

f(i) = 3i^2 - 2i

Для k = 12 выведется 2: f(3) = 21, но 12 < f(3) - f(2) = 21 - 8 = 13.

2 выведется, если:
- i = 2, при этом k >= f(2) - f(1)
- i = 3, и k < f(3) - f(2)

f(1) = 1
f(2) = 8
f(3) = 21

Первый случай: 1 < k <= 8, при этом k >= 8 - 1. Подходят k = 7 и k = 8.
Второй случай. 8 < k <= 21, при этом k < 21 - 8. Подходят k = 9, 10, 11, 12.

Всего 6 чисел.

3. По аналогии с первым, выводится наименьшее натуральное i, для которого f(i) >= g(k). Для k = 14 g(k) = g(14) = 71, и i = 5 (5 в кубе не меньше 71, а 4 в кубе - меньше 71). Нужно найти такое целое k, для которого
g(k) <= 5^3
g(k) > 4^3

64 < 5k + 1 <= 125
63 < 5k <= 124
13 <= k <= 24
k = 13.

Для начала смотрим что выходит при К= 36, выходит 5

Анализируем функцию F. Это линейная функция наподобии Фибоначи, значит ответом будет некий один отрезок из К

Потом немножко дорабатываем программу и смотрим на результат

var

   i, K, counter: integer;

function F(x: integer): integer;

begin

   if x < 2 then

       F := 1

   else F := F(x - 1) + 2 * F(x - 2);

end;

begin

   for K := 0 to 100 do  

   begin

       i := 28;

       //        readln(K);

       while (i > 0) and (F(i) > K) do  

           i := i - 1;

       

       if i = 5 then begin

           counter := counter + 1;

           writeln(counter, ') K = ', K);

       end;

   end

end.

Вывод

1) K = 21

2) K = 22

3) K = 23

4) K = 24

5) K = 25

6) K = 26

7) K = 27

8) K = 28

9) K = 29

10) K = 30

11) K = 31

12) K = 32

13) K = 33

14) K = 34

15) K = 35

16) K = 36

17) K = 37

18) K = 38

19) K = 39

20) K = 40

21) K = 41

22) K = 42

ответ 22