制作序列的数字之和

Question

在昨晚观看橄榄球的时候,我想知道是否有任何分数是不可能的,因为你只能得到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的序列(可能的最小分数).对于除了琐碎案件之外的任何事情,似乎都是不切实际和缓慢的.

Answer 1

只有一个无法达到的数字,所有分数都可以达到.

维基页面应该包含用于解决它的算法的链接,例如:http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

对于2个数字a,b,已知精确的公式(ab-ab)(可用于减少搜索空间),对于3个数字a,b,ca sharp lower bound(sqrt(3abc)-abc)和已知很快的算法.

如果数字是算术级数,那么确切的公式是已知的(参见wiki).我提到这一点是因为在你的例子中,所有数字都在算术级数.

所以要回答你的问题,找到Frobenius数字并加1.

希望有所帮助.