2. Fórumok
  3. Szoftverfejlesztés
  4. C programozás

Új hozzászólás Aktív témák

  • #3012 vanek tag Jester01 #3011
    Új Válasz #3012
    Új hozzászólás
    Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra
    Privát üzenet küldése

    vanek

    tag

    válasz Jester01 #3011 üzenetére

    A lineáris algebrából jól ismert linearis diofantoszi egyenlet megoldásának a megvalósítása a feladat.
    Tekintsük a lineáris difantoszi egyenleteket a következő alakban:
    ax - by = c , ahol a, b, c eleme Z+
    Ekkor keressük azt az x, y egész számpárt, amely a legkisebb nem negatív megoldása az egyenletnek,
    amennyiben létezik megoldás. Ennek menete a következő: d = lnko(a, b), ahol a = d * av, b = d * bv
    és c = d * cv. Ha c nem osztható d-vel, akkor nincs megoldás, különben oldjuk meg az av *x0+bv * y0 = 1
    egyenletet az egész számok halmazán az euklideszi algotritmussal (az lnko-t is ezzel tudjuk kiszámolni).
    Pl.: 1027 * x0 + 712 * y0 = 1 esetén

    1027 = 712 * 1 + 315
    712 = 315 * 2 + 82
    315 = 82 * 3 + 69
    82 = 69 * 1 + 13
    69 = 13 * 5 + 4
    13 = 4 * 3 + 1

    0 + 1 * 3 = 3;
    1 + 3 * 5 = 16;
    3 + 16 * 1 = 19;
    16 + 19 * 3 = 73;
    19 + 73 * 2 = 165;
    73 + 165 * 1 = 238;

    A második részt az első részben kapott számok segítségével számolva végül megkapjuk a két számot: 165
    és 238. Ez után ki kell próbálni, hogy mi lehet a két szám előjele (4 variáció). Majd ha az előző megoldás
    volt av * x+bv * y = 1 -re, akkor av * x0 - bv * (-y0) = 1 lesz, ami nekünk kell. Végül az eredeti egyenlet
    megoldását kapjuk, ha vissza szorzunk cv * d-vel:

    av * x0 - bv * (-y0) = 1
    av * x0 * cv - bv * (-y0) * cv = cv
    d * av * x0 * cv - d * bv * -y0 * cv = a * (x0 * cv) - b * (-y0 * cv) = c = d * cv

    Tehát x = x0 * cv és y = -y0 * cv megoldás, de nem feltétlenül a két legkisebb nemnegatív, tehát ezt még
    meg kell keresni: x- = k * bv és y- = k * av mind megoldások bármely k eleme Z-re. Keresd meg a megfelelő
    k-t és kész vagy.

    Bemenet: be.txt a, b, c
    Kimenet: ki.txt x, y

    Pl:
    Be: 53,8,64
    Ki: 8,45

    Be: 516,390,564
    Ki: 54,70

Új hozzászólás Aktív témák