Keskustelu: Koodit: Java: Suurin yhteinen tekijä

Tämä ohjelma etsii syt:n, eli suurimman yhteinen tekijän kahdelle luvulle. Suurin yhteinen tekijä on korkeintaan pienempi luku.

Koodi

import java.util.Random;

public class Syt {
    public static void main(String[] args){
        Random sattuma = new Random();
        int luku = 0;
        int luku_2 = 0;
        int syt = 0;
        int temp = 0;
        //Arvotaan luvut.
        luku = sattuma.nextInt(1000000);
        luku_2 = sattuma.nextInt(1000000);

        //Katsotaan, onko molemmat luvut jaollisia luvuilla 1-1 000.
        //Myöhemmin luvusta vähennetään tarvittaessa kyseinen jakaja.
        for (int x = 1; x <= 1000; x++){
            if (luku % x == 0 && luku_2 % x == 0){
                //Suurempi yhteinen tekijä löydetty.
                syt = x;
            }
        }
        temp = syt; //Löydetty jakaja
        //Suurin yhteinen jakaja on korkeintaan pienempi luku.
        if (luku <= luku_2){
            syt = luku;
        }
        else if (luku_2 < luku){
            syt = luku_2;
        }
        while (luku % syt != 0 || luku_2 % syt != 0){
            syt -= temp; //Vähennetään löydetty jakaja
        }
        //Näytetään luvut ja suurin yhteinen tekijä.
        System.out.println(luku);
        System.out.println(luku_2);
        System.out.println(syt);
    }

}

Tuo koodi ei anna oikeita tuloksia. Jos esimerkiksi luvut ovat 12345 ja 12345, koodin mukaan suurin yhteinen tekijä on 823, vaikka oikea vastaus on selvästi 12345. (Lisäys: Näköjään korjasitkin nyt koodia tältä osin.)

Lisäksi algoritmisi on järjettömän hidas suurilla luvuilla kuten vaikka 2000000000 ja 2000000001.

Yleensä suurin yhteinen tekijä selvitetään tehokkaalla Eukleideen algoritmilla:

int syt(int a, int b) {
	int c = a % b;
	if (c == 0) {
		return b;
	} else {
		return syt(b, c);
	}
}

int syt_silmukka(int a, int b) {
	int c;
	while ((c = a % b) != 0) {
		a = b;
		b = c;
	}
	return b;
}

Jos rekursiota haluaa oikein tiivistää, voi ajatella, että syt(a, 0) = a, jolloin funktiosta tulee tällainen:

int syt(int a, int b) {
	return b != 0 ? syt(b, a % b) : a;
}

Silmukasta taas voi tiivistää tällaisen:

int syt(int a, int b) {
	while (true) {
		if ((a = a % b) == 0) return b;
		if ((b = b % a) == 0) return a;
	}
}

Tutkin äsken asiaa. Ohjelma antaa näköjään väärän vastauksen, jos luvut ovat yhtäsuuria.

Suurimman yhteisen tekijän voi laskea myös niin, että etsitään yhteistä tekijää niin kauan kunnes luvut ovat samoja, ja saatu tulos on suurin yhteinen tekijä.

JRokka kirjoitti:

Suurimman yhteisen tekijän voi laskea myös niin, että etsitään yhteistä tekijää niin kauan kunnes luvut ovat samoja, ja saatu tulos on suurin yhteinen tekijä.

Hieno juttu, mutta ”etsitään yhteistä tekijää niin kauan kunnes luvut ovat samoja” ei sinänsä kerro yhtään siitä, miten tulokseen päästään. Kuulostaa jotenkin abstraktilta kuvaukselta yllä esittelemästäni Eukleideen algoritmista.

Yhteisen tekijän voi laskea myös esimerkiksi näin. a = 27 ja b = 81. Jos a > b niin a -= b ja jos a < b b -= a. Jos luvut ovat samoja suurin yhteinen tekijä on löydetty. Esimerkissä b on yhden kierroksen jälkeen 54 ja toisen kierroksen jälkeen 27, jolloin a ja b ovat yhtä suuria. Näin suurin yhteinen tekijä on löydetty.

Kyseessä on siis edelleen Eukleideen algoritmi. Luvun vähentäminen toisesta on vain hitaampi tapa jakojäännöksen laskemiseen. Käytännössä jos luvut ovat vaikka 300000001 ja 3, täytyy suorittaa 100000000 + 2 vähennyslaskua, kun taas jakojäännöksiä tarvittaisiin vain kaksi. Jakojäännöksellä toki ei päädytä lopussa samaan lukuun vaan nollaan, mutta tällöin se jäljelle jäävä luku on oikea suurin yhteinen tekijä.

Aina ei ole järkevää keksiä, millä tavalla ”myös” voi tehdä, vaan pitää miettiä, millainen ratkaisu on suhteessa muihin tunnettuihin vaihtoehtoihin.

Kyllähän ”myös” voi jakaa luvut alkutekijöihinsä ja etsiä sitten kaikki yhteiset alkutekijät ja kertoa ne keskenään, mutta tämä on selvästi hitaampi ja monimutkaisempi vaihtoehto kuin Eukleideen algoritmi eli jakojäännöksen käyttö.