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:19]
petvana
+++ courses:a4m33pal:uloha4-2013 [2025/01/03 18:28] (aktuální)
@@ Řádek 1: / Řádek 1: @@
+====== Zadání - Building Binomial Heaps ======
+https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=binomialheaps2
+====== Řešení - Building Binomial Heaps ======
 Úloha je především o dvou tématech, a to permutacích a binomiálních stromech. Nejprve je potřeba udělat si pořádek v pochopení permutací. Vstup dostanete jeko dvě permutace, které zároveň definují interval prohledávaných permutací. Je tedy potřeba naprogramovat funkci, která bude schopná iterovat od první permutace do té poslední. Example 1:
@@ Řádek 15: / Řádek 21: @@
 VAL(EP(π, N)) = { 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 }
-...
+Dále je potřeba vytvořit binomiální haldu z rozšířené permutace. **Binomiální halda** je seznam binomiálních stromů hloubky N. Každý strom má 2^N uzlů a binomiální halda neopsahuje dva stromy se stejnou hloubkou. Které stromy budou zastoupeny se dá jednoduše rozhodnout z binárního zápisu celkového poštu uzlů. Příklad:
+N = 25 >> 0b11001 >> halda budo obsahovat stromy hloubek { 0, 3, 4 } >> N = 2^0 + 2^3 + 2^4 = 1 + 8 + 16 = 25
+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** }.
+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é!  ^
 ~~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?

courses/a4m33pal/uloha4-2013.1381493979.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru