Сдай ЕГЭ на 100 баллов!

Учебные материалы и курсы для подготовки
к ЕГЭ по математике и другим предметам

+7 (495) 984-09-27
+7 (800) 775-06-82
Ваш регион: Москва
Книга

Задача №22. Перебор вариантов.

Автор материалов — Лада Борисовна Есакова.

Поиск количества программ по результату

Задачу такого типа можно решить, построив подробное дерево всех возможных вариантов наборов команд и подсчитав те, которые приведут к нужному результату. Однако, это очень длинный и объемный способ. Его использование может привести к вычислительным ошибкам, а при большой длине программы построение дерева вообще практически невозможно.

Рассмотрим более эффективный метод подсчета количества программ.

Пример 1.

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

1. при­бавь 2,

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

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 2, вто­рая — умно­жа­ет его на 3.

Про­грам­ма для Уве­ли­чи­те­ля — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко есть про­грамм, ко­то­рые число 1 пре­об­ра­зу­ют в число 31?

Ответ обос­нуй­те.

 

Решение:

Заполним таблицу со следующими столбцами:

«Число» — перечень всех чисел от 1 до 31;

«Числа-источники» — числа, из которых одной из указанных команд можно получить текущее число;

«Количество способов» — количество способов, которыми можно получить текущее число из чисел-источников. Равно сумме значений «Кол-во способов» чисел-источников.

Заметим, что никаким набором указанных команд невозможно получить четное число из 1, значит, четные числа можем в таблице не рассматривать вообще.

Число

Числа-источники

Кол-во способов получения

1 1 1
3 1 2
5 3 2
7 5 2
9 3 ; 7 2+2=4
11 9 4
13 11 4
15 5 ; 13 2+4=6
17 15 6
19 17 6
21 7 ; 19 2+6=8
23 21 8
25 23 8
27 9 ; 25 4+8=12
29 27 12
31 29 12

 

Число 1 нам дано, т.е. его можно получить единственным способом: ничего не делая.

Число 3 можно получить из 1 двумя способами: командой 1. и командой 2. И т.д.

Заметим, что два источника могут быть только у чисел, кратным трем. Это наблюдение поможет нам быстро заполнить таблицу, т.к. количество способов увеличивается, когда рассматриваем число, кратное трем.

Например, число 9 можно получить из числа 3 и числа 7. Сложив количество способов получения чисел 3 и 7 (2+2=4), получим количество способов получения числа 9.

Полная таблица приведена для наглядности, можно было заполнить только строки с числами, кратными 3, т.к. только они меняют количество способов получения числа.

Для числа 31 получаем количество способов 12. Это и есть искомое количество программ.

 

Ответ: 12

 

Пример 2.

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

1. при­бавь 1,

2. при­бавь 3.

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

Про­грам­ма для Ариф­ме­ти­ка — это по­сле­до­ва­тель­ность ко­манд.

Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 2 пре­об­ра­зу­ют в число 15?

 

Решение:

Заполним таблицу со следующими строками:

«Число» — перечень всех чисел от 2 до 15;

«Числа-источники» — числа, из которых одной из указанных команд можно получить текущее число;

«Количество способов» — количество способов, которыми можно получить текущее число из чисел-источников. Равно сумме значений «Кол-во способов» чисел-источников.

Число

Числа-источники

Кол-во способов получения

2 2 1
3 2 1
4 3 1
5 2 ; 4 1+1=2
6 3 ; 5 1+2=3
7 4 ; 6 1+3=4
8 5 ; 7 2+4=6
9 6 ; 8 3+6=9
10 7 ; 9 4+9=13
11 8 ; 10 6+13=19
12 9 ; 11 9+19=28
13 10 ; 12 13+28=41
14 11 ; 13 19+41=60
15 12 ; 14 28+60=88

Для числа 15 получаем количество способов 88. Это и есть искомое количество программ.

 

Ответ: 88

 

Пример 3.

Исполнитель Май15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

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

Программа для исполнителя Май15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение:

Заполним таблицу со следующими строками:

«Число» — перечень всех чисел от 2 до 29;

«Числа-источники» — числа, из которых одной из указанных команд можно получить текущее число;

«Количество способов» — количество способов, которыми можно получить текущее число из чисел-источников. Равно сумме значений «Кол-во способов» чисел-источников.

Число

Числа-источники

Кол-во способов получения

2 2 1
3 2 1
4 2 ; 3 1+1=2
5 4 2
6 3 ; 5 1+2=3
7 6 3
8 4 ; 7 2+3=5
9 8 5
10 5 ; 9 2+5=7
11 10 7
12 6 ; 11 3+7=10
13 12 10
14 7 ; 13 3+10=13
15 14 13
16 15 13
17 16 13
18 17 13
19 18 13
20 19 13
21 20 13
22 21 13
23 22 13
24 23 13
25    
26    
27    
28 14 13
29 28 13

До строки с числом 15 считаем все способы получения чисел. Начиная с числа 16 и до числа 24 (включительно) числа-источники 8-12 и способ получения числа применением команды «Умножить на 2» не подходят, т.к. траектория вычисления не содержит число 14. Для этих чисел учитываем одно число-источник (предыдущее) и один способ получения – «Прибавить 1».

Числа 25 вообще не должно быть в траектории, а значит, числа 26 и 27 получить невозможно.

Для числа 28 существует одно число-источник (14).

Для числа 29 получаем количество способов 13. Это и есть искомое количество программ.

Ответ: 13

 

Звоните нам: +7 (800) 775-06-82 (бесплатный звонок по России)
                       +7 (495) 984-09-27 (бесплатный звонок по Москве)

Или нажмите на кнопку «Узнать больше», чтобы заполнить контактную форму. Мы обязательно Вам перезвоним.