9

昨晚看橄榄球比赛时，我想知道是否有任何分数是不可能的，因为您只能在 3、5 或 7 的批次中得分。很快就发现任何大于 4 的数字都是可以达到的。5=5、6=3+3、7=7、8=3+5、9=3+3+3、10=5+5等等。

将这个想法扩展到 5、7 和 9 会产生以下可能的分数： 

5,7,9,10,12,14 // and now all numbers are possible.

对于 7、9 和 11： 

7,9,11,14,16,18,20,22,23,25,27 // all possible from here

我在脑海中做了这些，任何人都可以提出一个好的算法来确定可能的最低分数，在给定一组分数的情况下，所有分数都可以达到。

我是这样建模的： 

forall a < 10:
   forall b < 10:
      forall c < 10:
          list.add(3a + 5b + 7c);
list.sort_smallest_first();

然后检查列表中是否有超过 3 的序列（可能的最小分数）。对于琐碎案例之外的任何事情，似乎都非常不切实际和缓慢。

4

1 回答 1

8

只有一个无法达到的数字，高于它所有的分数都是可以达到的。

这称为 frobenius 数。见：http ://en.wikipedia.org/wiki/Frobenius_number

wiki 页面应该有算法的链接来解决它，例如： http: //www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

对于 2 个数字 a,b，一个精确的公式 (ab-ab) 是已知的（您可以使用它来减少搜索空间），对于 3 个数字 a,b,ca，下限 (sqrt(3abc)-abc) 和相当快的算法是已知的。

如果数字是算术级数，则已知一个精确的公式（参见 wiki）。我之所以提到这一点，是因为在您的示例中，所有数字都是算术级数。

因此，要回答您的问题，请找到 Frobenius 数并将其加 1。

希望有帮助。

于 2010-08-12T04:53:40.533 回答