Теория:
Характеристика задания
1. Тип ответа: запись числового выражения.
2. Структура содержания задания: задан алгоритм на формальном языке.
3. Уровень сложности: повышенный.
4. Примерное время выполнения: \(8\) минут.
5. Количество баллов: \(1\).
6. Требуется специальное программное обеспечение: да.
7. Задание проверяет умение анализировать результат исполнения алгоритма, содержащего ветвление и цикл, с помощью языка программирования.
Пример задания
Рис. \(1\). Пример задания
Для начала рассмотрим более лёгкое аналогичное задание.
У исполнителя Калькулятор три команды, которым присвоены номера:
1) прибавь \(1\);
2) умножь на \(2\);
3) умножь на \(3\).
У исполнителя Калькулятор три команды, которым присвоены номера:
1) прибавь \(1\);
2) умножь на \(2\);
3) умножь на \(3\).
Сколько существует программ, которые число \(1\) преобразуют в число \(6\)?
Решить такую задачу можно следующими способами:
1) построить дерево;
2) построить таблицу вариантов;
3) с помощью языка программирования.
1) построить дерево;
2) построить таблицу вариантов;
3) с помощью языка программирования.
Способ \(1\)
Рис. \(2\). Дерево
Способ \(2\)
Чтобы определить количество программ, нужно рассмотреть условия:
1) прибавь \(1\);
2) умножь на \(2\);
3) умножь на \(3\).
2) умножь на \(2\);
3) умножь на \(3\).
Построим таблицу. Условия получения чисел будут таковы:
если число не делится ни на \(2\), ни на \(3\), то количество вариантов вычисляется по формуле (т. е. равно предыдущему значению) (\(1\)).
Если число делится только на \(2\), то количество вариантов вычисляется по формуле
(\(2\)).
Если число делится только на \(3\), то количество вариантов вычисляется по формуле
(\(3\)).
Если число делится и на \(2\), и на \(3\), то количество вариантов вычисляется по формуле
(\(4\)).
Построим таблицу, в верхней строке будем писать числа \(N\), которые нужно получить, а в нижней строке — количество команд \(N\), которые мы получаем.
Рис. \(3\). Таблица
Способ \(3\)
Разработаем программу, которая определит результат. В программе используем функцию, которая будет возвращать значения при определённых условиях.
Какие условия нужно рассмотреть?
1  | Объявим функцию \(F\), переменная \(x\) — первое число (из которого нужно начать работу), \(y\) — второе число, которое нужно получить |
1 2  | Проверим условие: если \(x\) окажется больше \(y\), то команд получения из одного числа другого нет, т. е. \(0\) |
1 2 3  | Проверим условие: если \(x\) равно \(y\), то команда есть, и она одна, поэтому возвращаем \(1\) команду |
1 2 3 4  | Данная строка возвращает значение функции. Как видим, в записях «\(x + 1\)», «\(x*2\)», «\(x*3\)» заложены условия задания: 1) прибавь \(1\); 2) умножь на \(2\); 3) умножь на \(3\) |
1 2 3 4 5  | Вызов функции \(F\) с параметрами \(x=1\) и \(y=6\) |
 | Результат работы программы |
Ответ: \(10\).
Пример задания
Алгоритм решения задания похож на предыдущий, исключением является то, что добавляется условие «траектория вычислений содержит число \(10\) и не содержит \(17\)». Нам нужно ввести ещё ограничение: «если \(x\) окажется больше \(y\), то команд получения из одного числа другого нет, т. е. \(0\)», и при появлении числа \(17\) значение функции тоже будет равно \(0\). Условие «содержит число \(10\)» запишем в строке вызова функции
\(print(1,10)*(10,35)\).
Программа
1  | Объявим функцию \(F\), переменная \(x\) — первое число (из которого нужно начать работу), \(y\) — второе число, которое нужно получить |
1  2  | Проверим условие: если \(x\) окажется больше \(y\), то команд получения из одного числа другого нет, т. е. \(0\). Также проверяем, если встречается \(17\), то возвращается \(0\) |
1  2  3  | Проверим условие: если \(x\) равно \(y\), то команда есть, и она одна, поэтому возвращаем \(1\) команду |
1 2 3 4  | Данная строка возвращает значение функции. Как видим, в записях «\(x+1\)», «\(x*2\)» заложены условия задания: 1) прибавь \(1\); 2) умножь на \(2\) |
1 2 3 4 5  | Вызов функции \(F\) с параметрами. В данном задании вызов разбит на \(2\) части, так как условие — «включая \(10\)», поэтому запрашиваем два промежутка и перемножаем их |
 | Вывод результата |
Ответ: \(98\).
Пример задания
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть \(1\)
B. Вычесть \(4\)
C. Найти целую часть от деления на \(3\)
Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе \(19\) результатом является \(2\), при этом траектория вычислений не содержит числа \(7\) и содержит \(13\)? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Напишем программу для решения задачи.
| def \(f(x, y)\): | Определяется новая функция с именем \(f\) и двумя параметрами\(x\) и \(y\). |
| if \(x < y\) or \(x == 7\): | Проверка условия: если \(x\) стал меньше \(y\) ИЛИ \(x\) равен \(7\), то выполняется следующая строка. |
| return \(0\) | Если условие из строки \(2\) выполнилось, функция прекращает работу и возвращает \(0\). |
| if \(x == y\): | Проверяется, равны ли \(x\) и \(y\). |
| return \(1\) | Если \(x == y\), значит, мы уже достигли нужного числа. |
| else: | Если ни одно из базовых условий (строки \(2\) и \(4\)) не сработало, значит, нужно продолжить вычисления. |
| return \(f(x - 1, y) + f(x - 4, y) + f(x // 3, y)\) | Функция вызывает саму себя три раза с новыми значениями \(x\): \(x - 1\); \(x - 4\); \(x // 3\). Затем результаты трёх вызовов складываются. Количество способов из \(x\) попасть в \(y =\) сумма способов из \((x-1)\), \((x-4)\) и \((x//3)\) попасть в \(y\). Каждый вызов идёт по своей ветке рекурсии, пока не достигнет одного из базовых случаев. |
| print(\(f(19, 13) * f(13, 2)\)) | Сначала вычисляется \(f(19, 13)\) — сколько способов из \(19\) получить \(13\) по правилам (уменьшать на \(1\), на \(4\) или делить на \(3\) нацело, но не переходя через y и не попадая в \(7\)). Затем вычисляется \(f(13, 2)\) — сколько способов из \(13\) получить \(2\) по тем же правилам. После этого результаты перемножаются, и итог выводится на экран. |
Ответ: \(68\).