获取获得一定分数N所需的（美国）足球积分累积的所有组合的算法 [英] Algorithm to get all combinations of (American) football point-accumulations necessary to get a certain score N

问题描述

这是我的面试问题之一，我想不出获得N号的好方法。（此外，我也不了解美式足球计分系统）

It was one of my interview question, and I could not think of the good way to get number N. (plus, I did not understand the American football scoring system as well)

6 points for the touchdown
1 point for the extra point (kicked)
2 points for a safety or a conversion (extra try after a touchdown)
3 points for a field goal

获得 >所有要获得一定分数N所必需的点累加组合？

What would be an efficient algorithm to get all combinations of point-accumulations necessary to get a certain score N?

推荐答案

假设您在这里寻找

首先让我们找到一个递归函数：

f（n）=（f（n-6）> = 0？f（n-6）：0）+（f（n-1）> = 0≤f（n-1）：0）+（f（n-2）＞ ＝0≤f（n-2）：0）+（f（n-3）＞ ＝0≤f（n- 3）：0）

基数： f（0）= 1 和 f（n）=-无穷大[ n< 0]

其背后的想法是：您始终可以达到 0 ，通过没有得分的游戏。如果您可以获取 f（n-6），还可以获取 f（n），依此类推在每种可能性上。

The idea behind it is: You can always get to 0, by a no scoring game. If you can get to f(n-6), you can also get to f(n), and so on for each possibility.

使用上述公式可以轻松创建递归解决方案。

Using the above formula one can easily create a recursive solution.

请注意，您甚至可以使用 动态编程 ，用[-5，n]初始化表，初始化 f [0] = 0 并 f [-1] = f [-2] = f [-3] = f [-4] = f [-5] =-无穷大并遍历索引 [1，n] 以根据上面的递归公式获得可能性的数量。

Note that you can even use dynamic programming with it, initialize a table with [-5,n], init f[0] = 0 and f[-1] = f[-2] = f[-3] = f[-4] = f[-5] = -infinity and iterate over indexes [1,n] to achieve the number of possibilities based on the the recursive formula above.

编辑：

我刚刚意识到上述公式的简化版本可能是：

f（n）= f（n-6） + f（n-1）+ f（n-2）+ f（n-3）

，基数为： f（0） = 1 ， f（n）= 0 [n< 0]

两个公式将得出完全相同的结果

I just realized that a simplified version of the above formula could be:
f(n) = f(n-6) + f(n-1) + f(n-2) + f(n-3)
and base will be: f(0) = 1, f(n) = 0 [n<0]
The two formulas will yield exactly the same result.

这篇关于获取获得一定分数N所需的（美国）足球积分累积的所有组合的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！