子数列的记忆迭代法问题的解法
第一个用了迭代法计算成功了
def targetSum(S, i, tgt):
# your code here
k = len(S)
# If calculation with this input is already computed return result from mem
if tgt < 0:
return float('inf')
if i >= k and tgt >= 0:
return tgt
else:
minimum = min(targetSum(S, i+1, tgt-S[i]), targetSum(S, i+1, tgt))
# Store result of current calculation in mem if needed again later
print(minimum)
return minimum
def tgtSum(tgt, S):
return targetSum(S, 0, tgt)
t6 = (tgtSum(457, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1
assert t6 == 1, 'Test 6 failed'
第二个问题
def memoTargetSum(S, tgt):
k = len(S)
assert tgt >= 0
## Fill in base case for T[(i,j)] where i == k
T = {} # Memo table initialized as empty dictionary
for j in range(tgt+1):
T[(k,j)] = j
# your code here
for i in range(k-1,-1,-1):
for j in range(tgt,-1,-1):
if T[(i + 1, j)]-S[i] < 0:
T[(i,j)] = T[(i + 1, j)]
else:
T[(i,j)] = T[(i + 1, j)]-S[i]
return T
第二个代码有的成功，有的没有成功
a2= [1, 2, 3, 4, 5, 10]
成功了
a3= [11, 23, 37, 48, 94, 152, 230, 312, 339, 413]
没有成功，为什么？
还有第三个问题
给出的代码是：
def getBestTargetSum(S, tgt):
k = len(S)
assert tgt >= 0
# your code here
return res
验证代码为：
def checkTgtSumRes(a, tgt,expected):
a = sorted(a)
res = getBestTargetSum(a, tgt)
res = sorted(res)
print('Your result:' , res)
assert tgt - sum(res) == expected, f'Your code returns result that sums up to {sum(res)}, expected was {expected}'
i = 0
j = 0
n = len(a)
m = len(res)
while (i < n and j < m):
if a[i] == res[j]:
j = j + 1
i = i + 1
assert j == m, 'Your result {res} is not a subset of {a}'
print('--test 1--')
a1 = [1, 2, 3, 4, 5, 10]
print(a1, 15)
checkTgtSumRes(a1, 15, 0)
print('--test 2--')
a2 = [1, 8, 3, 4, 5, 12]
print(a2, 26)
checkTgtSumRes(a2, 26, 0)
这个该怎么写？
记忆化递归，是有一个变量记录曾经递归过的东西，然后每次递归前先查询，有的话直接返回，没有的话再去计算。你这第二问代码绝对不是记忆化递归，因为没有查询是否存在，而是通通计算。看代码样式推测你写的动态规划，离题甚远了。
- 你可以看下这个问题的回答https://ask.csdn.net/questions/335076
- 这篇博客你也可以参考下：【差分隐私组合定理，直方图，列联表代码实现】差分隐私代码实现系列（五）
- 除此之外, 这篇博客: 梯度下降算法中的几点答疑：迭代到什么时候停止？为什么要求导？几个式子之间是什么关系？j是干什么的？中的 三、迭代到什么时候停止呢？ 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
迭代到偏导数几乎为0，小于1e-5时，说明已经进入了比较平滑的状态，类似于山谷的状态，这时候再继续迭代效果也不大了，所以这个时候可以退出循环！也可以说，走到这一步的
和上一个
- 您还可以看一下 孙玖祥老师的图解数据结构与算法课程中的 使用邻接矩阵创建图-代码实现小节, 巩固相关知识点
- 以下回答由chatgpt基于相关博客总结生成:
对于第一个问题，你成功使用了迭代法进行计算。迭代法是一种递推的方法，通过不断迭代来得到问题的解。具体来说，你将一个列表转换成了方矩阵，然后通过遍历矩阵中的元素，计算每个子矩阵的和，并找到最大的和作为结果。
对于第二个问题，有些代码成功解决了问题，有些代码却没有成功。这可能是因为在某些情况下，你的代码无法正确地计算出最大和。原因可能是代码逻辑的问题，比如你可能遗漏了某些特殊情况或者没有正确处理边界条件。另外，可能还存在一些语法错误或逻辑错误等问题。为了确定失败的代码出现问题的原因，你可以逐步调试代码，检查每一步的计算是否正确，并尝试添加一些边界条件的判断逻辑。
对于第三个问题，编写验证代码可以通过编写一些测试用例，并在运行代码后比较输出结果与预期结果是否一致来确认代码的正确性。具体来说，你可以编写一些输入示例，并手动计算出预期的输出结果。然后，运行代码并将输出结果与预期结果进行对比。如果两者一致，那么可以确认代码的正确性。如果不一致，那么可能需要检查代码逻辑，或者添加一些边界条件的判断逻辑，以确保代码的正确性。
以下是对第一个问题的代码的修改，以及对第三个问题的验证代码的示例：
# 从矩阵中寻找和最大的子矩阵 def find_the_max(ary): max_val = 0 for i in range(len(ary)-1): for j in range(len(ary[i])-1): sum_val = ary[i][j] + ary[i+1][j] + ary[i][j+1] + ary[i+1][j+1] if sum_val > max_val: max_val = sum_val return max_val n = int(input()) arr_lists = list(map(int,input().split())) matrix = ListToMatrix(arr_lists) result = find_the_max(matrix) print(result) # 验证代码 expected_result = 10 if result == expected_result: print("代码输出结果与预期结果一致！") else: print("代码输出结果与预期结果不一致，请检查代码逻辑。")你可以根据此示例对第二个问题的代码进行类似的修改，并写出相应的验证代码。
记忆化搜索，第二问并非让您将递归的形式改为递推，而是让您优化递归求解的时间复杂度。注意到搜索时可能会尽过很多重复的状态，每次重复计算浪费了大量的时间，可以加入记忆化搜索。将固定的状态集合的答案记录下来，下次直接返回答案即可。代码如下
T = {}
def targetSum(S, i, tgt):
# your code here
k = len(S)
global T
if T.__contains__((i, tgt)):
return T[(i, tgt)]
# If calculation with this input is already computed return result from mem
if tgt < 0:
return float('inf')
if i >= k and tgt >= 0:
return tgt
else:
minimum = min(targetSum(S, i+1, tgt-S[i]), targetSum(S, i+1, tgt))
# Store result of current calculation in mem if needed again later
# print(minimum)
T[(i, tgt)] = minimum
return minimum
def tgtSum(tgt, S):
global T
T.clear()
return targetSum(S, 0, tgt)
t6 = (tgtSum(457, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1
assert t6 == 1, 'Test 6 failed'
t7 = (tgtSum(15, [1, 2, 3, 4, 5, 10])) # should be 0
assert t7 == 0, 'Test 7 failed'
第三问的意思是让您输出所选T集合的方案，再记忆化的基础上把最优解给记录下来即可，详细见代码
T = {}
def targetSum(S, i, tgt):
# your code here
k = len(S)
global T
if T.__contains__((i, tgt)):
return T[(i, tgt)]
# If calculation with this input is already computed return result from mem
if tgt < 0:
return (float('inf'), [])
if i >= k and tgt >= 0:
return (tgt, [])
else:
# minimum = min(targetSum(S, i+1, tgt-S[i]), targetSum(S, i+1, tgt))
choose_i = targetSum(S, i+1, tgt-S[i])
not_choose_i = targetSum(S, i+1, tgt)
if choose_i[0] <= not_choose_i[0]: # 判断选/不选谁更优 [0] 存最小解值，[1] 存 T 集合
minimum = choose_i
minimum[1].append(S[i])
else:
minimum = not_choose_i
# Store result of current calculation in mem if needed again later
# print(minimum)
T[(i, tgt)] = minimum
return minimum
def getBestTargetSum(S, tgt):
k = len(S)
assert tgt >= 0
# your code here
T.clear()
res = targetSum(S, 0, tgt)[1]
return res # 应该返回一个列表对应最优解所选出的 T 集合
def checkTgtSumRes(a, tgt,expected):
a = sorted(a)
res = getBestTargetSum(a, tgt)
res = sorted(res)
print('Your result:' , res)
assert tgt - sum(res) == expected, f'Your code returns result that sums up to {sum(res)}, expected was {expected}'
i = 0
j = 0
n = len(a)
m = len(res)
while (i < n and j < m):
if a[i] == res[j]:
j = j + 1
i = i + 1
assert j == m, 'Your result {res} is not a subset of {a}'
print('--test 1--')
a1 = [1, 2, 3, 4, 5, 10]
print(a1, 15)
checkTgtSumRes(a1, 15, 0)
print('--test 2--')
a2 = [1, 8, 3, 4, 5, 12]
print(a2, 26)
checkTgtSumRes(a2, 26, 0)
求采纳
py 子数列的记忆迭代法问题的解法
#一般迭代法
import numpy as np
def f(x):
y=(x+1)**(1/3) #迭代函数
return y
def main():
#-----一般迭代法-----#
x0=1.5 #一般迭代法迭代初始值
e=10**(-9) #误差要求
m=0
while abs((f(x0)-x0))>e: #采用残差来判断
x1=f(x0) #迭代公式
x0=x1
m=m+1 #统计迭代次数
print(f"x0={x0}")
print(f"m={m}")
#-----Steffensen加速收敛法-----#
x0=1.5 # 迭代初始值
n=0
while abs((f(x0)-x0)) > e: # 采用残差来判断
y0=f(x0)
z0=f(y0)
x1=x0-(y0-x0)**2/(z0-2*y0+x0) #迭代公式
x0=x1
n=n+1 #统计迭代次数
print(f"x0={x0}")
print(f"n={n}")
if __name__ == '__main__':
main()
第二个代码中的问题可能出现在第三个for循环中，即for j in range(tgt,-1,-1)。在这个循环中，我们假设T[(i + 1, j)]已经计算出来，并存储在字典T中。但是，在实际执行中，我们需要在计算T[(i + 1, j)]之前先计算T[(i + 1, j - 1)]，因为后者可能被前者使用。因此，第二个代码中的问题可能是由于计算顺序不正确导致的。
尝试使用递归或动态规划等算法来实现getBestTargetSum函数，确保遍历整个整数列表并找到符合条件的子集，在验证代码checkTgtSumRes中，您可以使用assert语句来确保函数返回的子集的和与预期值相符，并检查返回的子集是否是整数列表的子集
试试通过递归来实现
采用chatgpt：
第二个问题：
在第二个问题的代码中，我们使用了一个动态规划的记忆化迭代法来解决子数列的目标和问题。该算法尝试使用数组S中的元素来构建目标和tgt，并通过填充和更新记忆化表T来实现。
然而，在处理列表a3=[11, 23, 37, 48, 94, 152, 230, 312, 339, 413]时，该算法可能无法正确计算出最优解。问题出在以下这行代码：
if T[(i + 1, j)] - S[i] < 0:
这行代码的逻辑是，如果将S[i]添加到当前目标和j会导致负数，那么将跳过该选择。然而，这个逻辑是错误的。在子数列的目标和问题中，我们可以选择跳过一些元素而不将它们添加到当前目标和中，以便最终得到一个目标和等于tgt的子数列。
为了修复这个问题，我们需要修改上述代码块中的条件判断部分。以下是修正后的代码：
if T[(i + 1, j)] < S[i]:
T[(i,j)] = T[(i + 1, j)]
else:
T[(i,j)] = max(T[(i + 1, j)], T[(i + 1, j - S[i])] + S[i])
这样修改后的代码会检查两种情况：
如果不选择将S[i]添加到当前目标和中，那么T[(i,j)]将等于T[(i + 1, j)]。
如果选择将S[i]添加到当前目标和中，那么T[(i,j)]将等于T[(i + 1, j - S[i])] + S[i]。
通过在这两种情况中选择较大的值来更新T[(i,j)]，我们可以保证算法计算得到的最优解。
修正后的代码如下所示：
def memoTargetSum(S, tgt):
k = len(S)
assert tgt >= 0
T = {} # Memo table initialized as empty dictionary
for j in range(tgt + 1):
T[(k, j)] = j
for i in range(k - 1, -1, -1):
for j in range(tgt, -1, -1):
if T[(i + 1, j)] < S[i]:
T[(i, j)] = T[(i + 1, j)]
else:
T[(i, j)] = max(T[(i + 1, j)], T[(i + 1, j - S[i])] + S[i])
return T
使用修正后的代码，应该能够正确计算包含列表a3的子数列的目标和。
第三个问题：
要修改代码以记录附加信息以便恢复解决方案，我们可以使用动态规划的方法。可以使用一个二维数组dp来记录子问题的解，并且使用另一个二维数组prev来追踪每个解的来源。
下面是修改后的getBestTargetSum函数的代码：
def getBestTargetSum(S, tgt):
k = len(S)
assert tgt >= 0
# Initialize the dp and prev arrays
dp = [[False] * (tgt + 1) for _ in range(k + 1)]
prev = [[None] * (tgt + 1) for _ in range(k + 1)]
# Base cases
for i in range(k + 1):
dp[i][0] = True
# Compute the dp array
for i in range(1, k + 1):
for j in range(1, tgt + 1):
if j < S[i - 1]:
dp[i][j] = dp[i - 1][j]
prev[i][j] = (i - 1, j)
else:
if dp[i - 1][j] or dp[i - 1][j - S[i - 1]]:
dp[i][j] = True
if dp[i - 1][j]:
prev[i][j] = (i - 1, j)
else:
prev[i][j] = (i - 1, j - S[i - 1])
# Reconstruct the solution
res = []
i = k
j = tgt
while i > 0 and j > 0:
if prev[i][j] is not None:
prev_i, prev_j = prev[i][j]
if j != prev_j:
res.append(S[i - 1])
i = prev_i
j = prev_j
else:
break
return res
这段代码使用了一个dp二维数组来记录子问题的解。dp[i][j]表示是否存在子数列的和为j的子集，使用前i个元素。prev二维数组用于追踪每个解的来源，其中prev[i][j]存储了子数列和为j的子集的前一个元素的索引。
然后，我们根据prev数组从后向前重建解决方案。在重建解决方案时，如果prev[i][j]不为None，则表示当前的元素S[i - 1]是解的一部分，并且我们将其添加到结果列表res中。然后，我们将索引更新为prev[i][j]，以追踪下一个元素。
最后，返回结果列表res。
您可以运行checkTgtSumRes函数来验证代码的正确性。它会打印您的结果和预期结果之间的差异，并在结果不符合预期时引发断言错误。