HÍREK
LEGUTÓBBI MÓDOSÍTÁSOK SAJÁT
MUNKÁK OKTATÁS és KAPCSOLAT EGYÉB
MÓDSZERTANOK TANULD MEG A JAVA JAVÁT!

Gyakorlati alapok

A legnagyobb, egyúttal a legkisebb közösködő

 

 

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;
 

A futtatható Java-kód tehát két bemeneti adatot vár számításaihoz (int elsoSzam, int masodikSzam). A két pozitív egész számot egy hátultesztelő ciklus ellenőrzi, hogy valamelyikük nem 0 vagy kisebb-e nála (while (elsoSzam <= 0 && masodikSzam <= 0)), mert a szorzásokba és osztásokba nem kerülhet 0. Ezután a "klasszikus", euklideszi algoritmus következik, amely során olyan módon keressük a legkisebb közös osztót, hogy a nagyobb számot elosztjuk a kisebbel, a maradékot pedig eltároljuk. Az elsoSzam lesz a masodikSzam és vele elosztjuk az előzőleg kapott maradékot. A legnagyobb közös osztó az utolsó előtti, még nem 0 maradék lesz. Nézzük meg ezt a lépéssorozatot egy jellemző példán keresztül:

 

legnagyobbKozosOszto(84, 18)

1. 84 / 18 = 4, maradék 12,

2. 18 / 12 = 1, maradék 6,

3. 12 / 6 = 2, maradék 0.

Végeredmény:

Kérjük adja meg az 1. számot (nagyobb 0-nál):
84
Kérjük adja meg a 2. számot (nagyobb 0-nál):
18
A legnagyobb közös osztó: 6
A legkisebb közös szorzó: 252

 

A maradékellenőrzéses euklidészi algoritmust egy elöltesztelő ciklus hajtja végre (while (maradek != 0)). Az eredmény kiírásakor nyilvánvalóan az utolsó, még nem 0 maradék kerül a legnagyobb közös osztó helyére (ezt abban a pillanatban a masodikSzam tárolja), illetve fontos azonosság, hogy a legkisebb közös szorzó a két szám szorzatának és legnagyobb közös osztójának hányadosa (szorzat/masodikSzam):

 

System.out.println ("A legnagyobb közös osztó: " + masodikSzam);
System.out.println ("A legkisebb közös szorzó: " + szorzat/masodikSzam);

 

 

 

 

 

 

 

 

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. számot (nagyobb 0-nál): \n");
        String elso = in.nextLine();
        elsoSzam = Integer.parseInt(elso);
        System.out.print("Kérjük adja meg a 2. számot (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 legnagyobb közös osztó: " + masodikSzam);
    System.out.println ("A legkisebb közös szorzó: " + szorzat/masodikSzam);
    }
}

 

Végeredmény (például):

Kérjük adja meg az 1. számot (nagyobb 0-nál):
68
Kérjük adja meg a 2. számot (nagyobb 0-nál):
12
A legnagyobb közös osztó: 4
A legkisebb közös szorzó: 204