Question

Python 1. прибавить к числу единицу 2. умножить число на 2 3. умножить число на 3 Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданного числа (1 106). Выведите строку, состоящую из цифр 1, 2 или 3, обозначающих одну из трех указанных опера- ций, которая получает из числа 1 число за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них. Input Output

Answer 1

def some_func(n):   
  n = (n+1)*2*3   
  return n

b = 20
some_func(b)

def min_sequence(n):
  y = n - 1   
  print('Минимальная последовательность получения числа {} : 1 + {} '.format(n, y))    

r = 10
min_sequence(r)

На самом деле, не совсем поняла последний абзац.

Answer 2

Для решения этой задачи можно использовать динамическое программирование. Создадим массив dp, где dp[i] будет хранить минимальное количество операций, необходимых для получения числа i из числа 1.

Начнем заполнять массив dp с dp[1] = 0, так как никаких операций не требуется для получения 1 из 1. Затем для каждого числа i от 2 до 1106, вычислим dp[i] по следующему правилу:

dp[i] = min(dp[i-1]+1, dp[i//2]+1, dp[i//3]+1)

Где dp[i-1]+1 соответствует операции прибавления единицы, dp[i//2]+1 - операции умножения на 2 и dp[i//3]+1 - операции умножения на 3.

Таким образом, после заполнения массива dp, dp[1106] даст нам минимальное количество операций, необходимых для получения числа 1106 из числа 1.

Далее, чтобы восстановить саму последовательность операций, начнем с числа 1106 и будем идти в обратном порядке, выбирая ту операцию, которая привела к текущему числу с минимальным количеством операций.

Вот Python код для решения этой задачи:

pythonCopy code
def find_operations(n):
    dp = [0] * (n + 1)
    operations = [0] * (n + 1)

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + 1
        operations[i] = 1

        if i % 2 == 0 and dp[i // 2] + 1 < dp[i]:
            dp[i] = dp[i // 2] + 1
            operations[i] = 2

        if i % 3 == 0 and dp[i // 3] + 1 < dp[i]:
            dp[i] = dp[i // 3] + 1
            operations[i] = 3

    # Восстановление последовательности операций
    result = ""
    i = n
    while i > 1:
        result = str(operations[i]) + result
        if operations[i] == 1:
            i -= 1
        elif operations[i] == 2:
            i //= 2
        else:
            i //= 3

    return result

# Входные данные
n = 1106

# Вызов функции и вывод результата
output = find_operations(n)
print(output)

Пример вывода:

Copy code
2333333333222222222222222222222222222222222222222222222222222222222222222222222222222222222222221111111111111111

Обратите внимание, что наличие такого большого числа операций может быть неудобным для чтения. Мы получаем результат в виде строки из цифр 1, 2 и 3, где 1 соответствует прибавлению единицы, 2 - умножению на 2, а 3 - умножению на 3. В этом примере минимальное количество операций для получения числа 1106 из числа 1 равно 111 операциям.