Informatika gyűjtemény

Egy szinttel feljebb vektorok.cpp

2004050607080910

<<  5. óra - Kombináció  >>

<<  Vektorok  >>

NézetNyomtat

vektorok.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: 2 KB
/*
    Kombinációk egy vektorproblémához.
    A programot Uray M. János készítette 2008. október 14-én.
*/
#include <stdio.h>

#define IFile "new08i.txt"
#define OFile "new08o.txt"

#define MaxN 100
#define MaxK 6

int N, K;
// Kombinációs indexek
int A[MaxK + 1];
// Vektorok koordinátái
int V[MaxN][2];

int Load (void);
void Init (void);
int Step (void);
void Search (int);

inline int sqr (int A) {return A*A;}

int main (void) {
    printf("<-- Start -->\n");
    if (!Load())
        return 1;
    Init();
    do
        Search(0);
    while (Step());
    Search(1);
    return 0;
}

// Beolvasás a forrásállományból
int Load (void) {
    FILE * IN;

    IN = fopen(IFile, "rt");
    if (IN == NULL)
        return 0;
    fscanf(IN, "%d %d", &N, &K);
    for (int I = 0; I < N; I++)
        fscanf(IN, "%d %d", &V[I][0], &V[I][1]);
    fclose(IN);
    return 1;
}

// Kezdőértékek beállítása a kombinációkereséshez
void Init (void) {
    for (int I = 0; I < K; I++)
        A[I] = I;
    A[I] = N + 1;
}
// Egy kombinációs lépés
int Step (void) {
    int I;

    for (I = 0; I < K; I++)
        if (A[I + 1] > A[I] + 1) {
            A[I]++;
            if (A[I] == N)
                return 0;
            break;
        } else
            A[I] = I;
    return 1;
}
// Bejárás vagy kimeneti állomány elkészítése
void Search (int bSave) {
    // Legutóbbi megfelelő kombináció
    static int B[MaxK];
    // A legutóbbi megfelelő kombináció átmérője
    static long Min;
    // Volt-e már megfelelő kombináció
    static int bFound = 0;
    int SumV[2] = {0, 0}, I, J, Sign;
    long Max, D;

    if (bSave) {
        FILE * OUT = fopen(OFile, "wt");
        if (OUT == NULL)
            return;
        if (!bFound)
            fprintf(OUT, "NINCS MEGOLDÁS");
        else {
            for (int I = 0; I < K; I++) {
                if (I > 0)
                    fprintf(OUT, "+");
                fprintf(OUT, "(%d;%d)", V[B[I]][0], V[B[I]][1]);
            }
        }
        fclose(OUT);
        return;
    }

    // Ha a vektorok összege nullvektor, akkor zárt alakzatot alkotnak.
    for (I = 0; I < K; I++) {
        SumV[0]+= V[A[I]][0];
        SumV[1]+= V[A[I]][1];
    }
    if (SumV[0] || SumV[1])
        return;
    // Átmérő számolása maximumkiválasztással
    Max = 0;
    for (I = 0; I < K; I++)
        for (J = I + 1; J < K; J++) {
            D = sqr(V[A[I]][0] - V[A[J]][0]) + sqr(V[A[I]][1] - V[A[J]][1]);
            if (D > Max)
                Max = D;
        }
    // Átmérő összehasonlítása az előzővel (ha volt)
    if (!bFound || Max < Min)
        Min = Max;
    for (I = 0; I < K; I++)
        B[I] = A[I];
    bFound = 1;
}
(Vissza)