Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem I. 123. (January 2006)

I. 123. Create an OpenOffice or Excel sheet implementing the Euclidean algorithm to calculate the greatest common divisor of two positive integers with at most 6 digits.

The user enters the two integers into the first two cells of the first row. Every row then contains two numbers: the smaller number of the previous row and the remainder upon dividing the greater one by the smaller. These steps are repeated until a 0 appears among the numbers: the other number in that row is the greatest common divisor of the original numbers. This should be copied into the third cell of the first row.

See the example.

12 21 3
12 9
9 3
3 0

The sheet (i123.sxc, i123.xls) should be submitted.

(10 pont)

Deadline expired on February 15, 2006.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás. A feladat megoldásában három lényegében különböző típusú cellát kell kitöltenünk: az első oszlop celláit, a második oszlop celláit, illetve a harmadik oszlop első celláját, ahova az eredményt várjuk.

Az első oszlopba mindig az előző sorban szereplő két érték közül szeretnénk a kisebbet írni. Ez a második sort leszámítva mindig a B oszlopban lesz, hiszen oda a maradékokat írjuk, ami nyílván kisebb mint az A oszlopban lévő osztó. (Az első sor az input, ahol nincs kikötve hogy az első érték a nagyobb)

Így az első oszlop második sorába a következő képletet írjuk:

=MIN(A1;B1)

A további sorokba pedig: =HA(B2>0;B2;"") értelemszerűen a sor száma növekszik. A fenti képlettel azt is kiküszöböltük, hogy a végén ne lássunk 0-ákat.

A második oszlopba a nagyobbik maradéka kerül a kisebbikkel osztva. Itt is külön kell vennünk a második sort, ahol még nem tudjuk melyik cellában van a nagyobb szám, de onnantól kezdve biztosak lehetünk, hogy az A oszlopbeli érték a nagyobb.

Tehát a második oszlop második sora így fog kinézni:

=HA(A1<B1;MARADÉK(B1;A1);MARADÉK(A1;B1))

A további sorokba pedig (figyelve arra, hogy a felesleges nullákat ne jelenítsük meg):

=HA(ÉS(B2>0;B2<>"");MARADÉK(A2;B2);"")

Ezek után már csak a C1 cella kitöltése a feladatunk, amit legegyszerűbben úgy kapunk meg, ha megnézzük melyik a legkisebb elem az első oszlopban. =MIN(A:A)

A letölthető megoldás Kovács Péter (11.évf, Szolnok, Verseghy Ferenc Gimnázium) dolgozata alapján készült.

Schmidt Zoltán


Statistics:

21 students sent a solution.
10 points:Balambér Dávid, Bóra Eszter, Fábián András, Gál Tibor, Gilián Zoltán, Gombos Gergely, Gulyás 990 Péter, Györök Péter, Gyüre Balázs, Kiss Dániel Miklós, Kovács 129 Péter, Ozsvárt László, Ökrös Tamás, Pápai Dávid, Szikszay László, Szoldatics András, Véges Márton, Vincze János.
8 points:1 student.
3 points:1 student.
0 point:1 student.

Problems in Information Technology of KöMaL, January 2006