https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=binomialheaps2

Ú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:

Zajímavé je že hodnota π není potřeba počítat. Bylo by to také dost nepraktické, protože může být dost velká (teoreticky až 100!) .

Nyní co je to extended permutation? Není to nic jiného než že dáte původní permutaci (N/M)-krát za sebe a ke každé další sérii přičtete M. Uvedu příklad rozšířené permutace na Example 2:

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)

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

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?