СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 22 № 4565

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

 

1. прибавь 1,

2. умножь на 2.

 

Первая из них увеличивает на 1 число на экране, вторая удваивает его.

Программа для Удвоителя – это последовательность команд.

Сколько есть программ, которые число 3 преобразуют в число 23?

Решение.

Построим полное дерево решений и подсчитаем количество вариантов. Рассмотрим сначала ветвь, где первая команда умножение:

 

1) 3 → 6 → 12 → 13 → ... → 23

2) 6 → 7 → 14 → ... → 23

3) 7 → 8 → 16 → ... → 23

4) 8 → 9 → 18 → ... → 23

5) 9 → 10 → 20 → ... → 23

6) 10 → 11 → 22 → ...23

7) 11 → 12 → ... → 23

 

Теперь рассмотрим ветвь, где первая команда сложение, вторая умножение:

8) 3 → 4 → 8 → 16 → ... → 23

9) 8 → 9 → 18 → ... → 23

10) 9 → 10 → 20 → ... → 23

11) 10 → 11 → 22 → ...23

12) 11 → 12 → ... → 23

 

Ветвь, где первая и вторая команда сложение:

13) 3 → 4 → 5 → 10 → 20 → ... → 23

14) 10 → 11 → 22 → .. → 23

15) 11 → 12 → ... → 23

 

Первые три и более команд сложение:

16) 3 → 4 → 5 → 6 → 12 → ... → 23

 

Ещё 6 программ будут иметь такой же конец, как программы 2 — 7.

 

Всего 22 программы.

Источник: Демонстрационная версия ЕГЭ—2013 по информатике.