Тема : Вычисление информационного объема сообщения

B5 (повышенный уровень, время – 10 мин)

• 
  каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом
  
• 
  исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды
  

Пример задания:

1. 
   обратим внимание, что в условии ограничено число команд, поэтому неявно ставится задача написать самую короткую программу для решения задачи
   
2. 
   начнем решать задачу, «отталкиваясь» от начального числа
   
3. 
   на первом шаге с помощью имеющихся команд из числа 3 можно получить 6 или 12;
   
4. 
   на втором шаге из 6 можно получить 9 и 12, а из 12 – 15 и 48, и т.д., получается такая схема (структура «дерево»), цифры около стрелок показывает номер выполненной команды:
   

5. 
   уже чувствуется, что дерево сильно разрастается, на следующем уровне будет уже 8 вариантов, потом – 16 и т.д. (на каждом следующем уровне – в 2 раза большем, чем на предыдущем)
   
6. 
   нужно выбрать такой план дальнейшего перебора вариантов, который может быстрее всего привести к цели (числу 57)
   
7. 
   видим, что после второй операции ближе всего к результату оказалось число 48, попробуем начать анализ с этой ветки; если не получится – возьмем число 24 и т.д.
   
8. 
   ветка дерева, начиная от числа 48, построена на рисунке справа; красный крестик показывает, что полученное значение превышает 57
   
9. 
   итак, мы вышли на число 57 в результате такой последовательности команд: 22111, ее длина равна 5, что удовлетворяет условию задачи.
   
10. 
    таким образом, правильный ответ – 22111.
    

Возможные ловушки и проблемы: большую схему неудобно рисовать, в ней легко запутаться не всегда можно сразу угадать нужную ветку «дерева», то есть, ту, которая быстрее всего приведет к успеху

1. 
   нам нужно увеличить число (с 3 до 57), для этого в большинстве случаев умножение эффективнее сложения, поэтому нужно постараться максимально использовать умножение, а сложение – только в крайних случаях
   
2. 
   попробуем решить задачу «обратным ходом», начав с числа 57;
   
3. 
   очевидно, что последней командой не может быть умножение на 4 (57 на 4 не делится), поэтому последняя команда – сложение (прибавь 3), над стрелкой записан номер команды:
   

4. 
   число 54 также не делится на 4, поэтому предыдущая команда – тоже сложение:
   

5. 
   аналогично для числа 51:
   

6. 
   число 48 делится на 4, поэтому используем умножение:
   

7. 
   наконец, добавив в начало программы еще одно умножение, получаем полную цепочку:
   

8. 
   таким образом, правильный ответ – 22111, эта программа состоит из 5 команд.
   

Возможные ловушки и проблемы: иногда может потребоваться «откат» назад, например, если исходное число – 6, то применив деление на 4 для 12 мы «проскакиваем» его (получаем 12/4=3<6), поэтому нужно возвращаться обратно к 12 и дважды применять сложение; в этом случае ответ будет такой: