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 that you have read and understand our privacy policy and code of conduct.

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