Количество программ (задача 23)

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.

В задаче 23 ЕГЭ по информатике описывается исполнитель, который может выполнять несколько команд (чаще всего две), например, прибавить 1 или прибавить 3. Требуется найти количество программ, которые преобразуют одно число (исходное) в другое (цель). Например, из числа 2 нужно получить число 15, используя две описанные выше команды.

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

Для каждого числа менее цели количество программ, требуемых для её достижения - это сумма числа программ, получаемых с помощью каждой из команд исполнителя.

Заметим, что каждая команда увеличивает число. Поэтому если команда дает результат, превышающий целевое число, то в дальнейшем мы никогда не получим целевого числа. Если текущее число равно целевому, то мы, очевидно, достигли цели.

Наша рекурсивная функция на языке Питон может выглядеть, например, так:

def ways(n, goal):
    if n>goal: return 0
    if n==goal: return 1
    return ways(n+1,goal)+ways(n+3,goal)

Чтобы получить ответ для описанной выше задачи, нужно найти результат вычисления функции с параметрами 2 и 15:

print(ways(2,15))

Таким образом, задача решена с помошью всего лишь пяти строк кода на Питоне.

Если команды исполнителя не увеличивают число, а уменьшают его, то нужно изменить операцию сравнения: вместо "больше" написать "меньше". Так, для задачи получения числа 2 из числа 22 с помощью операций "вычти 2" и "вычти 5" можно написать такую программу:

def ways(n, goal):
    if n<goal: return 0
    if n==goal: return 1
    return ways(n-2,goal)+ways(n-5,goal)

print(ways(22,2))

Программы с обязательным этапом

В более сложных вариантах данной задачи требуется либо найти число программ, в которых траектория вычислений либо должна содержать определенное число, либо же, напротив, не должна содержать какого-то числа.

Рассмотрим вначале программы с обязательным этапом. Типичная задача - получить из числа 3 число 12, причем разрешается использовать три операции: "прибавь 1", "прибавь 2" и "умножь на 2", а на одном из промежуточных этапов должно получиться число 10.

Решается задача просто: подсчитывается число программ первого этапа (сколько существует способов получить из числа 3 число 10) и способов второго этапа (получить из число 10 число 12). Так как любую программу первого этапа можно комбинировать с любой программой первого этапа, то ответ на задачу - это произведение числа споcобов первого этапа на число способов второго этапа.

Программа для решений этой задачи может выглядеть так:

def ways(n, goal):
    if n>goal: return 0
    if n==goal: return 1
    return ways(n+1,goal)+ways(n+2,goal)+ways(n*2,goal)

print(ways(3,10)*ways(10,12))

Программы с избегаемым этапом

Если нам запрещают получать в ходе вычислений какое-то число, то нашу функцию придется немного изменить: она должна возвращать 0 для "запрещенных" чисел.

Пример задачи - получить из числа 3 число 13, причем разрешается использовать две операции: "прибавь 1" и "прибавь 2", а в процессе вычислений не должно получаться числа 8.

Введем в нашу функцию ешё один параметр - массив zapret, который содержит числа, которых мы должны избегать. Зачем массив? Для случаев, когда "запрещенных" чисел более одного. (Ниже мы столкнемся с ситуацией, когда это потребуется.)

Вот программа, решающая данную задачу:

def ways(n, goal, zapret):
    if n>goal: return 0
    if n in zapret: return 0
    if n==goal: return 1
    return ways(n+1,goal,zapret)+ways(n+2,goal,zapret)

print(ways(3,13,[8]))

Так как в нашем случае "запрещенное" число всего одно, то в функцию передается массив, состоящий из одного элемента.

Крест-накрест: обязательный этап вместо избегаемого и наоборот

Вначале - очень простая мысль: общее число программ - это сумма числа программ, треактория вычислений которых проходит через некое число, и числа программ, траектория которых через это число не проходит.

Таким образом, мы можем решать задачи с обязательным этапом, пользуясь методикой для избегаемого, и наоборот. Например, чтобы найти число программ с обязательным этапом, следует вычесть из общего числа программ число программ с избегаемым этапом.

Так, рассмотренную в разделе "Программы с обязательным этапом" задачу можно решить так:

def ways(n, goal, zapret):
    if n>goal: return 0
    if n in zapret: return 0
    if n==goal: return 1
    return ways(n+1,goal, zapret)+ways(n+2,goal, zapret)+ways(n*2,goal, zapret)

print(ways(3,10,[])*ways(10,12,[]))
print(ways(3,12,[])-ways(3,12,[10]))

(Когда у нас нет "запрещенных" чисел, тогда в функцию передается пустой массив.)

Мы решили задачу двумя способами: рассмотренным ранее перемножением числа вариантов первого этапа (3-10) и числа вариантов второго этапа (10-12), а также вычитанием из общего числа программ числа тех программ, траектория которых не содержит числа 10. В обоих случаях получается одинаковый результат (как и следовало ожидать).

Аналогичным образом можно решить задачу на запрещенный этап, используя метод обязательного этапа:

def ways(n, goal, zapret):
    if n>goal: return 0
    if n in zapret: return 0
    if n==goal: return 1
    return ways(n+1,goal,zapret)+ways(n+2,goal,zapret)

print(ways(3,13,[8]))
print(ways(3,13,[])-ways(3,8,[])*ways(8,13,[]))

Эта идея позволяет легко решать задачи вроде следующей: получить из числа 11 число 29, пользуясь операциями "прибавь 1" и "прибавь 2", причем траектория вычислений должна содержать либо число 17, либо число 23, либо оба этих числа одновременно.

Решение можно найти, если из общего числа программ вычесть число таких программ, траектория которых не содержит ни числа 17, ни числа 23:

def ways(n, goal, zapret):
    if n>goal: return 0
    if n in zapret: return 0
    if n==goal: return 1
    return ways(n+1,goal,zapret)+ways(n+2,goal,zapret)

print(ways(11,29,[])-ways(11,29,[17,23]))

Программы с обязательным и избегаемым этапами

Часто встречаются задачи, в которых сочетаются обязательный и избегаемый этап. Например, требуется получить из числа 2 число 29, при этом разрешены операции "прибавить 1" и "умножить на 2", а траектория вычислений должна содержать число 14 и не должна содержать числа 25.

Эту задачу можно решить двумя способами. Можно подсчитать число способов получить из числа 2 число 14, а из числа 14 - число 29 и перемножить эти числа (разумеется, нужно учитывать запрет на число 25). Можно также подсчитать число способов получить из числа 2 число 29 с запретом на число 25, а затем вычесть из него количество программ, которые не проходят ни через число 14, ни через число 25 - так мы получим количество программ, которые не проходят число 25, но обязательно пройдут через число 14.

Оба эти способа иллюстрирует такая программа:

def ways(n, goal, zapret):
    if n>goal: return 0
    if n in zapret: return 0
    if n==goal: return 1
    return ways(n+1,goal,zapret)+ways(n*2,goal,zapret)

print(ways(2,14,[25])*ways(14,29,[25]))
print(ways(2,29,[25])-ways(2,29,[14,25]))

В некоторых задачах число обязательных и/или избегаемых этапов более одного. Рассмотрим задачу, в которой траектория вычислений должна содержать число 8 и не должна содержать чисел 10 и 11, в ней требуется из числа 1 получить число 28, а используемые операции - "прибавь 1", "прибавь 2" и "умножь на три".

Задача решается следующей программой (в ней опять-таки показаны два возможных способа решения):

def ways(n, goal, zapret):
    if n>goal: return 0
    if n in zapret: return 0
    if n==goal: return 1
    return ways(n+1,goal,zapret)+ways(n+2,goal,zapret)+ways(n*3,goal,zapret)

print(ways(1,8,[10,11])*ways(8,28,[10,11]))
print(ways(1,28,[10,11])-ways(1,28,[8,10,11]))

Если количество "обязательных" чисел более одного, то нам надо разбить путь не на два этапа, а более. Например, в одной из задач нужно получить из числа 2 число 15, пользуясь операциями "прибавь 1", "прибавь 2" и "умножь на три", а траектория вычислений должна содержать числа 4 и 11.

Разбиваем путь на три этапа: 2-4, 4-11, 11-15. Программа для решения жтой задачи следующая:

Ограничение на число команд программы или требования к командам

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

Имеются две операции:

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

Сколько существует программ, для которых при исходном числе 4 результатом является число 14, а предпоследней командой которых является команда «1»?

Очевидно, нам надо знать последовательность команд, с помощью которых был получен результат, и подсчитывать только те решения, которые удовлетворяют условию задачи.

Добавим в нашу рекурсивную функцию ways дополнительный параметр prog: строку, содержащую цепочку команд, выполненных прелылущими операциями. При выполнении операции 1 будем приписывать к этой строке цифру 1, а при выполнении операции 2 - цифру 2. Когда цель будет достигнута, проверим, что предпоследний символ нашей строки равен 1. (Напомним, что в Питоне s[-1] - это последний символ строки, s[-2] - предпоследний и т.д.) Если это не так, то не учитываем такое решение.

При вызове этой функции из основной программы в качестве параметра prog задаем пустую строку.

Вот программа целиком:

def ways(n, goal, prog):
    if n>goal: return 0
    if n==goal:
        if prog[-2]=='1': return 1
        else: return 0
    return ways(n+1,goal,prog+'1')+ways(n+2,goal,prog+'2')

print(ways(4,14,''))

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

Допустимые операции исполнителя следующие:

1. Прибавить 1
2. Прибавить 4
3. Умножить на 2

Требуется получить из числа 3 число 27, причем программа должна содержать ровно 7 команд.

Можно было бы передавать при вызовах строку команд, как в предыдущем примере, и при достижении цели проверять её длину. Но так как нам требуется лишь число команд, то можно использовать целую переменную, которую будем увеличивать на единицу при последующий вызовах. При достижении цели проверим, равно ли число команд требуемому. Если это условие выполнено, функция вернет 1, в противном случае - 0.

Приведем программу, решающую эту задачу:

def ways(n, goal, lprog):
    if n>goal: return 0
    if n==goal:
        if lprog==7: return 1
        else: return 0
    return ways(n+1,goal,lprog+1)+ways(n+4,goal,lprog+1)+ways(n*2,goal,lprog+1)

print(ways(3,27,0))

Количество результатов программы, состоящей из определенного числа команд

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

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

Количество всех программ сравнительно велико. Так, если допустимо n команд, а длина программы - k команд, то число всех возможных программ - это n**k (операция ** - это возведение в степень).

Рассмотрим конкретную задачу. Пусть у исполнителя есть две допустимые команды: "прибавить 1" и "умножить на 2 и вычесть 3". Требуется начать с числа 3 и подсчитать количество различных результатов, которые дадут все программы, состоящие ровно из 12 команд.

Вначале решим задачу без применения рекурсии. Первый этап - генерация всех возможных программ для исполнителя. Программа - это строка символов, в которых символ "0" обозначает первую команду, а "1" - вторую. Такую строку можно получить, перебрав все числа от 0 до 2**12-1 и преобразовав эти числа в двоичную запись. Это делается следующим фрагментом программы:

k=12
for i in range(2**k):
prog=bin(i)[2:]
if len(prog)<k: prog='0'*(k-len(prog)) + prog

Выражение bin(i)[2:] работает так: функция bin(i) преобразует целое число в его двоичное представление, которое начинается с символов "0b". Чтобы отрезать эти символы, используем операцию выделения подстроки [2:], которая удалаяет первые два символа. Если длина нашей строки prog менее k, мы приписываем к ней слева такое количество нулей, чтобы её длина было ровно k символов.

Теперь выполним полученную программу. Выбираем из строки символы по очереди. Если символ - "0", то выполняем операцию "прибавить 1", в противном случае - операцию "умножить на 2 и вычесть 3". Соответствующий фрагмент программы вышлядит так:

    n=start
    for j in range(k):
        if prog[j]=='0': n += 1
        else: n=2*n-3

После завешения этого цивла переменная n будет содержать результат выполнения текущей программы из k команд.

Чтобы полсчитать число различных резудьтатов, будем использовать массив a (изначально пустой). Если данное число не содержится в нём - добавим это число в массив:

if not n in a: a.append(n)

Когда закончится внешний цикл, то в массиве a будут содержаться все возможные результаты выполнения - под одному разу каждый. Всё, что осталось сделать - вывести количество элементов массива a:

print(len(a))

Приведем программу полностью:

k=12
start=3
a=[]
for i in range(2**k):
    prog=bin(i)[2:]
    if len(prog)<k: prog='0'*(k-len(prog)) + prog
    n=start
    for j in range(k):
        if prog[j]=='0': n += 1
        else: n=2*n-3
    if not n in a: a.append(n)
print(len(a))

Теперь решим ту же самую задачу с использованием рекурсии. Для этого напишем рекурсивную функцию f:

def f(n,l,k):
    if l==k:
        if not n in a: a.append(n)
        return
    f(n+1,l+1,k)
    f(2*n-3,l+1,k)
    return

Параметры функции следующие: n - текущее число, с которым работает исполнитель, l - текущее число команд, k - длина программ, которые требуется выполнять.

Если l равно k, это означает, что мы выполнили программу из k команд. Проверяем, содержится ли данный результат в массиве a, если нет - добавляем его в массив. После этого выходим из программы.

