Сумма чисел, сделанных в последовательности

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://en.wikipedia.org/wiki/Frobenius_number

вики-страницы должны иметь ссылки на алгоритмы ее решения, например: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

Для 2 чисел а, Ь точная формула (аб-аб) известно (которые вы можете использовать, чтобы сократить вниз по вашему поисковому пространству), а для 3 чисел a, b, ca острая нижняя граница (sqrt (3abc) -abc) и довольно быстрые алгоритмы известны.

Если числа находятся в арифметической прогрессии, то известна точная формула (см. Wiki). Я упоминаю об этом, потому что в ваших примерах все числа находятся в арифметической прогрессии.

Чтобы ответить на ваш вопрос, найдите номер Фробениуса и добавьте 1 к нему.

Надеюсь, что это поможет.