При наблюдении регби вчера вечером я задавался вопросом, были ли какие-либо очки невозможны, учитывая Вас, может только доказать свое превосходство в большом количестве из 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 (самый маленький возможный счет). Кажется довольно непрактичным и медленным для чего-либо вне тривиального случая.
Есть только одно недостижимое число, выше которого достижимы все оценки.
Это называется числом Фробениуса. См .: 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) и довольно быстрые алгоритмы известны.
Если числа находятся в арифметической прогрессии, то точная формула известна (см. Вики). Я упоминаю об этом, потому что в ваших примерах все числа находятся в арифметической прогрессии.
Итак, чтобы ответить на ваш вопрос, найдите число Фробениуса и прибавьте к нему 1.
Надеюсь, что это поможет.