Определите число для получения которого из числа 31 существует 1001 программа

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

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

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

1. прибавь 2,

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

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

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

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

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

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

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

Разбор программы Количество нулей в числе

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

Число

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

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

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

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

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

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

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

Читайте также:

Какой программой записать винду

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

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

1. прибавь 1,

2. прибавь 3.

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

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

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

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

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

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

Число

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

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

Задание 23 // ЕГЭ по информатике 2022

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

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

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

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

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

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

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

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

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

Число

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

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

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

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

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

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

Ты нашел то, что искал? Поделись с друзьями!

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

Публикация обновлена: 07.06.2023

Источник: ege-study.ru