计算足球比赛中所有可能的得分方式(递归) [英] 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 to scores 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 to pop 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 the score_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屋！