Тема 23. Оператор присваивания и ветвления

23.02 Количество программ из A в B (на убывание)

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела оператор присваивания и ветвления

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#25996Максимум баллов за задание: 1

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

Вычесть $1$
Вычесть $3$
Взять остаток от деления на $4$

Команда $3$ выполняется только для чисел, больших, чем $4$ . Программа для исполнителя — это последовательность команд. Сколько существует таких программ, которые исходное число $22$ преобразуют в число $2$ ?

Показать ответ и решение

Рекурсия:

Решение рекурсией

Идея рекурсивного решения заключается в создании функции, которая считает количество программ, преобразующих число $x$ в число $y$ . Функция работает следующим образом:

- Если текущее число $x$ стало меньше целевого $y$ , дальнейшие команды не приводят к решению, возвращаем $0$ .

- Если $x$ равно $y$ , найден корректный путь, возвращаем $1$ .

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

1. Если $x > 4$ , можно применить команду 3 (взять остаток от деления на 4), а также команды 1 и 2 (вычесть 1 и вычесть 3).

2. Если $x ≤ 4$ , команда 3 недоступна, применяем только команды 1 и 2.

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

# Определяем функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число меньше целевого, путь невозможен
    if x < y:
        return 0
    # Если текущее число равно целевому, найден корректный путь
    elif x == y:
        return 1
    else:
        # Если текущее число больше 4, доступны все три команды
        if x > 4:
            return f(x - 1, y) + f(x - 3, y) + f(x % 4, y)
        else:
            # Иначе доступно только вычитание 1 и 3
            return f(x - 1, y) + f(x - 3, y)

# Запускаем функцию от исходного числа 22 до 2
print(f(22, 2))

—

Решение динамикой

Динамический подход заключается в построении массива, где индекс соответствует числу, а значение по индексу — количество программ, ведущих к этому числу, начиная с 22.

- Создаем массив длиной 23 (индексы от 0 до 22) и устанавливаем $a[22] = 1$ , так как существует один способ быть в начале.

- Проходим циклом по числам от 22 до 2 в обратном порядке (с помощью reversed(range(2,23))), чтобы суммировать пути для меньших чисел.

- Для каждого числа $i$ обновляем массив:

- прибавляем к $a[i − 1]$ количество программ для $i$ , так как можно вычесть 1;

- прибавляем к $a[i − 3]$ количество программ для $i$ , так как можно вычесть 3;

- если $i > 4$ , прибавляем к $a[i%4 ]$ количество программ для $i$ , так как можно взять остаток от деления на 4.

- После завершения цикла $a[2]$ содержит количество программ, преобразующих 22 в 2.

# Создаем массив для хранения количества программ до числа 22
a = [0] * 23  # Индексы от 0 до 22
# Начальное число 22 имеет одну траекторию
a[22] = 1

# Перебираем числа от 22 до 2 в обратном порядке
for i in reversed(range(2, 23)):
    # Применяем команду "вычесть 1"
    a[i-1] += a[i]
    # Применяем команду "вычесть 3"
    a[i-3] += a[i]
    # Применяем команду "взять остаток от деления на 4", если i > 4
    if i > 4:
        a[i % 4] += a[i]

# Выводим количество программ для достижения числа 2
print(a[2])

Ответ: 1873

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#26075Максимум баллов за задание: 1

Вычесть $1$ ;
Вычесть $3$ ;
Разделить нацело на $3$ .

При выполнении команды $3$ выполняется деление нацело (остаток отбрасывается). Программа для исполнителя — это последовательность команд. Сколько существует таких программ, которые исходное число $22$ преобразуют в число $2$ ?

Показать ответ и решение

Решение рекурсией

Идея решения с помощью рекурсии состоит в создании функции f(a, b), которая считает количество программ, преобразующих число $a$ в число $b$ . На каждом шаге проверяются следующие условия:

- Если $a$ равно $b$ , то найден корректный путь и функция возвращает 1;

- Если $a$ стало меньше $b$ , то путь невозможен и возвращается 0;

- Если ни одно из условий не выполнено, функция вызывает саму себя трижды, моделируя каждую из команд: a-1 (вычесть 1), a-3 (вычесть 3) и a//3 (целочисленное деление на 3). Сумма этих трёх вызовов даёт общее количество программ для текущего значения $a$ .

Таким образом, при вызове f(22, 2) функция рекурсивно перебирает все допустимые последовательности команд, подсчитывая количество способов достичь числа 2.