Если же требуемое количество команд ещё не выполнено, вызываем функцию два раза, первый - увеличив значение n на 1, второй - со значением 2*n-3. В обоих случаях увеличиваем l на 1, т.к. мы выполнили ещё одну команду.

Основная программа очень короткая: в ней переменной a присваивается пустой массив, вызывается функция f с параметром l, равным 0 (мы её не выполнили ни одноё команды), а после её завершения печатается количество элементов в массиве a.

Вот программа полностью:

def f(n,l,k):
    if l==k:
        if not n in a: a.append(n)
        return
    f(n+1,l+1,k)
    f(2*n-3,l+1,k)
    return

k=12
start=3
a=[]
f(start,0,k)
print(len(a))

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

Некоторые "хитрые" операции

В ряде задач встречаются "хитрые" операции получения следующего числа. Рассмотрим некоторые из них.

"Сделай нечётное". Если число чётное, к нему прибавляется 1, а если чётное, то 2. Результат достигается с помощью выражения n+n%2+1.

"Дописать справа 0" и "дописать справа 1". К десятичной записи числа справа приписывается ноль или единица. Такой результат дают выражения 10*n и 10*n+1 соответственно.

"Прибавить предыдущее" и "прибавить следующее". В первом случае к числу прибавляется число, меньшее на 1 (так, из числа 5 получается число 5+4, т.е. 9), во втором - на единицу большее. Соответствующие выражения - 2*n-1 и 2*n+1.

"Обнулить младший разряд". Операция обнуляет младший разряд в троичной записи числа. Соответствующее выражение - (n//3)*3. Внимание, тут есть подвох! Если последняя цифра числа в троичной записи - ноль (например, число 6 в троичной записи выглядит как 20), то число не изменяется и рекурсия зациклится. Поэтому надо проверять эту ситуацию и в случае, когда последняя цифра - ноль, не вызывать функцию. Для операций "отнять 2" и "обнулить младший разряд" функция ways может выглядеть так:

def ways(n, goal, zapret):
    if n<goal: return 0
    if n in zapret: return 0
    if n==goal: return 1
    if n%3==0: return ways(n-2,goal,zapret)
    else: return ways(n-2,goal,zapret)+ways((n//3)*3,goal,zapret)

(Обратите внимание: так как операции уменьшают число, то во второй строке функции используется операция сравнения "меньше", а не "больше".)

"Добавить слева 1". Операция приписывает к двоичной записи числа единицу слева. Это можно сделать, например, с помощью выражения int('1'+bin(n)[2:],2).

"Убрать последнюю цифру справа". Удаляется последняя цифра справа в десятичной записи числа. Это можно сделать целочисленным делением на 10: n//10.

"Обнулить". Первая слева цифра числа в двоичной записи не изменяется, а остальные заменяются нулями. Возможное выражение - n-int(bin(n)[3:],2). Тут тоже возможны неприятности, аналогичные упомянутым в операции "обнулить младший разряд" (см. выше).

"Прибавить следующее четное". К числу прибавляется минимальное четное число, превосходящее данное. Так, к числу 2 прибавляется 4, а к числу 5 - 6. Это можно сделать при помощи выражения 2*n+1+(n+1)%2.

"Сделать простое". Требуется получить простое число, большее, чем данное, и ближайшее в нему. Так, для числа 8 результатом должно быть число 11. Тут придется написать функцию, которая будет последовательно перебирать числа n+1, n+2 и т.д., пока не найдет простое число. Функция может выглядеть, например, так:

def makeprime(n):
    n += 1
    while True:
        k=2
        prime=True
        while k*k<=n:
            if n%k==0:
                prime=False
                break
            k += 1
        if prime: return n
        n += 1

(О простых числах и способах проверки "на простоту" я писал ранее.)

Задачи ЕГЭ 23 и 13 - по сути одна задача

Данная задача является подсчетом числа путей в ориентированном графе. Вершинами графа являются числа, а правила перехода от одного числа к другому задаются разрешенными в задаче операциями. Поэтому данная задача аналогична задаче ЕГЭ № 13, в которой рисуется схема дорог между городами и задается вопрос вроде: "Сколько существует различных путей из города А в город Н?"

Возникает вопрос: а можно ли решать программным путем и задачу 13? Разумеется, можно! Самая большая сложность - представить граф из задачи 13 в форме, удобной для компьютерной обработки. Впрочем, сложность эта вполне преодолима. Но более подробный рассказ об этом - тема для отдельной заметки.

Использованные выше задачи взяты с сайта "Решу ЕГЭ" (информатика) и с сайта К.Ю.Полякова.

Поиск по этому блогу

Информатика, ЕГЭ, Питон и т.п.