math - 30人のグループを作る

Question

3人のグループを連続して提供できるプログラムを作成して、同じ人のグループに2回参加する人がいないようにしたいと思います。したがって、2つの異なるシリーズで123と124を使用することはできません。

例：9人。それは4回形成することができます（絶対最大）：
シリーズ1：
グループ1：1 2 3
グループ2：4 5 6
グループ3：7 8 9

シリーズ2：
グループ1：1 5 9
グループ2：2 6 7
グループ3：3 4 8

シリーズ3：
グループ1 3 5 7
グループ2：1 6 8
グループ3：2 4 9

シリーズ4：
グループ1：3 6 9
グループ2：2 5 8
グループ3：1 4 7

でも、たった12人で手作業でやるのは難しいと思います。12人の4-5シリーズ（絶対最大）を形成することが可能です。

このプログラムの書き方がわかりません。ペンと紙で「試す」以外に、体系的な方法を見つけることができません。30人でやりたいです。30人で13-14シリーズを形成することができます。（絶対最大）

score 1 · Accepted Answer

わかりました、これはc ++を使用したバックトラッキングソリューションです:

#include <stdio.h>

using namespace std;

int v[100], n;
int ma[100][100];

void init(int k)
{
    v[k] = 0;
}

bool solutionReached( int k ) 
{
    if (k == n + 1)
        return true;
    return false;
}

void printSolution( int k ) 
{
    for (int i = 1; i < k; i++)
    {
        printf("%i ", v[i]);
        if (i % 3 == 0)
        {
            printf("\n");
        }
    }

    for (i = 1; i < n; i++)
    {
        if (i % 3 == 1)
        {
            for (int j = i + 1; j < i + 3; j++)
            {
                ma[v[i]][v[j]] = 1;
                ma[v[j]][v[i]] = 1;
            }
        }

        for (int j = i + 1; j % 3 == 0; j++)
        {
            ma[v[i]][v[j]] = 1;
            ma[v[j]][v[i]] = 1;
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            //printf("%d ", ma[i][j]);
        }
        //printf("\n");
    }

    printf("\n");
}

bool hasSuccesor( int k ) 
{
    if(v[k] < n)
    {
        v[k]++;
        return true;
    }
    return false;
}

bool isValid( int k ) 
{
    for (int i = 1; i < k; i++)
    {
        if (v[i] == v[k])
        {
            return false;
        }

        /*if (ma[v[i]][v[k]] == 1)
        {
            return false;
        }*/
    }

    for (i = 1; i < k; i++)
    {
        if (i % 3 == 1)
        {
            for (int j = i + 1; j < i + 3; j++)
            {
                if (ma[v[i]][v[j]] == 1)
                {
                    return false;
                }
            }
        }

        for (int j = i + 1; j % 3 == 0; j++)
        {
            if (ma[v[i]][v[j]] == 1)
            {
                return false;
            }
        }
    }

    return true;
}

void bkt(int k)
{
    if(solutionReached(k))
        printSolution(k);
    else
    {
        init(k);
        while(hasSuccesor(k))
            if(isValid(k))
                bkt(k + 1);
    }
}

int main(int argc, char* argv[])
{
    n = 9;
    bkt(1);

    return 0;
}

実験したい場合は、のようにn = 9で割り切れる任意の数に変更しますが、小さい数 (>15) でもかなりの時間がかかります (コンピューターによって異なります)。312, 15, 21

編集：「同じ人が2回グループにいる人はいない」ようにやり直しましたが、9人で4つではなく3つのグループしか見つかりませんでした。

例: - for 9 プログラムの場合:

12 プログラムの場合:

15 の場合:

18 の場合: (1 分半後 - まだあります -)

それらをファイルに保存する場合は、fstream を含め、printSolution を次のように変更します。

        void printSolution( int k ) 
    {
        ofstream cout;
        cout.open("date.txt", ios::app);

        for (int i = 1; i < k; i++)
        {
            cout << v[i] << " ";
            if (i % 3 == 0)
            {
                cout << "\n";
            }
        }

        for (i = 1; i < n; i++)
        {
            if (i % 3 == 1)
            {
                for (int j = i + 1; j < i + 3; j++)
                {
                    ma[v[i]][v[j]] = 1;
                    ma[v[j]][v[i]] = 1;
                }
            }

            for (int j = i + 1; j % 3 == 0; j++)
            {
                ma[v[i]][v[j]] = 1;
                ma[v[j]][v[i]] = 1;
            }
        }
     }

math - 30人のグループを作る

1 に答える 1

Related

Reference