Ú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!
- Amazon Kindle
- Kamionok, fuvarozás, logisztika topik
- Amlogic S905, S912 processzoros készülékek
- Nyíregyháza és környéke adok-veszek-beszélgetek
- A régi node-okra koncentrál a szankciók miatt Kína
- Magga: PLEX: multimédia az egész lakásban
- Azonnali VGA-s kérdések órája
- Windows 11
- Székesfehérvár és környéke adok-veszek-beszélgetek
- Facebook és Messenger
- További aktív témák...
- LG NanoCell 55NANO766QA Halvány píxel csík
- Philips 58PUS8545/12 1 ÉV GARANCIA Játék üzemmód
- Tyű-ha! HP EliteBook 850 G7 Fémházas Szuper Strapabíró Laptop 15,6" -65% i7-10610U 32/512 FHD HUN
- Bomba ár! HP EliteBook 840 G5 - i5-8G I 8GB I 128GB SSD I 14" FHD I HDMI I Cam I W10 I Gari!
- The Last of Us Part I Ps5