KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

I. 124. Write a program to solve Diophantine equations of the form ax+by=c. The program receives the integers a, b and c having at most four digits in one line from the standard input, separated by spaces. Your program should display the integer solutions in a parametric form in one line as shown below. If there is no solution, print the text ,,no solution''.

Examples:

The source code (i124.pas, i124.cpp, ...) is to be submitted.

(10 points)

Deadline expired on 16 March 2006.


Google Translation (Sorry, the solution is published in Hungarian only.)

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=x0+b/lnko(a,b)*t;   y=y0;   a/lnko(a,b)*t

ahol x0 és y0 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 )

x0 és y0 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*x0 -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.

(x0 és y0 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)*xn+0*xn-1

egyenletet kapjuk, innen xn értéke meghatározható. xn-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. xn és xn-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


Statistics on problem I. 124.
10 students sent a solution.
10 points: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 points:1 student.
0 point:1 student.


  • Problems in Information Technology of KöMaL, February 2006

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley