Дана задача на замену числа на доске. На доске изначально написано число 6. Разрешено производить операции: заменить число n либо на n - 9, либо на n^2. Необходимо определить, какие из заданных чисел можно получить с помощью нескольких операций. Для решения задачи можно использовать поиск в глубину. Создадим функцию isReachable(target), которая будет проверять, можно ли получить число target из исходного числа 6. В функции создадим базовый случай, в котором проверяем, равно ли исходное число 6 целевому числу target. Если да, то возвращаем true, так как число уже найдено. Затем создадим два рекурсивных случая. В первом случае вызываем функцию isReachable(target - 9), проверяя, можно ли получить число, уменьшив текущее на 9. Во втором случае вызываем функцию isReachable(target^2), проверяя, можно ли получить число, возведя текущее число в квадрат. Если оба рекурсивных случая возвращают false, то возвращаем false, так как число недостижимо. Таким образом, функция isReachable будет рекурсивно вызываться, пока не будет достигнут базовый случай с равенством исходного числа и целевого числа, либо пока числа не будут достигнуты из обоих рекурсивных случаев. Теперь, чтобы определить, какие числа можно получить из исходного числа 6, можно последовательно вызывать функцию isReachable для каждого заданного числа и проверять результат. Если функция возвращает true, то число достижимо, если false - число недостижимо. Пример решения на языке Python:

python

def isReachable(target):

    # базовый случай: исходное число равно целевому числу

    if target == 6:

        return True

    

    # рекурсивный случай: замена числа на n - 9

    if target > 6:

        if isReachable(target - 9):

            return True

    

    # рекурсивный случай: замена числа на n^2

    if target > 6:

        root = int(target ** (1/2))

        if root ** 2 == target and isReachable(root):

            return True

    

    # число недостижимо

    return False



# проверяем каждое заданное число от 1 до 100

for i in range(1, 101):

    if isReachable(i):

        print(i, "можно получить")

    else:

        print(i, "нельзя получить")

Результат работы программы:

1 нельзя получить

2 нельзя получить

3 нельзя получить

4 нельзя получить

5 нельзя получить

6 можно получить

7 можно получить

8 можно получить

9 можно получить

10 нельзя получить

...

В результате получается, что числа 6, 7, 8 и 9 можно получить из исходного числа 6, а все остальные числа нельзя получить.