Největší společný dělitel – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Dave
~ Anonymní uživatel
22 příspěvků
10. 11. 2012   #1
-
0
-

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

Nahlásit jako SPAM
IP: 46.167.205.–
Reklama
Reklama
Buco0
Newbie
10. 11. 2012   #2
-
0
-

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.

Nahlásit jako SPAM
IP: 195.91.108.–
TheOndrap+2
Super člen
11. 11. 2012   #3
-
0
-

#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);
    }
Nahlásit jako SPAM
IP: 88.102.250.–
ZČU v Plzni je mnohem víc, než jenom právnická fakulta !!
Fakulta aplikovaných věd www.fav.zcu.cz
"Když nedokážete říci věci jednoduše, pak jim dostatečně nerozumíte"
nergal+1
Návštěvník
11. 11. 2012   #4
-
-1
-
Mimo téma

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 ;)

Nahlásit jako SPAM
IP: 85.135.129.–
viem že neviem čo viem
TheOndrap+2
Super člen
11. 11. 2012   #5
-
0
-

#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

Nahlásit jako SPAM
IP: 88.102.250.–
ZČU v Plzni je mnohem víc, než jenom právnická fakulta !!
Fakulta aplikovaných věd www.fav.zcu.cz
"Když nedokážete říci věci jednoduše, pak jim dostatečně nerozumíte"
ingiraxo+15
Grafoman
11. 11. 2012   #6
-
0
-

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

Nahlásit jako SPAM
IP: 213.168.183.–
Moje aplikace: http://ophite.cz
Tutoriály na: C#
nergal+1
Návštěvník
11. 11. 2012   #7
-
-1
-
Mimo téma

#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

Nahlásit jako SPAM
IP: 85.135.129.–
viem že neviem čo viem
Dave
~ Anonymní uživatel
22 příspěvků
11. 11. 2012   #8
-
0
-

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

Nahlásit jako SPAM
IP: 46.167.205.–
sleepy0
Stálý člen
11. 11. 2012   #9
-
0
-

#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). ;)

Nahlásit jako SPAM
IP: 158.195.195.–
sleepy0
Stálý člen
11. 11. 2012   #10
-
0
-

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

Nahlásit jako SPAM
IP: 158.195.195.–
Dave
~ Anonymní uživatel
22 příspěvků
11. 11. 2012   #11
-
0
-

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.

Nahlásit jako SPAM
IP: 94.112.37.–
sleepy0
Stálý člen
11. 11. 2012   #12
-
0
-

#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. ;).

Nahlásit jako SPAM
IP: 158.195.195.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 27 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý