Skip to main content

Задание 23

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

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

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

Пример 1​

Задача

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

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

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

public class Example1 {

    // кол-во подходящих программ
    static int cnt = 0;

    // следующий ход, value - текущее значение, met - ответ на вопрос, встречено ли число 10
    static void next(int value, boolean met) {
        // если значение больше целевого, то оно точно не встретится
        if (value > 20)
            // поэтому завершаем выполнение программы
            return;
        // если значение равно целевому
        if (value == 20) {
            // если при этом встречено число 10
            if (met)
                // увеличиваем счётчик подходящих программ на 1
                cnt++;
            return;
        }
        // если значение равно 10
        if (value == 10)
            // говорим, что число 10 встречено
            met = true;
        // увеличиваем значение на 1 и запускаем обработку следующего хода
        next(value + 1, met);
        // умножаем значение на 2 и запускаем обработку следующего хода
        next(value * 2, met);
    }

    public static void main(String[] args) {
        // запускаем программу для значения 1
        next(1, false);
        // выводим количество подходящих программ
        System.out.println(cnt);
    }
}

Вывод программы:

28

Ответ: 28

Пример 2​

Задача

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

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

Первая команда увеличивает число на экране на 1, вторая – увеличивает его на 2, а третья – умножает его на 3. Программа для исполнителя М17 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и при этом траектория вычислений содержит числа 8 и 10?

public class Example2 {

    // кол-во подходящих программ
    static int cnt = 0;

    // следующий ход, value - текущее значение, met8 - ответ на вопрос, встречено ли число 8,
    // met10 - ответ на вопрос, встречено ли число 10
    static void next(int value, boolean met8, boolean met10) {
        // если значение больше целевого, то оно точно не встретится
        if (value > 12)
            // поэтому завершаем выполнение программы
            return;
        // если значение равно целевому
        if (value == 12) {
            // если при этом встречено число 10
            if (met8 && met10)
                // увеличиваем счётчик подходящих программ на 1
                cnt++;
            return;
        }
        // если значение равно 10
        if (value == 10)
            // говорим, что число 10 встречено
            met10 = true;
        // если значение равно 8
        if (value == 8)
            // говорим, что число 8 встречено
            met8 = true;
        // увеличиваем значение на 1 и запускаем обработку следующего хода
        next(value + 1, met8, met10);
        // увеличиваем значение на 2 и запускаем обработку следующего хода
        next(value + 2, met8, met10);
        // умножаем значение на 3 и запускаем обработку следующего хода
        next(value * 3, met8, met10);
    }

    public static void main(String[] args) {
        // запускаем программу для значения 1
        next(2, false, false);
        // выводим количество подходящих программ
        System.out.println(cnt);
    }
}

Вывод программы:

60

Ответ: 60

Пример 3​

Задача

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

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

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

public class Example3 {

    // кол-во подходящих программ
    static int cnt = 0;

    // следующий ход, value - текущее значение, met14 - ответ на вопрос, встречено ли число 14,
    // met25 - ответ на вопрос, встречено ли число 25
    static void next(int value, boolean met14, boolean met25) {
        // если значение больше целевого, то оно точно не встретится
        if (value > 29)
            // поэтому завершаем выполнение программы
            return;
        // если значение равно целевому
        if (value == 29) {
            // если при этом встречено число 10
            if (met14 && !met25)
                // увеличиваем счётчик подходящих программ на 1
                cnt++;
            return;
        }
        // если значение равно 25
        if (value == 25)
            // говорим, что число 25 встречено
            met25 = true;
        // если значение равно 14
        if (value == 14)
            // говорим, что число 14 встречено
            met14 = true;
        // увеличиваем значение на 1 и запускаем обработку следующего хода
        next(value + 1, met14, met25);
        // умножаем значение на 2 и запускаем обработку следующего хода
        next(value * 2, met14, met25);
    }

    public static void main(String[] args) {
        // запускаем программу для значения 1
        next(2, false, false);
        // выводим количество подходящих программ
        System.out.println(cnt);
    }
}

Вывод программы:

13

Ответ: 13