Adott egy \(n\) elemű egész számokat tartalmazó \(A\) vektor.
1. Adjuk meg azt a \(P\) és \(Q\) indexet, ami maximalizálja a \(\sum_{i=P}^{Q}A[i]\) részvektort. Az algoritmus műveletideje legyen \(O(n)\).
2. Válasszuk ki a vektor második legkisebb elemét \(n + O(log_{2}n)\) összehasonlítással.
Hétvégén egy mezőn jártam,
néhány fával, mindegyiken több madárral.
Több mint egy fa, már-már erdő,
s mennyi madár, egész felhő.
Járok-kelek, nézegetek.
Számolgatok, jegyzetelek.
Elámulok, mit álmodok?
Minden fán ugyanannyi madár,
összesen 200-300 is meglehet tán!
Tovább bonyolódik az eset:
pontos számukból a fák száma is meglehet.
Két feladat az én drága olvasóimnak. Nem annyira nehezek, de az elsőnek annyira szép a megoldása, hogy muszáj leírni, a másikat meg csak azért, mert ott találtam az első mellett.
Adott egy teniszkupa 127 indulóval. Egyenes kiesés szerint játszanak, tehát az első körben 2*63 ember játszik egymással, egy szerencsés pedig automatikusan bejut a következő fordulóba. Ezután a maradék 64 játszik 32 meccset, stb., stb.
Összesen hány meccset kell játszani ahhoz, hogy győztest lehessen hirdetni? (Ha ez megvan, akkor általánosítsuk “n” indulóra a feladatot.)
Van 8 biliárdgolyónk, közülük 7 egyforma nehéz, az egyik viszont kicsit nehezebb náluk. Van még egy remek kétkarú mérlegünk is, amire akárhány golyót fel lehet pakolni, és - ahogy már nyilván kitalálták – megmondja, hogy melyik serpenyőjében van több súly.
Hány mérés kell ahhoz, hogy a nyolc golyóból megtaláljuk a nehezebbet? (Majdnem azt írtam, hogy a kakukktojást, de úgy egy egész más feladatról kezdenénk el beszélgetni, ahogy Önöket ismerem.)