Új hozzászólás Aktív témák
-
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én1027 = 712 * 1 + 315
712 = 315 * 2 + 82
315 = 82 * 3 + 69
82 = 69 * 1 + 13
69 = 13 * 5 + 4
13 = 4 * 3 + 10 + 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 * cvTehá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, yPl:
Be: 53,8,64
Ki: 8,45Be: 516,390,564
Ki: 54,70
Új hozzászólás Aktív témák
● olvasd el a téma összefoglalót!
● ha kódot szúrsz be, használd a PROGRAMKÓD formázási funkciót!