Задача №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
Ты нашел то, что искал? Поделись с друзьями!
Благодарим за то, что пользуйтесь нашими материалами.
Информация на странице «Задача №22. Перебор вариантов.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать необходимые и поступить в высшее учебное заведение или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими статьями из разделов нашего сайта.
Публикация обновлена:
07.06.2023