# Определяем рекурсивную функцию f(a, b) для подсчета программ
def f(a, b):
    # Если текущее число равно целевому числу,
    # то найден один корректный путь, возвращаем 1
    if a == b:
        return 1
    # Если текущее число меньше целевого,
    # дальнейшие преобразования невозможны, возвращаем 0
    if a < b:
        return 0
    # В остальных случаях считаем все возможные варианты:
    # 1) вычесть 1
    # 2) вычесть 3
    # 3) разделить нацело на 3
    # Суммируем количество программ из каждого варианта
    return f(a - 1, b) + f(a - 3, b) + f(a // 3, b)

# Запускаем функцию для исходного числа 22 и целевого числа 2
print(f(22, 2))

—

Решение динамикой

Динамический способ решения основывается на обратном построении массива, где индекс $i$ соответствует числу на экране, а значение в ячейке $a[i]$ — количество способов из исходного числа 22 дойти до числа $i$ .

- Сначала создаём массив, заполненный нулями, длиной достаточной для хранения всех промежуточных значений, например, 70 элементов; - В ячейку с индексом 22 записываем 1, так как начинаем с числа 22 и существует ровно один способ быть в этом положении; - Затем проходим в цикле от 21 до 2 включительно, и для каждого числа $i$ вычисляем количество программ, суммируя:

- $a[i+ 1]$ — количество программ, которые придут к $i$ через команду "вычесть 1";

- $a[i+ 3]$ — количество программ, которые придут к $i$ через команду "вычесть 3";

- $a[i∗3]$ , $a[i∗3 + 1]$ , $a[i∗3 + 2]$ — количество программ, которые придут к $i$ через команду "разделить нацело на 3 учитывая, что при делении нацело все числа $i∗ 3$ , $i∗ 3+ 1$ , $i∗ 3+ 2$ дают в результате $i$ .

После заполнения всех ячеек, значение $a[2]$ будет содержать общее количество программ, которые преобразуют число 22 в число 2.

# Создаем массив из 70 элементов, все значения изначально равны 0
a = [0] * 70
# Начальное число 22 имеет ровно один способ быть в позиции
a[22] = 1
# Перебираем все числа от 21 до 2 включительно в обратном порядке
for i in range(21, 1, -1):
    # Считаем количество программ для числа i,
    # суммируя варианты, которые приведут к i:
    # 1) из i+1 командой "вычесть 1"
    # 2) из i+3 командой "вычесть 3"
    # 3) из i*3, i*3+1, i*3+2 командой "разделить нацело на 3"
    a[i] = a[i + 1] + a[i + 3] + a[i * 3] + a[i * 3 + 1] + a[i * 3 + 2]

# Выводим количество программ, преобразующих 22 в 2
print(a[2])

Ответ: 2196

Ошибка.
Попробуйте повторить позже

Задача 3#26129Максимум баллов за задание: 1

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

1. Разделить на $2$ с округлением вниз (выполнить целочисленное деление на $2$ )

2. Вычесть $1$

Первая команда уменьшает число на экране в $2$ раза, вторая — уменьшает его на $1$ . Программа для исполнителя — это последовательность команд.

Определите количество программ, которые число $64$ преобразуют в число $14$ .

Показать ответ и решение

Решение рекурсией

Идея рекурсивного решения заключается в том, чтобы построить функцию, которая считает количество всех программ, преобразующих число $a$ в число $b$ . Функция работает следующим образом: если текущее число $a$ равно целевому числу $b$ , значит найден один корректный путь, и функция возвращает 1; если текущее число $a$ меньше $b$ , значит дальнейшие операции невозможны и путь недопустим, функция возвращает 0; в остальных случаях функция вызывает саму себя дважды: первый вызов с аргументом $a∕∕2$ , что соответствует команде «разделить на 2», второй вызов с аргументом $a − 1$ , что соответствует команде «вычесть 1». Результаты этих вызовов суммируются, чтобы получить общее количество программ. Вызов функции f(64,14) рекурсивно перебирает все варианты команд, подсчитывая все возможные последовательности от 64 до 14.

# Определяем рекурсивную функцию f(a, b), считающую количество программ
def f(a, b):
    # Если текущее число равно целевому, значит найден корректный путь
    if a == b:
        return 1
    # Если текущее число стало меньше целевого, путь невозможен
    if a < b:
        return 0
    # В остальных случаях пробуем два варианта:
    # 1) разделить число на 2 целочисленно
    # 2) вычесть 1
    # и суммируем количество таких программ
    return f(a // 2, b) + f(a - 1, b)

# Запускаем функцию от 64 до 14 и выводим результат
print(f(64, 14))

—

Решение динамикой

Динамический способ решения строится на том, что мы создаем массив, где каждый индекс $i$ соответствует числу, а значение по этому индексу показывает количество способов преобразовать 64 в число $i$ . Изначально создаем массив из 65 элементов (от 0 до 64) и присваиваем $a[64] = 1$ , так как стартуем с числа 64 и существует ровно один способ быть в этом положении. Затем проходим по массиву от 64 вниз до 15, для каждого числа $i$ распределяя его количество способов на два числа, в которые можно перейти: $i∕∕2$ (команда «разделить на 2») и $i − 1$ (команда «вычесть 1»), суммируя к уже существующим значениям. После завершения цикла в $a[14]$ хранится общее количество программ, преобразующих 64 в 14.

# Создаем массив для хранения количества программ для чисел от 0 до 64
a = [0] * 65
# Начальное число 64, количество способов быть в нём равно 1
a[64] = 1
# Проходим по всем числам от 64 вниз до 15
for i in range(64, 14, -1):
    # Для каждого числа i распределяем количество способов
    # на число i//2 (разделить на 2) и i-1 (вычесть 1)
    a[i // 2] += a[i]
    a[i - 1] += a[i]

# Выводим количество программ, которые ведут от 64 к 14
print(a[14])

Ответ: 63

Ошибка.
Попробуйте повторить позже

Задача 4#30471Максимум баллов за задание: 1

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

Вычесть $3$
Поделить на $3$ , если число кратно $3$
Поделить на $2$ , если число кратно $2$

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

Сколько существует программ, для которых при исходном числe $30$ результатом является число $3$ ?

Показать ответ и решение

Решение рекурсией

Идея рекурсивного решения заключается в том, чтобы определить функцию f(st, fn), которая считает количество различных программ, преобразующих число st в число fn.

На каждом шаге выполняются следующие проверки:

- Если st == fn, значит текущее число совпало с целевым, найден один путь, возвращаем 1.

- Если st < fn, то текущее число меньше целевого, дальнейшие преобразования невозможны, возвращаем 0.

- Иначе функция делает три рекурсивных вызова:

1. f(st // 3, fn) * (st % 3 == 0) — учитываем команду "поделить на 3"только если число кратно 3, иначе результат будет 0.

2. f(st // 2, fn) * (st % 2 == 0) — учитываем команду "поделить на 2"только если число кратно 2, иначе результат будет 0.

3. f(st - 3, fn) — учитываем команду "вычесть 3".

Итоговое количество программ вычисляется как сумма этих трёх значений. Запуск функции с начальными аргументами f(30, 3) подсчитает все возможные последовательности команд.

# Определяем рекурсивную функцию f(st, fn), которая считает количество программ
def f(st, fn):
    # Если текущее число совпало с целевым, возвращаем 1
    if st == fn:
        return 1
    # Если текущее число меньше целевого, пути нет, возвращаем 0
    if st < fn:
        return 0
    # Считаем количество программ, использующих команду "поделить на 3", если число кратно 3
    x = f(st // 3, fn) * (st % 3 == 0)
    # Считаем количество программ, использующих команду "поделить на 2", если число кратно 2
    y = f(st // 2, fn) * (st % 2 == 0)
    # Считаем количество программ, использующих команду "вычесть 3"
    z = f(st - 3, fn)
    # Суммируем все возможные варианты
    return x + y + z

# Вызываем функцию для исходного числа 30 и целевого числа 3
print(f(30, 3))

—

Решение динамикой

Идея динамического решения состоит в том, чтобы построить массив a, где индекс соответствует числу, а значение — количеству способов добраться от этого числа до целевого.

- Инициализируем массив нулями: a = [0] * 100.

- В ячейку с индексом 30 записываем 1, так как мы начинаем с числа 30.

- Проходим по всем числам от 29 до 3 (включительно) в обратном порядке. Для каждого числа i считаем количество способов, складывая:

1. a[i + 3] — вариант "вычесть 3"из числа i + 3 приводит в i.

2. a[i * 3] — вариант "поделить на 3"из числа i * 3 приводит в i.

3. a[i * 2] — вариант "поделить на 2"из числа i * 2 приводит в i.

После заполнения массива, значение a[3] будет содержать количество программ, преобразующих число 30 в число 3.

# Создаем массив из 100 элементов, все значения изначально равны 0
a = [0] * 100
# Исходное число 30 имеет один способ быть на этом месте
a[30] = 1
# Перебираем числа от 29 до 3 включительно в обратном порядке
for i in range(29, 2, -1):
    # Количество способов для i равно сумме способов из i+3, i*3 и i*2
    a[i] = a[i + 3] + a[i * 3] + a[i * 2]

# Выводим количество программ, которые ведут от 30 к 3
print(a[3])

Ответ: 23

Ошибка.
Попробуйте повторить позже

Задача 5#52529Максимум баллов за задание: 1

Исполнитель Бот решил сыграть в игру. Он преобразовывает числа на доске с помощью трёх команд:

1. Вычесть 2

2. Вычесть 3

3. Извлечь корень

Первые две команды уменьшают число на доске на 2 и 3 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 25 в число 3?

Показать ответ и решение

Решение рекурсией

Идея рекурсивного решения состоит в том, чтобы построить функцию f(x, y), которая подсчитывает количество последовательностей команд, переводящих число $x$ в число $y$ . Внутри функции задаём три случая:

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

- Если $x$ равно $y$ , значит найден корректный путь, и функция возвращает 1.

- Если ни одно из этих условий не выполнено, функция рекурсивно вызывает сама себя три раза: первый раз с аргументом $x − 2$ (команда "вычесть 2"), второй раз с аргументом $x − 3$ (команда "вычесть 3"), третий раз с аргументом $√ -- x$ (команда "извлечь квадратный корень"). Сумма этих трёх значений даст количество всех программ, которые переводят $x$ в $y$ .

# Определяем функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число меньше целевого, то путь невозможен
    if x < y:
        return 0
    # Если текущее число совпало с целевым, значит найден один путь
    elif x == y:
        return 1
    # В остальных случаях считаем все возможные переходы:
    # вычесть 2, вычесть 3 и извлечь квадратный корень
    else:
        return f(x - 2, y) + f(x - 3, y) + f(x ** 0.5, y)

# Запускаем функцию от 25 до 3 и выводим результат
print(f(25, 3))

—

Решение динамикой

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

- Инициализируем массив длиной, достаточной для всех промежуточных чисел (например, 1000 элементов), и присваиваем a[25] = 1, так как изначально мы находимся в числе 25, и существует ровно один способ быть в этом положении.

- Проходим по массиву в обратном порядке от 24 до 3 (включительно), для каждого числа i вычисляем количество способов дойти до него:

1. Добавляем a[i + 2], так как из числа i+2 можно получить i командой "вычесть 2".

2. Добавляем a[i + 3], так как из числа i+3 можно получить i командой "вычесть 3".

3. Добавляем a[i ** 2], так как из числа î2 можно получить i командой "извлечь квадратный корень".

- После завершения цикла значение a[3] даст общее количество программ, которые переводят 25 в 3.

# Создаем массив для хранения количества способов для чисел до 1000
a = [0] * 1000
# Исходное число 25 имеет один способ быть достигнутым
a[25] = 1
# Проходим по всем числам от 24 до 3 включительно
for i in range(24, 2, -1):
    # Количество способов добраться до i равно сумме:
    # из i+2 командой "вычесть 2",
    # из i+3 командой "вычесть 3",
    # из i**2 командой "извлечь корень"
    a[i] = a[i + 2] + a[i + 3] + a[i ** 2]
# Выводим количество программ, приводящих от 25 к 3
print(a[3])

Ответ: 238

Ошибка.
Попробуйте повторить позже

Задача 6#57112Максимум баллов за задание: 1

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

А. Вычти 3

Б. Вычти 5

В. Найди целую часть от деления на 3

Первая из них уменьшает число на экране на 3, вторая уменьшает число на экране на 5, третья заменяет число на экране на целую часть от деления числа на 3. Программа для исполнителя — это последовательность команд.

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

Показать ответ и решение

Рекурсия:

Решение рекурсией

Идея рекурсивного решения состоит в том, чтобы определить функцию f(x, y), которая возвращает количество программ, преобразующих число $x$ в число $y$ .

- Сначала проверяем, не стало ли число меньше целевого. Если $x < y$ , то дальнейшее применение команд приведет к числам меньше $y$ , поэтому путь невозможен, возвращаем $0$ .

- Если $x == y$ , значит достигнут целевой результат, и найден один корректный путь, возвращаем $1$ .

- Если ни одно из условий не выполнено, вызываем функцию рекурсивно трижды, соответствуя трем командам:

1. x-3 — уменьшение на 3

2. x-5 — уменьшение на 5

3. x//3 — целая часть от деления на 3

Каждый вызов возвращает количество программ для соответствующего перехода, и мы суммируем эти три значения, чтобы получить общее количество программ от $x$ до $y$ .

Так как траектория должна проходить через числа 68 → 35 → 14 → 4, общее количество программ вычисляется как произведение трёх рекурсивных вызовов: f(68, 35) * f(35, 14) * f(14, 4).

# Определяем рекурсивную функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число стало меньше целевого,
    # путь невозможен, возвращаем 0
    if x < y:
        return 0
    # Если текущее число совпало с целевым,
    # значит найден подходящий путь, возвращаем 1
    elif x == y:
        return 1
    # В остальных случаях считаем все возможные варианты переходов:
    # вычесть 3, вычесть 5, разделить нацело на 3
    else:
        return f(x - 3, y) + f(x - 5, y) + f(x // 3, y)

# Вычисляем количество программ, проходящих через все ключевые числа: 68 -> 35 -> 14 -> 4
print(f(68, 35) * f(35, 14) * f(14, 4))

—

Решение динамикой

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

1. Создаем массив a длиной достаточно большой, чтобы покрыть все числа от исходного до целевого, и заполняем его нулями.

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

3. Проходим по массиву в обратном порядке от 68 до 4:

- Если текущий индекс равен 14 или 35, обнуляем все предыдущие ячейки, чтобы учесть условие, что траектория должна пройти через эти числа.

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

- i - 3

- i - 5

- i // 3

4. После прохода по всем значениям, ячейка a[4] содержит общее количество программ, ведущих от 68 к 4 с учётом прохождения через 35 и 14.

# Создаем массив для подсчета количества программ, все элементы инициализируем нулями
a = [0] * 1000
# В ячейку с индексом 68 записываем 1, стартуем с числа 68
a[68] = 1
# Проходим по всем числам от 68 до 4 включительно, двигаясь вниз
for i in range(68, 3, -1):
    # Если текущий индекс 14 или 35, обнуляем все ячейки ниже текущей,
    # чтобы траектория учитывала прохождение через эти числа
    if i == 14 or i == 35:
        for j in range(i):
            a[j] = 0
    # Применяем команды и суммируем количество программ для соответствующих чисел
    a[i - 3] += a[i]
    a[i - 5] += a[i]
    a[i // 3] += a[i]

# Выводим общее количество программ, ведущих к числу 4
print(a[4])

Ответ: 2024

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#63351Максимум баллов за задание: 1

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

1. Вычесть 2

2. Вычесть 3

3. Извлечь корень

Первые две команды уменьшают число на доске на 2 и 3 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя - это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 25 в число 3?

Показать ответ и решение

Решение рекурсией

Идея рекурсивного решения заключается в том, чтобы определить функцию F(x, y), которая будет возвращать количество программ, преобразующих число $x$ в число $y$ . Алгоритм строится следующим образом:

- Если текущее число $x$ совпало с целевым $y$ , то найден один корректный путь, и функция возвращает 1.

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

- Если ни одно из условий не выполнено, функция рекурсивно вызывает сама себя для каждого возможного действия:

1. x - 2 — уменьшение на 2, прибавляем результат к общему числу программ.

2. x - 3 — уменьшение на 3, прибавляем результат к общему числу программ.

3. pow(x, 0.5) — извлечение квадратного корня возведением в степень 0.5, но только если число неотрицательное; добавляем результат к общему числу программ.

Таким образом, функция постепенно перебирает все возможные последовательности команд от числа 25 до числа 3. Каждый рекурсивный вызов делит задачу на подзадачи, соответствующие одному шагу программы, и суммирует результаты. Вызов F(25, 3) вернёт итоговое количество всех программ.

# Определяем функцию F(x, y), которая считает количество программ
def F(x, y):
    # Если текущее число совпало с целевым, возвращаем 1
    if x == y:
        return 1
    # Если текущее число стало меньше целевого, путь невозможен, возвращаем 0
    if x < y:
        return 0
    # Если текущее число больше целевого, считаем все возможные действия
    # Вычесть 2 и рекурсивно вычислить количество программ
    # Вычесть 3 и рекурсивно вычислить количество программ
    # Извлечь квадратный корень, если x >= 0, и рекурсивно вычислить количество программ
    if x > y:
        return F(x - 2, y) + F(x - 3, y) + (F(pow(x, 0.5), y) if x >= 0 else 0)

# Вызываем функцию от 25 до 3 и выводим результат
print(F(25, 3))

Ответ: 238

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания