Informatika gyűjtemény

Egy szinttel feljebb mb_egyiptom.c

2004050607080910

<<  6. óra  >>

<<  Egyiptomi törtek  >>

NézetNyomtat

mb_egyiptom.c (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: us-ascii
Méret: 2 KB
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
    int p;
    int q;
} tort_t;

void egyszerusit(tort_t *t)
{
    int i, a = t->p, b = t->q;

    if (a > b) {
        i = a;
        a = b;
        b = i;
    }

    i = b % a;

    while (i != 0) {
        b = a;
        a = i;
        i = b % a;
    }

    t->p /= a;
    t->q /= a;
}

int cmp(tort_t *a, tort_t *b)
{
    return a->p * b->q - a->q * b->p;
}

void kivon(tort_t *a, tort_t *b)
{
    a->p = a->p * b->q - a->q * b->p;
    a->q = a->q * b->q;

    egyszerusit(a);
}

/*
 * MOHO
 * ----
 */
void moho(tort_t *t)
{
    tort_t a = *t, b;
    int db = 0, i, r;

    for (i = 2; i <= INT_MAX; i++) {
        if (a.p == 1) {
            printf("1/%d\n", a.q);
            db++;
            break;
        }

        b.p = 1;
        b.q = i;

        r = cmp(&a, &b);
        if (r > 0) {
            printf("1/%d\n", i);
            kivon(&a, &b);
            db++;
        } else if (r == 0) {
            break;
        }
    }

    printf("DB: %d\n", db);
}

/*
 * MASIK
 * -----
 */
int van_ket_azonos(int *nevezo, int db, int *index)
{
    int i;

    for (i = 0; i < db - 1; i++)
        if (nevezo[i] == nevezo[i + 1]) {
            *index = i;
            return 1;
        }

    return 0;
}

void kivesz(int *nevezo, int db, int index)
{
    memmove(nevezo + index, nevezo + index + 1,
        (db - index - 1) * sizeof(int));
}

void csere(int *nevezo, int a, int b)
{
    int x = nevezo[a];

    nevezo[a] = nevezo[b];
    nevezo[b] = x;
}

void elore(int *nevezo, int db, int index)
{
    while (index > 0) {
        if (nevezo[index - 1] <= nevezo[index])
            break;

        csere(nevezo, index - 1, index);
        index--;
    }
}

void hatra(int *nevezo, int db, int index)
{
    while (index < db - 1) {
        if (nevezo[index] <= nevezo[index + 1])
            break;

        csere(nevezo, index, index + 1);
        index++;
    }
}

void masik(tort_t *t)
{
    int *nevezo, i, db, index, k;

    db = t->p;

    nevezo = malloc(db * sizeof(int));
    if (!nevezo) {
        fprintf(stderr, "Nem tudok memoriat foglalni\n");
        return;
    }

    for (i = 0; i < db; i++)
        nevezo[i] = t->q;

    while (van_ket_azonos(nevezo, db, &index)) {
        k = nevezo[index];

        if (k % 2 == 0) {
            kivesz(nevezo, db, index);
            nevezo[index] = k / 2;
            elore(nevezo, db, index);
            db--;
        } else {
            nevezo[index] = (k + 1) / 2;
            nevezo[index + 1] = k * (k + 1) / 2;
            elore(nevezo, db, index);
            hatra(nevezo, db, index + 1);
        }
    }

    for (i = 0; i < db; i++)
        printf("1/%d\n", nevezo[i]);

    printf("DB: %d\n", db);

    free(nevezo);
}

/*
 * GOLOMB
 * ------
 */
void golomb(tort_t *t)
{
    tort_t a = *t, b;
    int i, db = 0;

    while (1) {
        for (i = 1; i < a.q; i++)
            if (a.p * i % a.q == 1) {
                printf("1/%d\n", a.q * i);
                b.p = 1;
                b.q = a.q * i;
                kivon(&a, &b);
                db++;
                break;
            }

        if (a.p == 1) {
            printf("1/%d\n", a.q);
            db++;
            break;
        }
    }

    printf("DB: %d\n", db);
}

int main(int argc, char **argv)
{
    tort_t t;

    if (argc != 3) {
        printf("Usage: %s p q\n", argv[0]);
        return 1;
    }

    t.p = atoi(argv[1]);
    t.q = atoi(argv[2]);

    egyszerusit(&t);

    //moho(&t);
    //masik(&t);
    golomb(&t);

    return 0;
}
(Vissza)