Diskuze: Najväčší delenec

V předchozím kvízu, Online test znalostí Java, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Neaktivní uživatel

Člen

Neaktivní uživatel:28.9.2017 17:55

Ahoj, potreboval by som pomôcť s algoritmom. Snažím sa prísť na chybu sám, skúšam si dosadzovať za premenne čísla, ale neviem na to prísť. Chcem na základne vopred daného čísla (nazvem ho a) vyhľadať v poli čo najdlhší súvislý úsek, ktorý keď sčítam, tak dostanem najväčšieho možného delenca. Deliteľom je naše vopred dané číslo a. Samozrejme chcem, aby delenec % a == 0 . Platí, že čísla v poli, aj číslo a patria množine celých kladných reálnych čísel. Rozmýšľal som takto, ale moc mi to nefunguje:

long povSucet = sucet;
long delenec = 0;

for(int i =0; i < pocet; i++){
        for(int j = pocet - 1; j >= i; j--){
                if(sucet % a == 0 && j+1 > delenec)
                        delenec = j+1;
                sucet -= pole[j];
        }
        sucet = povSucet;
        for(int k = 0; k < i+1 ; k++)
                sucet -= pole[k];

        if(sucet % a == 0 && (pocet - i - 1)  > delenec)
                delenec = (pocet - i - 1);
}

System.out.println(delenec);

Pre začiatok som si vytvoril premenne delenec, do ktorého chcem pridať najdlhší súvislý úsek z poľa, ktorý vyhovuje podmienkam, a premenna povSucet predstavuje pôvodný súčet všetkých prvkov v poli. Je tam preto, že v nasledovnom cykle pracujem s premennou sucet a odpočítavam od nej (potom ju potrebujem vrátiť na pôvodnu hodnotu). Nasleduje môj nevydarený algoritmus pocet je počet všetkých prvkov v poli. Sucet je ich súčet. Treba vysvetliť konkrétnejšie ako to malo fungovať? Mimochodom, ak takýto delenec neexistuje, tak len vypíšem 0 Vopred ďakujem za každý nápad aj kritiku.

Odpovědět

28.9.2017 17:55

Neaktivní uživatelský účet

Peter Sciranka

Tvůrce

Peter Sciranka:28.9.2017 19:26

Ahoj, skús napísať nejaký konkrétky príklad, číslo a čo potrebuješ aby bol výsledok, nie som si úplne istý či som to pochopil a na konkrétnom prípade sa takéto úlohy chápu najlepšie. (Inak prepáč že podpichnem, ale je buď "množina celých kladných čísel" alebo "kladných reálnych čísel" ale nie je "celých kladných reálnych čísel" .

Nahoru Odpovědět

28.9.2017 19:26

Act as if it was Impossible to Fail

Neaktivní uživatel

Člen

Neaktivní uživatel:28.9.2017 19:54

S tými množinami máš pravdu tak teda - množina celých kladných čísel. Oukej skúsim nejaký príklad:

Dostávame: a = 2; pocet (počet čísel v poli) = 6; pole[] = { 3, 4, 1, 2, 4, 3};
Hľadáme: Najdlhší súvislý úsek v poli, ktorého keď jednotlivé prvky sčítame, tak dostaneme nejaké číslo. Ak toto číslo vydelíme s a, teda v tomto konkrétnom prípade s dvojkou, tak nám po delení ostane zvyšok práve 0. Ako výstup potrebujem vypísať na jediný riadok dĺžku takého úseku.

V tomto prípade by bol výsledok 5. Môžeme napr. sčítať hneď prvých 5 prvkov, teda 3+4+1+2+4 = 14. Platí, že po operácii 14/2 dostaneme zvyšok 0. Žiaden dlhší súvislý úsek, ako 5 už dostať nemôžeme. O kratšie úseky sa nezaujímame. Čiže na výstup vypíšeme číslo 5.

Môže byť takýto vzorový príklad? Snáď som pomohol o niečo priblížiť môj problém.

Nahoru Odpovědět

28.9.2017 19:54

Neaktivní uživatelský účet

Peter Sciranka

Tvůrce

Peter Sciranka:28.9.2017 20:15

Ahoj, na začiatku som si nevšimol že sa jedná o java fórum , ale to nevadí, napísal som ten program v C#, logiku určite pochopíš kód je takýto:

int a = 5;

 // príklad na číslo
 long x = 14285751;
 string xHelp = x.ToString();
 int pocet = x.ToString().Length;

 // navacsi mozny delenec
 int delenec = 0;

 // prejde všetky kombinácie, začína sa na indexe 0, postupuje sa po 1
 for (int i = 0; i<pocet; i++)
 {
     int sucet = 0;
     for(int j = i; j<pocet; j++)
     {
        int number = (int)Char.GetNumericValue(xHelp[j]);
        sucet += number;

        if(sucet%a==0)
        {
            if(j-i+1>delenec)
            {
                delenec = j - i + 1;
            }
        }
     }
}

Console.WriteLine(delenec);

Mne to funguje, tak si to už len napíš v Jave. Dúfam že som pomohol, ak by som to predsa nepochopil, tak napíš a pozriem sa ešte na to.
P.S.: Jedná sa o algoritmus ktorý vlastne počíta všetky možné kombinácie, takže sa nejedná o veľmi efektívny spôsob, ale priznám sa, nemám veľmi naštudované algoritmy, ale pre tvoj príklad by to malo snáď stačiť.

Editováno 28.9.2017 20:16

Akceptované řešení
+20 Zkušeností
+2,50 Kč

Nahoru Odpovědět

28.9.2017 20:15

Act as if it was Impossible to Fail

Peter Sciranka

Tvůrce

Peter Sciranka:28.9.2017 20:23

Inak, teraz ma napadlo, dalo by sa ešte kontrolovať, či súčasný počet čísel (delenec) je väčší rovný ako počet ciefier ktoré budeme kontrolovať, tak sa preruší cyklus, a algoritmus by bol menej náročný.

Nahoru Odpovědět

28.9.2017 20:23

Act as if it was Impossible to Fail

Neaktivní uživatel

Člen

Neaktivní uživatel:28.9.2017 20:35

wow. Klobúk dole rozmýšľal som nad tým až príliš zložito a ono to je v podstate takto ľahké? Ďakujem za pomoc. Ja si to predčasné prerušenie cyklu už budem vedieť urobiť.

Nahoru Odpovědět

28.9.2017 20:35

Neaktivní uživatelský účet

Peter Sciranka

Tvůrce

Peter Sciranka:28.9.2017 20:38

Som rád že som pomohol, ono to je tak ako píšeš, mne sa tiež veľa krát stalo, že človek hľadá ťažké riešenie a pritom to je ľahké a sa potom bije do hlavy ako je možné, že mu to hneď nenapadlo
Drž sa

Nahoru Odpovědět

28.9.2017 20:38

Act as if it was Impossible to Fail

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 7 zpráv z 7.