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

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.

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

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

 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.

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

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

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"

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

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.