Gyakorlati alapok
Euklidész, a zseniális burkolómester, avagy a világ első algoritmusa
Az előző, A legnagyobb, egyúttal a legkisebb közösködő című fejezet bevezette azt a témakört, amely voltaképpen a zseniális ógörög matematikustól, Alexandriai Euklidésztől (Kr. e. 300 körül) indult el. Munkásságát jól ismerhetjük az Elemek (Sztoikheia) című munkájából, amelyben többek között a matematika egyik fontos ágát, a geometriát alapozta meg. Szintén ebben a művében található a világ egyik legrégibb algoritmusának leírása, amely két szám legnagyobb közös osztóját állapítja meg több lépésben. Emlékezzünk vissza a fogalmakra az előző fejezetből:
Két vagy több pozitív szám esetében a legkisebb közös többszörös az a szám, amelyik még mindegyik számmal osztható.
Két pozitív egész szám közös osztói közül a lehetséges legnagyobb (nem 0) pozitív egész, amely mindkét egész számot maradék nélkül osztja.
A két matematikai fogalom nyilvánvalóan összetartozik és bizonyos összefüggések szerint kölcsönösen egymásba konvertálhatók: két szám legnagyobb közös osztójának és legkisebb közös többszörösének szorzata egyenlő a két szám szorzatával:
legnagyobbKozosOszto(a, b) * legkisebbKozosTobbszoros(a, b) = a * b;
No de mi köze mindennek a hidegburkoláshoz?
A kérdés megválaszolásához be kell pillantanunk Józsi bácsi, a tapasztalt burkolómester dolgos hétköznapjaiba. Adott egy 2 x 5 méteres helyiség, amelyet járócsempével kell burkolnia. Vajon mekkora lesz annak a járócsempének a mérete, pontosabban oldalhossza, amelyet mindenféle további vagdosás (tehát anyagmaradék nélkül) felhasználhat?
A kérdés feltevése során nyilvánvalóan eltekintünk ama ténytől, hogy a járócsempe-gyártók nem nagyon szoktak egyedi méretű csempéket készíteni, de ha igen, ez a mi szempontunkból annál jobb.
A válasz a 2 oldalhossz közös osztójának megtalálásában van.
A példánál maradva először számoljuk át a métert centiméterre:
2 x 5 méter = 200 x 500 centiméter
Ezután meg kell találnunk a 2 oldalhossz közös osztóját. A közös osztókereső algoritmus működési leírása az előző, A legnagyobb közösködő című fejezetben található, ezért itt és most nem részletezzük. A végeredmény 100 lesz.
Egy 200 x 500 centiméteres helyiség 100 cm oldalhosszú járócsempével maradék nélkül lefedhető.
Ellenőrizzük ezt le az alábbi futtatható Java-kódban:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int elsoSzam, masodikSzam;
do {
System.out.print("Kérjük adja meg az
1. oldalhosszt (nagyobb 0-nál): \n");
String elso = in.nextLine();
elsoSzam = Integer.parseInt(elso);
System.out.print("Kérjük adja meg a
2. oldalhosszt (nagyobb 0-nál): \n");
String masodik = in.nextLine();
masodikSzam =
Integer.parseInt(masodik);
}while (elsoSzam <= 0 || masodikSzam <= 0);
int szorzat = elsoSzam * masodikSzam;
int maradek = elsoSzam % masodikSzam;
while (maradek != 0){
elsoSzam = masodikSzam;
masodikSzam = maradek;
maradek = elsoSzam % masodikSzam;
}
System.out.println ("A járócsempe oldalmérete: " + masodikSzam);
}
}
Végeredmény:
Kérjük adja meg az 1. számot (nagyobb 0-nál):
200
Kérjük adja meg a 2. számot (nagyobb 0-nál):
500
A járócsempe oldalmérete: 100
Természetesen az algoritmus pontos értéket szolgáltat rafináltabb oldalhosszok esetében is. Nézzünk meg például egy 252 x 105 cm oldalhosszú spájz optimálisnak tűnő járócsempe adatait:
Kérjük adja meg az 1. számot (nagyobb 0-nál):
252
Kérjük adja meg a 2. számot (nagyobb 0-nál):
105
A járócsempe oldalmérete: 21
No de jók-e nekünk ezek az értékek, hiszen milyen számot is találtunk meg? A legnagyobb közös osztót, ennek kiírása után pedig az algoritmus dolgát végezve megáll.
Igazából Józsi bácsi nem igazán tud mit kezdeni olyan információval, miszerint egy 2 x 5 méteres helyiséget 1 méter oldalhosszú csempével fedjen le.
Ehelyett jóval hasznosabb egy olyan algoritmus készítése, amely kilistázza az összes közös osztót, amelyből aztán Józsi bácsi kiválaszthatja a számára legmegfelelőbbet.
Az alábbi futtatható Java-kód ezt fogja nekünk megtenni. Legfontosabb része a pontos feltételmegadás a léptető for cikluson belül...
if((elsoSzam % i == 0) && (masodikSzam % i == 0))
...amely mindkét oldal maradék nélküli oszthatóságát vizsgálja.
A kód további érdekessége, hogy alapjában véve édesmindegy, honnan indul a for ciklus lefelé léptetése: az elsoSzam vagy a masodikSzam változótól, noha azt gondolhatnánk, hogy ez lényeges. (Csak annyiban az, hogy ha nagyobb számtól indulunk, feleslegesen futott a ciklus, amíg el nem érjük a kisebb számot, hiszen egyszerre két szám tulajdonságát vizsgáljuk.) Következésképpen elég volna a kisebb számtól indulnunk, ekkor azonban néha egy adatcsereberét kéne elkövetnünk (Hogyan cseréljünk meg kezeinkben 2 teli poharat? (adatcserebere) című fejezet). Ezt nem implementáltam, legyen ez a Tisztelt Olvasó házi feladata.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int elsoSzam, masodikSzam;
do {
System.out.print("Kérjük adja meg az
1. oldalhosszt (nagyobb 0-nál): \n");
String elso = in.nextLine();
elsoSzam = Integer.parseInt(elso);
System.out.print("Kérjük adja meg a
2. oldalhosszt (nagyobb 0-nál): \n");
String masodik = in.nextLine();
masodikSzam =
Integer.parseInt(masodik);
}while (elsoSzam <= 0 || masodikSzam <= 0);
System.out.println();
System.out.print(elsoSzam + " és " + masodikSzam + " közös
osztói: ");
for(int i = masodikSzam; i > 0; i--){
if((elsoSzam % i == 0) && (masodikSzam
% i == 0)){
System.out.print(i + " ");
}
}
}
}
Végeredmény:
Kérjük adja meg az 1. oldalhosszt (nagyobb 0-nál):
252
Kérjük adja meg a 2. oldalhosszt (nagyobb 0-nál):
105
252 és 105 közös osztói: 21 7 3 1
Az algoritmus prímszámok esetében is működőképes (Prímszám-e? című fejezet), ám ekkor természetesen a prímszám-tulajdonságból következően az egyedüli oldalhossz 1 lesz:
Végeredmény:
Kérjük adja meg az 1. oldalhosszt (nagyobb 0-nál):
7
Kérjük adja meg a 2. oldalhosszt (nagyobb 0-nál):
3
7 és 3 közös osztói: 1
Ha jobban belegondolunk, a lista legalját mindig és kizárólag 1 egység csempeoldalhossz fogja zárni, hiszen mindkét oldalhossz garantáltan osztható önmagával is (például 150 / 150 = 1), illetve ha mindkét oldalhossz páros szám, akkor a lista legalján az 1. helyen 1, a 2. helyen mindig és kizárólag 2 egység csempeoldalhossz lesz és így tovább. De például egy 5000 x 3000 centiméteres helyiség 1 centiméter oldalhosszú csempéjével Józsi bácsi nem fog tudni mit kezdeni (hacsak éppen nem mozaikot rak). A lényeg azonban, hogy a listából már képes lesz kiválasztani az optimális csempeméretet.
Józsi bácsinak még annyit tudunk segíteni: kiszámoljuk neki, hogy hány db járócsempére lesz szüksége. Ezt nem nehéz illusztrálnunk. Az egyszerűsítés kedvéért induljunk ki a már említett 2 x 5 egység oldalhosszú helyiségünkből:
Jól láthatjuk, hogy 1 egység oldalhosszú járólapból, csempéből hány darabra van szükség: 10 darabra. A vizualitáson felül ennek matematikai képlete:
helyiség területe (a * b) / járócsempe területe (osztó * osztó)
Nézzük meg a futtatható Java-kódot:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int elsoSzam, masodikSzam, csempeHossz;
boolean rosszAdat = false;
do {
System.out.print("Kérjük adja meg az
1. oldalhosszt (nagyobb 0-nál): \n");
String elso = in.nextLine();
elsoSzam = Integer.parseInt(elso);
System.out.print("Kérjük adja meg a
2. oldalhosszt (nagyobb 0-nál): \n");
String masodik = in.nextLine();
masodikSzam = Integer.parseInt(masodik);
}while (elsoSzam <= 0 || masodikSzam <= 0);
System.out.println();
System.out.print(elsoSzam + " és " + masodikSzam + " közös
osztói: ");
for(int i = masodikSzam; i > 0; i--){
if((elsoSzam % i == 0) && (masodikSzam
% i == 0)){
System.out.print(i + " ");
}
}
System.out.println();
do {
rosszAdat = false;
System.out.print("Kérjük adja meg a
kiválasztott csempehosszt (nagyobb 0-nál és szerepel a listában):\n");
String csempe = in.nextLine();
csempeHossz = Integer.parseInt(csempe);
if(csempeHossz <= 0){
rosszAdat =
true;
continue;
}
if((elsoSzam % csempeHossz != 0) || (masodikSzam
% csempeHossz != 0)){
rosszAdat =
true;
}
}while (rosszAdat);
System.out.println ("A helyiség alapterülete: " + (elsoSzam *
masodikSzam));
System.out.println ("1 db járócsempe alapterülete: " + (csempeHossz
* csempeHossz));
double csempeMennyiseg = (elsoSzam * masodikSzam) / (csempeHossz
* csempeHossz);
System.out.println ("A szükséges járócsempe-mennyiség: " +
csempeMennyiseg + " db");
}
}
Végeredmény:
Kérjük adja meg az 1. oldalhosszt (nagyobb 0-nál):
525
Kérjük adja meg a 2. oldalhosszt (nagyobb 0-nál):
0
Kérjük adja meg az 1. oldalhosszt (nagyobb 0-nál):
525
Kérjük adja meg a 2. oldalhosszt (nagyobb 0-nál):
105
525 és 105 közös osztói: 105 35 21 15 7 5 3 1
Kérjük adja meg a kiválasztott csempehosszt (nagyobb 0-nál és szerepel a
listában):
0
Kérjük adja meg a kiválasztott csempehosszt (nagyobb 0-nál és szerepel a
listában):
6
Kérjük adja meg a kiválasztott csempehosszt (nagyobb 0-nál és szerepel a
listában):
21
A helyiség alapterülete: 55125
1 db járócsempe alapterülete: 441
A szükséges járócsempe-mennyiség: 125.0 db
A kód nem engedi, hogy bárhol 0 kerüljön a rendszerbe, mert az osztásos műveletek miatt garantált a 0-val osztás kivétele, rossz csempehossz megadása esetén pedig újfent bekéri az adatot.
Ugyanakkor az előzetes közös osztó keresése azt is szavatolja, hogy a további osztás ellenére a végeredmények szintén egész számok lesznek! Józsi bácsi tehát megnyugodhat: nem kell csempéket vagdosnia.
Pénzes László