0

Есть определенное число шаров N, пусть будет 10. Есть определенное число корзин K, пусть будет 3. Тогда я использую следующий алгоритм:

N = 0; 0 шаров можно распределить по корзинам одним способом `
       0 0 0
N = 1; 1 шар можно распределить по корзинам тремя способами
       1 0 0
       0 1 0
       0 0 1
N = 2; 2 шара можно распределить по корзинам шестью способами
       2 0 0
       0 2 0
       0 0 2
       1 1 0
       1 0 1
       0 1 1
и так далее.

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

upd. Скажите, пожалуйста, можно ли автоматически составить матрицу в данном случае (10, 3) с использованием треугольника Паскаля? Здесь получается, что сумма строки равна конкретному N.

2
  • В комбинаторике есть формула распределения N элементов по K группам.
    – Get
    25 ноя 2014 в 15:51
  • Здесь вопрос не о том, сколько всего комбинаций, а какие именно.
    – Danaida
    25 ноя 2014 в 16:01

1 ответ 1

1

Не прошло и четырех лет, как я нарвался на эту задачку :)

Ну, а вдруг кому пригодится?

Здесь легко проходит рекурсивный перебор - просто первое место поочередно забиваем от 0 до N, и, соответственно, задача сводится к меньшей...

#include <vector>
#include <iostream>
#include <iomanip>

using namespace std;

void Generate(int N, int K, vector<int>& res) // N шаров, K корзин
{
    if (N == 0)
    {
        for(auto n: res) cout << n << " ";
        for(int i = 0; i < K; ++i)
        {
            cout << 0;
            if (i != K-1) cout << " ";
        }
        cout << endl;
    }
    else if (K == 0)
    {
        return;
    } else {
        for(int i = 0; i <= N; ++i)
        {
            res.push_back(i);
            Generate(N-i,K-1,res);
            res.pop_back();
        }
    }
}



int main(int argc, const char * argv[])
{
    vector<int> r;
    Generate(10,3,r);
}

https://ideone.com/NzvVWI

Ваш ответ

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

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