Java - algoritmus – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Java - algoritmus – Java – Fórum – Programujte.comJava - algoritmus – Java – Fórum – Programujte.com

 
Hledat
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vytvořte si vlastní webové stránky. Snadno, rychle a levně přes Saywebpage.com
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno
Laser Game Ostrava

Marek
~ Anonymní uživatel
512 příspěvků
11. 3. 2020   #1
-
0
-

Zdravím,

potreboval by som pomôcť s vymyslením vhodného algoritmu k takejto úlohe:
V poli budem mať uložené celé čísla, ktoré budú utriedené vzostupne a môžu sa opakovať. Metóda vráti, či existujú v poli dve čísla také, že ich súčet bude presne hodnota, ktorá sa zadá do parametra. 
Viem, že to ide urobiť vo vnorenom cykle, ale potrebujem to v čase lepšom ako O(n^2).

Ďakujem za akékoľvek rady.

Nahlásit jako SPAM
IP: 176.102.96.–
11. 3. 2020   #2
-
0
-

Určil bych si rozdíl zadané - nejmenší = největší možné číslo, které může být jako druhý sčítanec a rozdíl zadané - největší = nejmenší možné číslo, které může být jako druhý sčítanec. Pak bych se snažil najít ty prvky v poli, které budou ležet vně  co nejblíž k hranici takto daného intervalu. Na výsledném intervalu bych postup zopakoval.

Musíš vyzkoušet, zda funguje. Je to jen nápad.

hu

Nahlásit jako SPAM
IP: 195.178.67.–
Kit+14
Guru
11. 3. 2020   #3
-
0
-

#1 Marek
Definuji dva indexy - jeden na první a jeden na poslední prvek. Sečtu hodnoty na těchto indexech. Pokud bude součet vyšší než parametr, snížím druhý index. Pokud bude nižší, zvýším první index. Pokud stejný, jsem hotov - existuje. To celé v cyklu, dokud je nižší index menší než horní. Pokud se indexy potkají, součet neexistuje.

Nahlásit jako SPAM
IP: 94.112.251.–
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
peter
~ Anonymní uživatel
3588 příspěvků
12. 3. 2020   #4
-
0
-

 A na O(n^2) jsi prisel jak?
Kdyz otestujes hodnotu na prvnim radku v prvnim cyklu a cisla jsou serazena, tak ve druhem cyklu prvnim kroku s jednickou uz nepracujes, ne? Takze to bude n/2 * (n+1) kroku, soucet rady cisel 1+2+3...+n.
A dal to uz vyplyva z toho, ze to mas serazene a z predchozich kroku.
Takze, kriticke hodnoty algoritmu pak jsou cislo<[0]+[1] a cislo=[n-1]+[n] (cislovani radku je od nuly), cili cislo <1+2 (nejmene kroku, 1) nebo cislo>3+4(nejvic kroku).

soucet cisel = 4

1 | 1+2<=4 ? 1+2==4 : end
2 | 1+2<=4 ? 1+2==4 : end
2 | 1+3<=4 ? 1+3==4 : end
3 | 1+4<=4 ? 1+4==4 : end -- 1+4 nevyhovuje prvni podmince, algoritmus skonci
4

1 
2 | 2+2<=4 ? 1+2==4 : end
2 | 2+3<=4 ? 2+3==4 : end -- 2+3 nevyhovuje prvni podmince, algoritmus skonci
3
4

1 
2 
2 | 2+3<=4 ? 2+3==4 : end -- 2+3 nevyhovuje prvni podmince, algoritmus skonci
3
4
A kdyz se cyklus provede jen 1x a hned skonci a protoze jsou cisla serazena,
nema vyznam dal testovat.

Nahlásit jako SPAM
IP: 2001:718:2601:258:1d39:5f06:3159:72a1...–
peter
~ Anonymní uživatel
3588 příspěvků
12. 3. 2020   #5
-
0
-

Mozna bych tu podminku mel rozepsat...
Prvni if testuje, zda je soucet cisel na radcich i a i+1 mensi nebo rovno zvolenemu cislu.
A druhy if, pokud prvni projde, tak testuje teprve rovnost a ulozi reseni nebo posune cyklus.
Pokud prvni test neprojde, tak se prvni cyklus zastavi a zacne se dalsi od radku i=j. Kde j je pocet provedenych cyklu1. Cili cylus(j=0; j<5radku; j++) {cylus(i=j; i<5radku; i++)}

1+2<=4 ? 1+2==4 : end
1+2<=4 ? (1+2==4 ? save : continue) : end
Nahlásit jako SPAM
IP: 2001:718:2601:258:1d39:5f06:3159:72a1...–
peter
~ Anonymní uživatel
3588 příspěvků
12. 3. 2020   #6
-
0
-

   

soucet = 4
1 | a
2 | . . a
2 | . . . b
3 | . b
4 | b
a==b ? end : ([a]+[b]>4 ? b-- : ([a]+[b]<4 ? a++ : save, a++ nebo b--))
a==b ? end : ([a]+[b]>4 ? b-- : ([a]+[b]<4 ? a++ : save, a++ nebo b--))

Podle mne, KIT to ma spatne. Ukolem je najit vsechny soucty, ne prvni. A v tom pripade pri stavu, ze se soucet==4 nastava krize, protoze musi bud zvysit A nebo snizit B. A pokud pod A jsou 2 hodnoty stejne a on snizi B, tak se pripravi o jedno reseni.
1 1 3 3 = 1+3 1+3, 1+3, 1+3 = 4 reseni
KIT udela toto
(1) 1 3 (3) ... 1+3 save, a++
1 (1) 3 (3) ... 1+3 save, a++
1 1 (3) (3) ... 3+3, b--
a==b end

Nahlásit jako SPAM
IP: 2001:718:2601:258:1d39:5f06:3159:72a1...–
peter
~ Anonymní uživatel
3588 příspěvků
12. 3. 2020   #7
-
0
-

Ale, pokud by slo o nalezeni prvni hodnoty, tak jeho reseni staci. Coz mozna odpovida zadani. Nevim, mne to moc nesedi. Ale asi to tak v zadani je.
"existujú v poli dve čísla také, že ich súčet bude presne hodnota"

Nahlásit jako SPAM
IP: 2001:718:2601:258:1d39:5f06:3159:72a1...–
MilanL+1
Expert
12. 3. 2020   #8
-
0
-

#7 peter
u Kitovo řešení není problém zaznamenat výsledek a pokračovat dál dokud se nesejdou indexy 

Nahlásit jako SPAM
IP: 91.139.9.–
MilanL+1
Expert
12. 3. 2020   #9
-
0
-

Také jde o rozsah pole a jeho hodnot, v některých případech, když hodnota součtu bude uvnitř intervalu hodnot pole, by se mohlo vyplatit i najít, pomocí algoritmu půlení, v poli nejbližší číslo menší nebo rovno hodnotě součtu a hledat pak v tomto redukovaném rozsahu pole.

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

Přidej příspěvek

×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, 16 hostů

Podobná vlákna

Algoritmus — založil RePRO

C++ algoritmus — založil silent

Algoritmus — založil Jirina.K

Moderátoři diskuze

 

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