一个程序有一个寄存器x,初始化为0,仅支持3个说明:
ldi V:加载(存储(即时值V,x x添加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。是否有更有效的方法来执行此操作?
如果通过"更有效",您的意思是"可能是正确的",则是。您当前的代码不适合所有输入。使用该SQR"通用卡",您不能微不足道地知道您正在查看的操作是否有益。例如
LDI 1
ADD -8
LDI 2
ADD -1
ADD 3
SQR
最大值来自(-8 -1(^2。您应该使用动态编程(请参阅第一个注释中提供的链接(在每个步骤中跟踪所有"最佳可能"结果。
您使用一个递归日常程序对此进行了古典编程,该例程在考虑到每个指令时尝试了两个分支:在最终答案中使用/不要使用该指令。然后,您会以X
的当前值和剩余的指令列表重复出现。
如果您想要进行数据流量分析,则您 can 应用各种换句话。例如,在任何ADD
指令的流中,您都可以将所有负值和所有正值组合到单个ADD
中。当您拥有LDI
时,您会考虑新值在真实值和绝对值上是否更大 - 后者是通过SQR
驱动改进的方法。
坦率地说,我建议您做一分子recur-dynamic_programming路线。
update
我给了这个想法。尽管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