-1

Не могу придумать алгоритм. Исходная задача такая. Переменные:

  1. Количество позиций (в моем случае это будет число от 2-х до 6-ти).
  2. Сумма всех стеков (фишек).
  3. Шаг изменения стека (фишек).
  4. С учетом/без учета порядка.

После того как я задам переменные, программа должна будет составлять большую таблицу, в которой будут все ситуации распределения фишек. Вот пример:

6 человек; в сумме на всех 3000 фишек; шаг 10 фишек. Без учета порядка. Программа начинает с 10/10/10/10/10/2950 (пусть будет так, что размер стека не может быть меньше шага), затем идет, например, 20/10/10/10/10/2940, и далее начинает перебирать всевозможные сочетания размеров стека (НО обязательно дающие в сумме одну и ту же цифру, которую мы зададим в качестве суммы стеков). В общем, каждый стек будет кратным шагу, и при перемене стеков местами не должно быть совпадений.

Т.е. в этом случае, например, 10/20/30/40/50/2850 и 30/40/2850/50/10/20 будут одинаковыми ситуациями, и в нашу таблицу внесется лишь одна из них (думаю, не столь важно, какая именно). В случае если я нажму галочку "с учетом порядка", то в таком это уже будут разные ситуации и обе будут внесены в нашу таблицу. Стек уже будет привязываться к номеру позиции.
У меня тяжеловато с комбинаторикой, так что я вряд ли смогу определить примерное количество подобных сочетаний.

Код

9
  • Обновил вопрос. 12 ноя 2014 в 12:44
  • @yarkov_aleksei, не вижу, что обновилось. Чем текущий ответ не устраивает?
    – dzhioev
    13 ноя 2014 в 16:06
  • Из ответа не понял ничего просто. ))) Не силен в математике я, к сожалению. 13 ноя 2014 в 17:56
  • @yarkov_aleksei тогда вопрос, а с чем вы бились два часа, если предметная область для вас - темный лес? Начните с малого.
    – smackmychi
    13 ноя 2014 в 18:16
  • 1
    @yarkov_aleksei, по первой ссылке 250 строк кода, который делает непонятно что и непонятно каким способом. Никто в нем разбираться не будет. Вы хотя бы напишите какой алгоритм пытаетесь написать, на каких входных данных проверяете, какой вывод, чем вывод не устраивает. По второй ссылке опять нет никакой конкретики, только комментарий в духе "Ничего не получается" и ссылка на код.
    – dzhioev
    13 ноя 2014 в 21:08

1 ответ 1

2

В случае, когда порядок важен, число вариантов будет равно числу композиций числа (Количество позиций / Шаг изменения стека), состоящих из (Количество позиций) слагаемых. Как их перечислять, можно прочитать тут. Предупреждаю, что число композиций растет очень быстро. Оно равно числу сочетаний из (n-1) по (k-1). Для вашего примера это будет (299 choose 5) = 19256456934 ~ 10^10, что уже на грани возможностей обычных компьютеров. Можно грубо оценить: чтобы сохранить каждую комбинацию, нужно 5 * 9 бит, поэтому чтобы сохранить их все, нужно порядка 100 Гб. Ну и времени на вычисления понадобится порядка суток.

Для случая, когда порядок не важен, число вариантов будет равно числу разбиений фиксированной длины. Про алгоритм перечисления можно прочитать тут. Число разбиений будет меньше, но я подозреваю, что зависимость тоже экспоненциальная. Точной формулы вроде бы нет.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.