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

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

9 голосов
/ 12 августа 2010

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

1 Ответ

8 голосов
/ 12 августа 2010

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

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

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

...