Задание 23 ЕГЭ по информатике. Решение программированием

Еще один способ решения данного задания – написание программы.

На примере первой задачи посмотрим несколько способов решения.

Задание 1

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

1. прибавь 1

2. умножь на 3

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

В решении электронными таблицами мы получили формулы для расчетов:

Если число n НЕ делится на 3, количество программ для него

kn = kn-1

Если же число делится на 3, то

kn = kn-1 + kn / 3

их мы и будем использовать в данном задании.

1 способ решения. Заполнение списка.

Необходимые навыки:

• работа со списками
• условный оператор
• цикл for

# +1 *3 1->20

a = [0] * 21 # создаем список из такого количества

# элементов, чтобы нам хватило индексов от 0 до 20

a[1] = 1 # заполняем элемент с индексом стартового числа

for i in range(2, 20 + 1): # перебираем остальные числа от 2 до 20

if i % 3 == 0: # если кратно 3, добавляем предыдущее и / 3

a[i] = a[i – 1] + a[ i // 3]

else: # если не кратно 3, добавляем только предыдущее

a[i] = a[i – 1]

print(a[20]) # выводим на экран значение конечного числа

Данное решение является самым частным и не всегда получится им хорошо решить. Потребуются дополнительные условия когда могут получаться отрицательные индексы.

2 вариант решения без инверсии команд

# +1 *3 1->20
a = [0] * 100 # создаем список из такого количества 
# элементов, чтобы нам хватило индексов от 0 до 20 * 3 (я взял сильно с запасом)
a[20] = 1 # заполняем элемент с индексом стартового числа
for i in range(19, 0, -1): # перебираем остальные числа от 2 до 20
	a[i] = a[i + 1] + a[i * 3]
print(a[1]) # выводим на экран значение конечного числа

При таком решении не требуется условный оператор, но размер списка надо предусмотреть в 3 раза больше.

3 вариант решения. Рекурсивная функция

# +1 *3 1->20
def f(n):
	if n > 20: # перепрыгнули 20
		return 0
	if n == 20: # попали в 20
		return 1
	return f(n + 1) + f(n * 3) # число до 20
	


print(f(1))

Задача 2. Все варианты решения

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

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 40 и при этом траектория вычислений содержит число 20 и не содержит число 8?

Разобьем решение со списком на два этапа

# +1 *2 2->40 v20 x8
a = [0] * 100 

a[20] = 1 # заполняем элемент с индексом стартового числа
a[40] = 1
for i in range(19, 2 - 1, -1): 
	if i != 8:
		a[i] = a[i + 1] + a[i * 2]
for i in range(39, 20 - 1, -1):
	a[i] = a[i + 1] + a[i * 2]
print(a[2] * a[20]) # выводим на экран значение конечного числа

Усовершенствуем рекурсивный алгоритм: добавим в функцию еще один параметр. Теперь их два: из какого числа считаем и в какое.

# +1 *2 2->40 v20 x8
def f(n, finish):
	if n == finish:
		return 1
	if n > finish or n == 8:
		return 0
	return f(n + 1, finish) + f(n * 2, finish)
	
	
print(f(2, 20) * f(20, 40))

Решение задания программированием наиболее кратко получается с использованием рекурсивной функции. В целом, написание кода занимает время примерно равное решению в электронных таблицах, за исключением случаев когда дан большой диапазон чисел.

Следует рассматривать такой вариант решения как средство для проверки ручного решения.