Главная / Задания по информатике / Группа B / 22 (в 2015 - 22, в 2014 - В13) / 22 (в 2015 - 22, в 2014 - В13) Решение 2 (построение дерева)

22 (в 2015 - 22, в 2014 - В13) Решение 2 (построение дерева)

1. Условие и подробное решение

У исполнителя Удоитель две команды, которым присвоены номера:

1.  прибавь 1,
2. умножь на 2.

Первая из них увеличивает число на экране на 1, вторая – умножает его на 2.  Программа для Удвоителя – это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 23?

Решение 2  Будем строить дерево решений. Ребра в нем будут помечены допустимыми командами, в каждом узле будет записано текущее число, т.е. число, полученное из числа 3 с помощью последовательности команд, которые соответствуют пути из корня в этот узел. В корне будет записано число 3. Нас интересует количество путей из корня в вершины, помеченные числом 23. Так как обе команды увеличивают исходное число, то вершины, соответствующие числам, большим, чем 23, рассматривать не нужно.

На рисунке линия (без стрелки), идущая влево, соответствует команде 1.  прибавь 1; линия (без стрелки), идущая вправо, соответствует команде 2. умножь на 2.

B13-Fig3

Отметим, что если в вершине записано число  n от 12  до 23 (12 - наименьшее число n, для которого 2*n > 23), то из этой вершины есть ровно один путь в вершину с пометкой 23. Действительно, один такой путь всегда есть, он соответствует 23-n ребрам с пометкой 1 (т.е. выполнить команду «прибавь 1»). Если мы «свернем» с этого пути, т.е., находясь, в промежуточной точке выполним команду «умножь на 2», то мы получим число, большее, чем 23. Т.к. обе наши операции увеличивают исходное число, то далее мы не сможем получить число 23.  Для краткости такой единственный путь от числа n, где 12<=n<22 к числу 23 на рисунке изображен стрелкой. Теперь количество путей из корня в вершины с пометкой 23 можно просто подсчитать.

Ответ: 22.

2. Комментарий к решению

1. При решении построением дерева приходится делать лишнюю работу. Например, число 8 в дереве появляется 3 раза. Обработав его один раз (например, после выполнения команд прибавь 1  и умножь на 2), можно посчитать, что есть 6 способов получить 23 из 8. Строить второй и тем более третий раз дерево с корнем 6 не нужно!  Решение с помощью построения таблицы и есть способ систематически избегать лишней работы.

2. Если бы вместо числа 23 нужно было получить большее число, скажем, 50 (и, заведомо, если взять 100), то, пожалуй, задача станет неподъемной. А с таблицами – легко.

 
 

0 Comments

Оставьте коммент первым.

 
 

Что думаете?

 




 
 

 
 
Яндекс.Метрика