Программное решение задач ЕГЭ по информатике

Задача 5543. Источник: Поляков. Задание КИМ 23

Страница задачи 5543

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

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

Выполняя первую из них, исполнитель увеличивает число на экране на 2, выполняя вторую – умножает на 3, выполняя третью – умножает на 4. Программой для исполнителя называется последовательность команд. Сколько существует различных программ, которые преобразуют исходное число 1 в число 600, и при этом траектория вычислений не содержит двух идущих подряд нечётных чисел.

Решение

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

Python

def r(a):
    if a[-1] > 600:
        return 0
    if a[-1] == 600:
        for i in range(len(a) - 1):
            if a[i] % 2 == 1 and a[i + 1] % 2 == 1:
                return 0
        return 1
    return r(a + [a[-1] + 2]) + r(a + [a[-1] * 3]) + r(a + [a[-1] * 4])


print(r([1]))

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

Python

def r(n=0):
    if a[n] > 600:
        return 0
    if a[n] == 600:
        for i in range(n - 1):
            if a[i] % 2 == 1 and a[i + 1] % 2 == 1:
                return 0
        return 1
    a[n + 1] = a[n] + 2
    k = r(n + 1)
    a[n + 1] = a[n] * 3
    k += r(n + 1)
    a[n + 1] = a[n] * 4
    k += r(n + 1)
    return k


a = [1] * 301
print(r())

PascalABC

var
    a: Array [1..301] of Integer;
function r(n: Integer := 1): Integer;
begin
    Result := 0;
    if a[n] > 600 then
        Exit;
    if a[n] = 600 then
    begin
        for var i := 1 to n - 1 do
            if (a[i] mod 2 = 1) and (a[i + 1] mod 2 = 1) then
                Exit;
        Result := 1;
    end
    else
    begin
        a[n + 1] := a[n] + 2;
        Result := Result + r(n + 1);
        a[n + 1] := a[n] * 3;
        Result := Result + r(n + 1);
        a[n + 1] := a[n] * 4;
        Result := Result + r(n + 1);
    end;
end;

begin
    a[1] := 1;
    Writeln(r());
end.

C++

#include <iostream>
using namespace std;
int a[301];
int r(int n = 0)
{
    if (a[n] > 600)
        return 0;
    if (a[n] == 600)
    {
        for (int i = 0; i <= n - 1; i++)
            if (a[i] % 2 == 1 and a[i + 1] % 2 == 1)
                return 0;
        return 1;
    }
    a[n + 1] = a[n] + 2;
    int k = r(n + 1);
    a[n + 1] = a[n] * 3;
    k += r(n + 1);
    a[n + 1] = a[n] * 4;
    k += r(n + 1);
    return k;
}

int main()
{
    a[0] = 1;
    cout << r() << endl;
}

Ответ

20375

Отправить замечание по решению

Код по которому имеется замечание:

Ваш вариант кода:

Комментарий: