单跳最多回溯n个楼梯n步 [英] backtracking n staircases at most k steps in a single jump
问题描述
您需要爬上n个台阶的楼梯，然后决定通过跳下台阶进行一些额外的锻炼。一次跳转最多可以覆盖k个步骤。返回您可能要爬上楼梯的所有可能跳序列，按顺序排序。
You need to climb a staircase that has n steps, and you decide to get some extra exercise by jumping up the steps. You can cover at most k steps in a single jump. Return all the possible sequences of jumps that you could take to climb the staircase, sorted.
我的实现显然给了我错误的答案。
My implementation is obviously giving me the wrong answer.
def climbingStaircase(n, k):
final_res=[]
final_res.append(CSR(n,k,[]))
return final_res
def CSR(n,k,res):
if n == 0:
return res
else:
for i in range(1,k+1):
if n-i>=0:
res.append(i)
n=n-i
res=CSR(n,i,res)
return res
对于n = 4和k = 2，输出应为
For n = 4 and k = 2, the output should be
[[1, 1, 1, 1],
[1, 1, 2],
[1, 2, 1],
[2, 1, 1],
[2, 2]]
实际输出：
[[1,1,1,1,2,1]]
有人可以指出我缺少的那一部分吗？
Can someone point out which part I'm missing?
推荐答案
下面的代码是一个巨大的问题：您在步骤范围内为每个可能性减去了步骤数量。
One huge problem is in the code below: you deduct the quantity of steps for each possibility within the step range.
n=n-i
res=CSR(n,i,res)
完成一步跳跃操作后，您需要回溯并从相同起点尝试（此实例的原始值 n ），跳了两步。将代码更改为：
When you're done exploring what you can do with a 1-step jump, you need to backtrack and try from the same starting point (this instance's original value of n) with a 2-step jump. Change the code to:
res = CSR(n-i, i, res)
在循环中，这会保持 n 的值不变。
This keeps the n value intact as you go through the loop.
此外，您不能将将来的跳跃限制为您刚尝试的最大值。也更改第二个参数：
In addition, you can't limit future jumps to the max of what you just took. Change that second parameter, too:
res = CSR(n-i, k, res)
那应该会让您感动。也可以尝试以下可爱的 debug 博客以寻求帮助。至少插入一个或两个跟踪语句，例如
That should get you moving. Also try this lovely debug blog for help. At least insert one or two tracing statements, such as
print n, k, res
。
CAVEAT
这不是您的全部麻烦。剩下的最大问题是 CSR 仅返回一个解决方案：您采取的每个步骤都会附加到 same 列表中。您需要一种方法来将完整的解决方案收集为单独的列表。 CSR 之后， climbingStaircase 中的追加仅执行一次完全完成。
This is not all of your trouble. The largest remaining problem is that CSR returns only one solution: every step you take is appended to the same list. You need a way to gather the completed solutions as separate lists; the append in climbingStaircase is executed only once, after CSR is entirely finished.
您需要以 n == 0 识别完成的解决方案。
You need to recognize a completed solution at n==0.
调试帮助
这是程序的版本，其中固定了递归参数，并调试了跟踪
Here is a version of your program with the recursion parameters fixed, and debugging traces inserted.
indent = ""
def climbingStaircase(n, k):
final_res = []
final_res.append(CSR(n, k, []))
return final_res
def CSR(n, k, res):
global indent
indent += " "
print indent, n, k, res
if n == 0:
print "SOLUTION", res
else:
for i in range(1, k+1):
if n-i >= 0:
CSR(n-i, k, res + [i])
indent = indent[:-2]
print climbingStaircase(4, 2)
请注意使用缩进来帮助可视化您的记录入侵和回溯。这里的关键部分是，我没有将其全局更新，而是将其保留为局部变量。我现在还删除了返回值，只需转储以输出找到的解决方案即可。您可以看到它的工作原理：
Note the use of "indent" to help visualize your recursion and backtracking. The critical part here is that, instead of updating res globally, I've left it as a local variable. I've also removed the return value for now, simply dumping to output the solutions as they're found. You can see how it works:
4 2 []
3 2 [1]
2 2 [1, 1]
1 2 [1, 1, 1]
0 2 [1, 1, 1, 1]
SOLUTION [1, 1, 1, 1]
0 2 [1, 1, 2]
SOLUTION [1, 1, 2]
1 2 [1, 2]
0 2 [1, 2, 1]
SOLUTION [1, 2, 1]
2 2 [2]
1 2 [2, 1]
0 2 [2, 1, 1]
SOLUTION [2, 1, 1]
0 2 [2, 2]
SOLUTION [2, 2]
[None]
有了这些东西，我希望您能追踪您的逻辑并弄清楚如何在您选择的水平上捕获解决方案的顺序。
With this stuff in place, I'm hopeful you can trace your logic and figure out how to capture the sequence of solutions at a level of your choosing.
这篇关于单跳最多回溯n个楼梯n步的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
