navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha4-2013 [2013/10/11 14:59] petvana |
courses:a4m33pal:uloha4-2013 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 27: | Řádek 27: | ||
| Uzly jsou vkládány postupně v jasném pořadí, a proto můžeme dopředu jednoznačně rozhodnout, které hodnoty budou ve kterém stromu. Neboli prvních 16 hodnot bude uloženo v binomiálním stromu hloubky 4, dalších 8 hodnotu bude uložena ve stromu hloubky 4 a poslední do stromu hloubky 0. (Kdo mi nevěří, že to tak dopadne, ať si algoritmus vkládání podrobně projde) 8-) | Uzly jsou vkládány postupně v jasném pořadí, a proto můžeme dopředu jednoznačně rozhodnout, které hodnoty budou ve kterém stromu. Neboli prvních 16 hodnot bude uloženo v binomiálním stromu hloubky 4, dalších 8 hodnotu bude uložena ve stromu hloubky 4 a poslední do stromu hloubky 0. (Kdo mi nevěří, že to tak dopadne, ať si algoritmus vkládání podrobně projde) 8-) | ||
| - | Máme tedy tři stromy obsahující v příkladu 2: { 0 2 4 1 3 | 5 7 9 6 8 | 10 12 14 11 13 | 15 }; { 17 19 16 18 | 20 22 24 21 }; { 23 }. | + | Máme tedy tři stromy obsahující v příkladu 2: { **0** 2 4 1 3 | 5 7 9 6 8 | 10 12 14 11 13 | **15** }; { 17 19 **16** 18 | 20 22 **24** 21 }; { **23** }. |
| Za úkol máme vypočítat hodnotu (MAX(B(i)) - ROOT(B(i))) pro každý strom B(i). Kořen binomiálního stromu obsahuje vždy nejmenší hodnotu, a proto je to stejné jako (MAX(B(i)) - MIN(B(i))). Nepotřebujeme tedy vůbec znát strukturu binomiálních stromů, ale tato hodnota lze vypočítat pouze ze seznamu uzlů jednotlivých stromů z předchozího kroku. | Za úkol máme vypočítat hodnotu (MAX(B(i)) - ROOT(B(i))) pro každý strom B(i). Kořen binomiálního stromu obsahuje vždy nejmenší hodnotu, a proto je to stejné jako (MAX(B(i)) - MIN(B(i))). Nepotřebujeme tedy vůbec znát strukturu binomiálních stromů, ale tato hodnota lze vypočítat pouze ze seznamu uzlů jednotlivých stromů z předchozího kroku. | ||
| + | |||
| + | DIFF(BH) = MAX(B(4)) - MIN(B(4)) + MAX(B(3)) - MIN(B(3)) + MAX(B(0)) - MIN(B(0)) = 15 - 0 + 24 - 16 + 23 - 23 = **23** | ||
| ^ Není tedy potřeba vytvořit žádnou binomiální haldu, je to absolutně zbytečné! ^ | ^ Není tedy potřeba vytvořit žádnou binomiální haldu, je to absolutně zbytečné! ^ | ||
| + | |||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
| + | |||
| + | |||
| + | ---- | ||
| + | By stradja3: mám pocit, že jsem to maximálně optimalizoval a přesto mi to nestíhá "test05" - nemáte nějaký obecný trik jak to zrychlit? Na všechno používám obyčejná pole, co se týče složitosti, tak to mám: (počet_permutací)*(3*M+N) | ||
| + | |||
| + | By Rozion: muzete nekdo poradit jak generovat permutace mezi 1. a 2. permutaci? | ||
