Největší společný dělitel – Java – Fórum – Programujte.com

Potřeboval bych najít největší společný dělitel více čísel. Našel jsem plno implementací pro dvě čísla pomocí euklidova algoritmu, ale to mi je k ničemu. Potřebuji najít největší společný dělitel čísel zadaných například do pole.

Díky za jakoukoliv radu

Vytvor si dve metody, Obe by mali prijimat dva parametry a vraciat int. Jednu na urcenie NSN (najmensi spolocny nasobok) napr. aj pomocou prvociselneho rozkladu.Druhu na urcenie NSD (najvacsi spolocny delitel) pomocou vzorca (a*b)/NSN(a,b)

Prvy prvok pola uloz do pomocnej premennej napr. tempResult. Potom v cykle for prechadzaj pole od prvku z indexom pole[1], a zavolaj metodu NSD (tempResult, pole[1]), vysledok uloz do pomocnej premennej  tempResult. Potom nacitaj tretie cislo a zavolaj metodu NSD(tempResult, pole[2]), vysledok znova uloz do temResult. Nacitaj stvrte, NSD(tempResult, pole[3]) a takto az do konca pola. Po poslednom prechode cyklu for ti v premennej tempResult ostane NSD vsetkych cisiel.

Dufam, ze ma pochopis. Malo by to funguvat, bohuzial nemam teraz cas aby som to naprogramoval a vyskusal.

#1 Dave
Ahoj, vyšťoural jsem z nosu něco takovýho, sice to asi není tak sofistikovaný jako ten Bucovo algoritmus (kterej jsem teda nečetl, protože je moc dlouhej) ale myslím že by to mohlo fungovat. Zdroj vstupních dat si jistě zajistíš sám, já je dával natvrdo :) + samozřejmě ty velikosti pole mam prasácky statický ;)

public static int maxSpolDelitel (int a, int b){
        int max = 1;
        for(int i=1; i<Math.max(a,b); i++){
            if(((a % i)==0)&((b % i)==0)){
                max = i;
            }
        }
        return max;
    }
    
    public static void main(String []args){
    
	int cisla []= {10, 10, 5, 25, 10};
        int max = Integer.MAX_VALUE;
        for(int i = 0; i<5; i++){
            for(int j = 0; j<5; j++){
                if(j!=i){
                    max = Math.min(max, maxSpolDelitel(cisla[i], cisla[j]));
                }
            }
        }
        System.out.println(max);
    }

ale pozrite si ucebnicu pre zakladne skoly a dozviete sa ze staci daco taketo:

int cisla[] = { 12,567,234,567,123};

int max = cisla[0];

for (int i = 0;i<size(cisla);i++) {
	max = gcd(max,cisla[i]); // funkcia gcd je najvacsi spolocny delitel 2 cisel
}

return max;

pri tom cykle dokonca staci int od 1 lebo gcd(a,a)=a ;)

#4 nergal

1) co s tím má co dělat učebnice základní školy?? Euklidův rozklad stejně vede na rozklad na prvočinitele

2) pouze si použil nějakou knihovní funkci, já jí napsal .. + GCD je podle mě implementovaná pouze pro BigInteger

3) OK, stačí projít celé pole, nemusí se porovnávat každý s každým

noo.. ve skutečnosti gcd vypadá špíše nějak takto 

public static int gcd(int a, int b) {
    if (a < 1 || b < 1)
        throw new IllegalArgumentException("Zadný parametr nesmí být menší než 1!");

    while (b != 0) {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

potom přidat cyklus pro průchod polem.. toť vše

#5 TheOndrap
napisal ze pozna algoritmus na gcd pre dva prvocinitele v kazdej ucebnici zo zakladnej skoly kde sa bere euklidov algoritmus je napisane ako sa postupuje ak chces pre viac cisel ako 2...

a rozklad na prvocinitele? neblazni.. staci euklidov algoritmus so zlozitostou O(n)=log n napisal ho ingiraxo

Děkuji všem mockrát. Ale asi jsem se špatně vyjádřil k zadání programu. 

Já první zadám velikost pole (např: 6)

Poté zadám 5 různých čísel, abych zaplnil pole (např: 1, 2, 3, 4, 5, 6)

Toto vše už mam.

Ale teď musím najít největší společný dělitel čísel v poli, takže výstup by mělo být číslo 3.

Děkuji za vaši trpělivost :D

#8 Dave
A to od kedy, ak sa mozem opytat je NSD (1,2,3,4,5,6) = 3. Toto zrejme nebude pravda, kedze je tam 1a 2. Bud sa pytas na ini algoritmus, je to preklep, alebo nevies co je NSD.

V tom tretom pripade, NSD je najvacsi spolocny delitel, takze ak mas NSD(a,b)=k potom k musi celociselne delit a aj b a navyse je to najvacsie take cislo. To z tych cisel co si dal bude 1.

V druhom sa ti ospravedlnujem.

V prvom ak si chcel nejaky algoritmus, mozno by nebolo od veci napisat co si chces a potom mozno aj tvoje riesenie, ak si ho vyriesil ;) . (Na ten prvy pripad som nemal co napisat, tak som napisal aspon toto, lebo mozno to niekedy niekomu pomoze). ;)

#5 TheOndrap
Preco si dal nergalovi -1, ked ma pravdu?

Takže jsem to napsal asi znovu špatně :D. Mám z té množiny čísel (1, 2, 3, 4, 5, 6) najít největší společný dělitel dvou prvků, který v poli existuje. Tudíž z množiny (1, 2, 3, 4, 5, 6) to vezme čísla 3 a 6 a z nich největší společný dělitel jsou 3. Samozřejmě je tam i třeba 2 a 4, ale jejich NSD jsou 2 a 2 jsou menší než ty 3.

#11 Dave
Aha no takto to je no potom ti nezostava napisat nic ine ako kod ktory pozostava z porovnania NSD vsetkych prvkou. Co si uz asi napisal :D. Mozno taky hint ze ak mas prvky v poli x_i a x_j take ze ich NSD(x_i, x_j)=k a existuju v tom poli prvky mensie ako k tak tie nemusis porovnavat. Takze ak mas pole (x_1,x_2,...,x_l, x_{l+1}, ..., x_i,....,x_j,....x_n), kde n jepocet porvkov a ako pred tym NSD(x_i, x_j)=k a plati k> x_l. Tak prvky od x_l po x_1 uz nebudes porovnavat. Niesom informatik takze mozno existuje algoritmus ktory toto vie este efektyvnejsie porovnat. Ale tak toto je moja prvotna myslienka. Takze:
1.) Zorad pole;

2.) Hladaj NSD od najvacsich cisle, asi takto NSD(x_n, x_{n-1}).... NSD(x_n, x_{n-m})=o a o je viac ako x_l alebo tak nejako. Jednoducho vzdy zmensis mnozinu pokial mas hladat.

Mozno to vysvetlim na tvojom priklade:

mam pole prvku {1,2,3...,6}. Spocitam NSD(5,6)=1 takze idem so 6 iba po 2. 2. krok NSD(6,4)=2, takze zmenim pole iba po 2: skumam prvky iba od {2,...,6} . idem na NSD(3,6)=3; Zmenim pole od {3,4,5,6} a skumam len toto pole. Chapes vzdy skumas iba prvky kore su vacsie ako NSD lebo mensie a rovne ti nedaju vacsi vysledok. ;).