Hodina 5. ročníka - 26. mája 2015 - Algopedia

Obsah

Budeme diskutovať o niektorých klasických problémoch, s vektormi alebo bez nich.

Moc

Vypočítajte n čo najefektívnejšie (prirodzené čísla aan). Problém je tiež známy ako logaritmický rast. Myšlienka tohto riešenia je táto:

Ak je n párne, potom a n = a 2 * n/2 = (a 2) n/2
Ak je n nepárne, potom n-1 je párne a máme an = a * a n-1 = a * a 2 * (n-1)/2 = a * (a 2) (n-1)/2 = a * (a 2) n/2

Vo vyššie uvedených vzorcoch sme uvažovali, že/je celočíselné rozdelenie jazyka C. Preto keď n je nepárne (n-1)/2 je rovnaké ako n/2. Pozorovalo sa, že bez ohľadu na paritu n, v každom kroku iterácie môžeme transformovať a na a * a potom môžeme deliť n číslom 2. Iba v prípadoch, keď n je nepárne, akumulujeme aktuálnu hodnotu a vo vypočítanom produkte. Tu je riešenie založené na tejto myšlienke:

Monotónna postupnosť

Povedzte, či je postupnosť čísel jednotvárna. Postupnosť je monotónna, ak sú jej počty vzostupne alebo zostupne. Sekvencia má najmenej dve čísla. Nie je dovolené používať polia (vektory alebo matice).

zátvorky

Ak dáte postupnosť 0 a 1, kde 0 znamená otvorenú zátvorku „(„ a 1 znamená uzavretú zátvorku „)“, povedzte, či je postupnosť správnym vyjadrením zátvoriek a či chcete vypočítať maximálny počet zátvoriek v druhej. Príklad: 0 1 0 0 1 0 1 1 je správny a má faktor vnorenia 2, zatiaľ čo postupnosť 0 0 0 1 1 1 0 je nesprávna. Nie je dovolené používať polia (vektory alebo matice).

Problém môžeme vyriešiť dodržaním nasledujúcich pravidiel platných pre akýkoľvek správny výraz:

kdekoľvek výraz „zlomíme“, vľavo budeme mať počet otvorených zátvoriek väčší alebo rovný uzavretým
na konci sa musí počet uzavretých zátvoriek rovnať uzavretým

Ak sú splnené obe podmienky, výraz je správny. Prvá podmienka musí byť splnená pre každú polohu prerušenia.

Téma domácich úloh: ako zovšeobecňujeme? Máme okrúhle zátvorky, štvorce a rovnátka, rovnaká požiadavka.