Informatika gyűjtemény

Egy szinttel feljebb bolgar.cpp

2004050607080910

<<  6. óra - Partíció  >>

<<  Bolgár szoliter  >>

NézetNyomtat

bolgar.cpp (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 1 KB
#include <stdio.h>

/*
    Partíciók előállításának alkalmazása a Bolgár solitaire-problémára.
    A programot Uray M. János készítette 2008. október 21-én.
*/

#define MaxN 100

// A: a partíciót tartalmazó tömb
// B: a tömb másolata a Bolgár solitaire részére
int A[MaxN], B[MaxN];
// Akkor igaz, ha már tudjuk, mennyi partíció létezik.
// (Először lefut a MakePartitions() függvény bDone = 0-val, majd 1-gyel.)
int bDone = 0;
// a partíciók száma
long P;

void MakePartitions (int);
int Find (int);

int main (void) {
    printf("<-- Start -->\n");
    MakePartitions(45);
    MakePartitions(45);
    return 0;
}

void MakePartitions (int N) {
    // N: a partícionálandó szám
    // M: a partíció hossza
    // Q: Az első egyes előtti utolsó index (0-tól)
    // D: A maradékos osztás osztója
    int I, M = 1, Q = 0, D;

    if (N > MaxN || N < 2)
        return;

    A[0] = N;
    if (bDone)
        Find(M);
    else
        P = 1;
    while (Q >= 0) {
        D = A[Q] - 1;
        for (N = M - Q + D; N > D; N-= D, Q++)
            A[Q] = D;
        A[Q] = N;
        M = Q + 1;
        for (; Q >= 0 && A[Q] == 1; Q--);
        if (bDone)
            Find(M);
        else
            P++;
    }
    bDone = 1;
}
int Find (int M) {
    long R = 0;
    // BM: a B[] hossza
    int I, J, T, BM = M;
    int bFound = 0;

    for (I = 0; I < BM; I++)
        B[I] = A[I];
    do {
        // bolgár solitaire egy lépése
        // egy levonása, nullák kihagyása
        for (J = I = 0; I < BM; I++)
            if (B[I] > 1)
                B[J++] = B[I] - 1;
        BM = J + 1;
        // a kivett elemek számát elhelyezni a csökkenő sorban
        for (J--; J >= 0; J--)
            if (B[J] < I) {
                B[J + 1] = B[J];
                B[J] = I;
            }
        // egyezés vizsgálata az eredetivel
        bFound = 0;
        if (BM == M) {
            bFound = 1;
            for (I = 0; I < M; I++)
                if (A[I] != B[I])
                    bFound = 0;
        }
        R++;
    } while (R < P && !bFound);
    if (bFound) {
        for (I = 0; I < M; I++)
            printf("%d ", A[I]);
        printf("\n");
    }
    return bFound;
}
(Vissza)