-1

给定篮球比赛的最终得分，我如何计算导致最终得分的可能得分序列的数量。

每个得分可以是以下之一：3 分、2 分、1 分，由客队或主队得分。例如：

basketball(3,0)=4

因为这些是 4 种可能的评分序列：

V3
V2, V1
V1, V2
V1, V1, V1

并且：篮球（88,90）=2207953060635688897371828702457752716253346841271355073695508308144982465636968075

此外，我需要以递归方式并且没有任何全局变量（允许使用字典，并且可能是解决此问题的方法）此外，该函数只能将结果作为参数（篮球（m，n））。

对于那些要求解决方案的人：

basketballDic={}
def basketball(n,m):
    count=0;
    if n==0 and m==0:
        return 1;
    if (n,m) in basketballDic:
        return basketballDic[(n,m)]
    if n>=3:
        count+= basketball(n-3,m)
    if n>=2:
        count+= basketball(n-2,m)
    if n>=1:
        count+= basketball(n-1,m)
    if m>=3:
        count+= basketball(n,m-3)
    if m>=2:
        count+= basketball(n,m-2)
    if m>=1:
        count+= basketball(n,m-1)
    basketballDic[(n,m)]=count;
    return count;
4

3 回答 3

2

当您考虑递归算法时，您需要弄清楚两件事。

  1. 什么是基本情况，递归在哪里结束。
  2. 什么是递归情况。也就是说，如何从一个或多个先前的值计算一个值？

对于您的篮球问题，基本情况非​​常简单。当没有得分时，恰好有一组可能的篮子碰巧到达那里（它是空集）。所以basketball(0,0)需要返回1。

递归的情况考虑起来有点棘手。您需要逐步减少给定的分数，例如 (M,N)，直到达到 (0,0)，然后计算获得每个分数的不同方法。有六种可能的方式可以使得分从以前的任何值变为 (M,N)（每支球队的 1、2 和 3 分篮子），因此达到 (M,N) 的方式的数量是到达 (M-1,N), (M-2,N), (M-3,N), (M,N-1), (M,N-2) 和 ( M,N-3)。所以这些是您想要进行的递归调用（可能在进行一些边界检查之后）。

你会发现一个朴素的递归实现需要很长时间才能解决高分。这是因为它一遍又一遍地计算相同的值（例如，它可能计算出只有一种方法可以达到 (1,0) 数百次不同的分数）。记忆可以通过记住以前计算的结果来帮助防止重复工作。还值得注意的是，问题是对称的（获得 (M,N) 分数的方法与获得 (N,M) 分数的方法数量相同），因此您可以通过记住不仅目前的结果，也是它的逆转。

于 2012-12-05T00:01:33.177 回答
1

有两种方法可以做到这一点，而且都无法与您指定的输出相匹配。不太相关的方法是计算最大可能的得分次数。由于篮球有 1 分，这将始终等于我们basketball()函数的两个输入的总和。第二种技术是计算得分的最小次数。这可以通过递归轻松完成，如下所示：

def team(x):
    if x:
        score = 3

        if x < 3:
            score = 2
        if x < 2:
            score = 1

        return 1 + team(x - score)
    else:
        return 0

def basketball(x, y):
    return team(x) + team(y)

这可以做得更简洁甚至更优雅吗？当然，但这应该为您正在研究的那种无状态的递归解决方案提供一个不错的起点。

于 2012-12-04T21:45:50.160 回答
0

尝试使用递归从给定的结果（每一个可能的播放 - 1,2,3 点）中减少，直到我达到 0，但为此我需要全局变量，我不能使用一个。

也许这就是你揭示你需要什么的地方。您可以通过传递当前计数和/或根据需要返回使用的计数（或剩余计数）来避免全局。

在您的情况下，我认为您只需将点传递给递归函数并让它返回计数。返回值将被添加，因此最终总数将随着递归展开而汇总。

编辑

我写了一个能够产生正确结果的函数。这个问题被标记为“memoization”，使用它可以极大地提升性能。没有它，相同的子序列将被一次又一次地处理。我使用装饰器来实现记忆。

我喜欢@Maxwell 对团队的单独处理，但这种方法不会产生您正在寻找的数字。（可能是因为您的原始措辞根本不清楚，所以我已经重写了您的问题描述）。我最终在一个函数中处理了 6 个家庭和访客评分的可能性。

我的计数是错误的，直到我意识到我需要计算的是我达到最终状态的次数。

解决方案

其他解决方案已发布。这是我的（不是很可读）单行：

def bball(vscore, hscore):
    return 1 if vscore == 0 and hscore == 0 else \
        sum([bball(vscore-s, hscore) for s in range(1,4) if s <= vscore]) + \
        sum([bball(vscore, hscore-s) for s in range(1,4) if s <= hscore])

实际上我在函数定义之前也有这一行：

@memoize

我使用了 Michele Simionato 的装饰器模块和 memoize 示例。尽管正如@Blckknght 提到的那样，该函数是可交换的，因此您可以自定义 memoize 以利用这一点。

虽然我喜欢通用记忆提供的关注点分离，但我也很想用（类似的东西）初始化缓存：

cache = {(0, 0): 1}

并删除函数中对 0,0 args 的特殊情况检查。

于 2012-12-04T21:33:20.500 回答