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

При наблюдении регби вчера вечером я задавался вопросом, были ли какие-либо очки невозможны, учитывая Вас, может только доказать свое превосходство в большом количестве из 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 (самый маленький возможный счет). Кажется довольно непрактичным и медленным для чего-либо вне тривиального случая.

9
задан Azhar 12 August 2010 в 05:30
поделиться

1 ответ

Есть только одно недостижимое число, выше которого достижимы все оценки.

Это называется числом Фробениуса. См .: 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.

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

8
ответ дан 4 December 2019 в 22:26
поделиться
Другие вопросы по тегам:

Похожие вопросы: