作出序列的數字總和

昨天晚上看橄欖球時，我想知道是否有任何得分是不可能的，因爲你只能以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（最小的分數可能）長。看起來很不切實際，而且對於任何超出平凡情況的東西都很慢。

來源

2010-08-12 Daniel

+1看橄欖球，如果我可以給你另一個如果你是十字軍迷。好問題 - 在他們增加點數之前，不可能得分19. – slugster 2010-08-12 04:54:47

坎特伯雷一路！ – Daniel 2010-08-12 07:46:20

只有一個難以達到的數字，高於所有數值都可以達到。

這被稱爲frobenius號碼。請參閱：http://en.wikipedia.org/wiki/Frobenius_number

維基頁面應該有鏈接的算法來解決這個問題，比如：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-12 04:53:40

+1，維基百科文章也以橄欖球爲例。 – Seth 2010-08-12 05:05:55

非常感謝。非常讓人印象深刻的是，該wiki文章使用了這個確切的例子 – Daniel 2010-08-12 07:46:04

有關於這件事的代碼高爾夫問題。 http://stackoverflow.com/questions/3465392/code-golf-frobenius-number。這是非常奇怪的，因爲這個頁面是我同時打開的唯一頁面，他們都提到了我從未聽說過的東西。真是巧合。 – bennybdbc 2010-08-12 09:04:18

作出序列的數字總和

回答

相關問題