Az I. 124. feladat (2006. február)

I. 124. Írjunk programot az ax+by=c alakú diophantoszi egyenletek megoldására. A program a standard bemeneten kapja a legfeljebb 4-jegyű a, b, c, egész számokat egy sorban, szóközzel elválasztva. A program írja ki az egész megoldásokat paraméteres alakban, szintén egy sorban, a példákban látható formátumban. Ha nincs megoldás, akkor írja ki azt, hogy ,,nincs megoldás''.

Példák:

Beküldendő a program forráskódja (i124.pas, i124.cpp, ...).

(10 pont)

A beküldési határidő 2006. március 16-án LEJÁRT.

A feladat megoldásához először nézzük végig a speciális eseteket, majd az általános esetet.

1. eset: 0*x+0*y=0

Ha a és b is 0, akkor az egyenletnek csak akkor van megoldása, ha c is 0. Ebben az egyetlen esetben van szükségünk két változóra a megoldáshoz:

x=t;   y=u

2. eset: 0*x+b*y=c

Ha a vagy b 0, akkor az egyenlet csak akkor oldható meg, ha a nem-nulla szorzótényező osztója c-nek, lenkező esetben az egyenlet bal oldala osztható lenne b-vel, a jobb oldala viszont nem. Ebben az esetben a megoldás:

x=t;   y=c/b

3. eset: a*x+b*y=c

Ha sem a, sem b nem 0, a megoldás a kétváltozós, lineáris diophantoszi egyenlet általános megoldása:

x=x₀+b/lnko(a,b)*t;   y=y₀;   a/lnko(a,b)*t

ahol x₀ és y₀ az egyenlet egy megoldása. Megoldás csak akkor létezik, ha c osztható lnko(a,b)-vel. (lnko(a,b) = a és b legnagyobb közös osztója )

x₀ és y₀ meghatározására létenek különböző algoritmusok, de mivel az együtthatók viszonylag kicsi számok, a legegyszerübb, ha sorban végignézzük 0-tól az egész számokat, míg találunk egy megfelelőt: c-a*x₀ -nak oszthatónak kell lennie b-vel. Bizotsan találunk egy ilyet, a [0;b/lnko(a,b)] halmazban.

A megoldáshoz szükségünk van az lnko(a,b) meghatározására, ezt az euklideszi algoritmussal könnyen megtehetjük: vegyük a nagyobbik szám helyett a nagyobbik szám kisebbik számmal való osztási maradékát, és ezt ismételjük addig, amíg valamelyik szám 0 nem lesz.

(x₀ és y₀ meghatározására lehetséges lenne például úgy, hogy az egyenletet átalakítjuk: (tegyük föl, hogy a<b, és jelölje b%a a b a-val való osztási maradékát, b/a pedig b és a hányadosának egészrészét)

c=b*y+a*x=(b/a*a+b%a)*y+a*x=a*(b/a*y+x)+b%a*y=a*z+b%a*y=...

ez az átalakítás az euklideszi algoritmus szerint megy, minden lépésben egy új ismeretlent bevezetve. Az átalakítások végén:

c=lnko(a,b)*x_n+0*x_n-1

egyenletet kapjuk, innen x_n értéke meghatározható. x_n-1 értékét pedig szabadon megválaszthatjuk. Ebből az egyenletből az is látszik, hogy miért kell c-nek oszthatónak lennie lnko(a,b)-vel. x_n és x_n-1-ből visszaszámolható x és y, ami a diophantoszi egyenlet egy megoldása lesz.)

Letölthető megoldás: i124.pas

Engedy István

Statisztika:

10 dolgozat érkezett.
10 pontot kapott:	Balambér Dávid, Czigler András, Györök Péter, Kovács 129 Péter, Ozsvárt László, Szoldatics András, Véges Márton, Vincze János.
3 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2006. februári informatika feladatai