5. évfolyam 39. óra - 2015. május 26. - Algopédia
Tartalom
Megbeszélünk néhány klasszikus problémát, vektorokkal vagy anélkül.
Erő
Számítson ki egy n-t a lehető leghatékonyabban (a és n természetes szám). A problémát logaritmikus emelkedésnek is nevezik. A megoldás ötlete a következő:
- Ha n páros, akkor a n = a 2 * n/2 = (a 2) n/2
- Ha n páratlan, akkor n-1 páros, és van egy = a * a n-1 = a * a 2 * (n-1)/2 = a * (a 2) (n-1)/2 = a * (a 2) n/2
A fenti képletekben azt vettük figyelembe, hogy/a C nyelv egész osztása, ezért ha n páratlan (n-1)/2 megegyezik az n/2-vel. Megfigyelhető, hogy n paritásától függetlenül az iteráció minden lépésében átalakíthatunk egy a-t a * a -vá, majd eloszthatjuk n-t 2-vel. Csak abban az esetben, ha n páratlan, akkor felhalmozzuk az a aktuális értékét a számított szorzathoz. Az ötleten alapuló megoldás:
Monoton sorrend
Mondjuk, ha a számok sorozata monoton. Egy szekvencia akkor monoton, ha a számai növekvő vagy csökkenő sorrendben vannak. A szekvenciának legalább két száma van. Nem használhat tömböt (vektorokat vagy mátrixokat).
zárójel
Adott 0 és 1 szekvencia, ahol a 0 nyitott zárójelet jelent (', az 1 pedig zárt zárójelet') ', mondjuk meg, hogy a szekvencia a zárójelek helyes kifejezése, és hogy kiszámoljuk-e egymásban a zárójelek maximális számát. Példa: A 0 1 0 0 1 0 1 1 helyes és 2-es beágyazási tényező, míg a 0 0 0 1 1 1 0 sorrend helytelen. Nem használhat tömböt (vektorokat vagy mátrixokat).
Megoldhatjuk a problémát az alábbi helyes kifejezésekre vonatkozó szabályok betartásával:
- bárhol is "törjük" a kifejezést, bal oldalon számos nyitott zárójelünk lesz, nagyobb vagy egyenlő, mint a zárt
- a végén a zárt zárójelek számának meg kell egyeznie a zárt zárójelek számával
Ha mindkét feltétel teljesül, a kifejezés helyes. Az első feltételt minden töréshelyzetnek teljesítenie kell.
Házi feladat: hogyan általánosítsunk? Van kerek zárójel, négyzet és merevítő, ugyanaz a követelmény.