计算足球比赛中所有可能的得分方式(递归) [英] Calculating all possible ways to score in a football game (recursively)
问题描述
假设有一个简化的足球计分系统,您可以在其中获得 {2, 3, 7} 分,那么在给定分数的情况下,您可以得分的所有可能方式是什么?
Assuming a simplified football scoring system where you can score {2, 3, 7} points, what are all the possible ways that you can score given a number of points?
我只是在解决 EPI 书中的问题,他使用 DP 解决了这个问题.我想练习一种递归技术,但我在尝试将所有不同的方法保存到结果列表中时被绊倒了.
I'm just working problems in the EPI book, and he solves this problem using DP. I wanted to practice a recursive technique, but I'm getting tripped up trying to save all the different ways in to a results list.
def find_scoring(points, scores):
ways_to_score = [2, 3, 7]
def score_finder(p, scores):
print(scores, p)
if p == 0:
print('here')
results.append(scores)
return True
elif p <= 1:
return False
for i in ways_to_score:
scores.append(i)
if not score_finder(p-i, scores):
scores.pop()
return False
results = []
score_finder(points, scores)
return results
print(find_scoring(12, []))
对于上述内容,我希望看到 [[2,2,2,2,2,2], [2,2,2,3,3], ....]
For the above, I would expect to see [[2,2,2,2,2,2], [2,2,2,3,3], ....]
我不知道如何正确传递分数变量.感谢帮助!
I cannot figure out how to pass the scores variable properly. Appreciate the assist!
推荐答案
results.append(scores)
仅在我们需要副本时添加对scores
的引用.我们可以用切片来做到这一点:scores[:]
.- 不需要
如果不是score_finder(p-i,scores):
;我们希望pop
无论我们是否在子节点中生成了成功的结果. - 将临时
scores
列表传递给score_finder
函数对调用者来说有点负担. - 相比之下,最好将
ways_to_score
参数化,以便调用者可以指定它,但使用默认参数,因此他们不必这样做. results.append(scores)
only adds a reference toscores
when we need a copy. We can do this with a slice:scores[:]
.- There is no need for
if not score_finder(p-i, scores):
; we want topop
regardless of whether we had a successful result generated in a child node or not. - It's a bit of a burden on the caller to pass the temporary
scores
list into thescore_finder
function. - In contrast, it's nice to parameterize the
ways_to_score
so that the caller can specify it, but use a default argument so they don't have to.
这是一个可能的重写,它解决了这些问题并稍微清理了逻辑:
Here's a possible rewrite which addresses these issues and cleans up the logic a bit:
def find_scoring(points, ways_to_score=[2, 3, 7]):
def score_finder(points, scores, result):
if points == 0:
result.append(scores[:])
elif points > 0:
for val in ways_to_score:
scores.append(val)
score_finder(points - val, scores, result)
scores.pop()
return result
return score_finder(points, [], [])
我们也可以返回一个生成器:
We can also return a generator:
def find_scoring(points, ways_to_score=[2, 3, 7]):
def score_finder(points, scores, result):
if points == 0:
yield scores[:]
elif points > 0:
for val in ways_to_score:
scores.append(val)
yield from score_finder(points - val, scores, result)
scores.pop()
yield from score_finder(points, [], [])
if __name__ == "__main__":
print(list(find_scoring(12)))
这篇关于计算足球比赛中所有可能的得分方式(递归)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!