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

• Jester01 veterán

  #3014

  #3012 vanek

  2011-12-12 18:44:47

  Új Válasz

  Ú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

  

  Jester01

  veterán

  #3012 vanek

  #3012 vanek

  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

  A bemásolt kiírásban a számokat a bemenetben és a kimenetben egyaránt vessző választja el, a programod viszont szóközt (whitespace) használ. Feltehetőleg a bíró is ezért nem fogadja el.

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