Простые инструкции Python Реализация

Question

Программа имеет один регистр X, инициализированный в 0, и поддерживает только 3 инструкции:

LDI v: загрузить (сохранить) непосредственное значение v в X ADD v: добавить непосредственное значение vв X и сохраните результат в X. SQR: возведите в квадрат значение X и сохраните результат в X.

Пример того, как на значение повлияет короткая последовательность инструкций:

Instruction     X
LDI 5           5
ADD 2           7
SQR             49
ADD -4          44
LDI -3          -3
SQR             9

Проблема, которую мне нужно решить, состоит в том, чтобы пропустить выбранные инструкции, чтобы получить максимально возможное значение для X в конце программы.

Что у меня есть:

def prog(n):
    x = 0
    arr = []
    for i in range(n):
        itm = input().split()
        arr += [(itm)]
    #arr_rev = arr[::-1]    
    #limit = arr_rev.index(["SQR"])+len(arr)-1
    limit = len(arr) - 1 - arr[::-1].index(['SQR'])

    for i in range(len(arr)):
        if i < limit:
            if arr[i][0] == "ADD":
                x += int(arr[i][1])
            elif arr[i][0] == "LDI":
                x = int(arr[i][1])
            elif arr[i][0] == "SQR":
                x = x**2
        else:
            if arr[i][0] == "ADD" and int(arr[i][1]) > 0:
                x += int(arr[i][1])
            elif arr[i][0] == "LDI" and int(arr[i][1]) > x:
                x = int(arr[i][1])
            elif arr[i][0] == "SQR":
                x = x**2

    return x

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

Однако квадрат отрицательное число делает его положительным, поэтому приведенная выше стратегия может работать не во всех случаях,Я исключил это правило во всех случаях, пока не сдам последний SQR.Есть ли более эффективный способ сделать это?

Answer 1

Если под «более эффективным» вы подразумеваете «может быть правильным», то да .Ваш текущий код не работает для всех входов.С этим «подстановочным знаком» SQR вы не можете легко узнать, полезна ли операция, на которую вы смотрите.Например,

LDI  1
ADD -8
LDI  2
ADD -1
ADD  3
SQR

Максимальное значение получается из (-8 + -1) ^ 2.Вы должны использовать динамическое программирование (см. Ссылку, приведенную в первом комментарии), чтобы отслеживать все «наилучшие возможные» результаты на каждом шаге.

Вы классически программируете это с помощью рекурсивной подпрограммы, которая пробует две ветви, как считаеткаждая инструкция: используйте / не используйте эту инструкцию в окончательном ответе.Затем вы возвращаетесь с текущим значением X и оставшимся списком инструкций.

---

Если вы хотите, чтобы провел анализ потока данных, вы можете применять различные короткие пути.Например, в любом потоке ADD инструкций вы можете объединить все отрицательные и все положительные значения в один ADD.Когда у вас есть LDI, вы учитываете, больше ли новое значение как в истинном, так и в абсолютном значении - последнее является тем, что приводит к улучшению через SQR.

Честно говоря, я рекомендую сделать пополамrecur-dynamic_programming route.

---

ОБНОВЛЕНИЕ

Я больше об этом думал.Хотя DP - это путь для решения больших проблем, это - , а не , что вы хотите атаковать первым (на мой взгляд).Скорее, атакуйте проблему того, стоит ли включать каждую конкретную команду.Вам нужно будет сделать оба, до дальнейшей доработки.Вы даже не можете гарантировать, что хотите включить команду SQR: последующее вычитание может сделать ее нежелательной.

Логика рекурсии выглядит примерно так:

def optimize(x_reg, command_list):
    # x_reg          current value of the X register
    # command_list   remaining list of commands

    # base case
    if len(command_list) == 0
         return x_reg

    # recursion case
    op = command_list[0][0]
    if op == "ADD":
        new_x = x_reg + command_list[0][1]
    elif op == "LDI":
        new_x = command_list[0][1]
    else:    # op == "SQR":
        new_x = x_reg * x_reg

    with_op = optimize(new_x, command_list[1:])  # Use the command
    sans_op = optimize(x_reg, command_list[1:])  # Don't use the command

    return max(with_op, sans_op)    # Return the larger of the two solutions found