Wykladnicze Dynamiki

Przydatne przy problemach

Operatory bitowe

• Przesunięcie w lewo - «, dopisuje na końcu liczby w zapisie binarnym zera, np. dla 9₁₀ = 1001₂, 9«4, czyli przesunięte o 4 miejsca równa się 10010000₂, czyli 9*16=144
• Przesunięcie w prawo - », usuwa ostanie cyfry (zera i jedynki) w zapisie binarnym, np. 144»4=9, bo 144₁₀ = 10010000₂, więc odcinając ostatnie 4 cyfry otrzymujemy 1001₂
• Iloczyn bitowy - &, sprawdza, czy w obu liczbach w zapisie binarnym występują na tych samych miejscach jedynki, np. c=a&b to liczba, składająca się z zer i jedynek, jednak jedynek, tylko tam, gdzie występowały one w liczbach a i b, np. gdy a=101011₂, a b=10101₂, to c=1₂
• Różnica bitowa - ^, zamienia jedynki na zera tam, gdzie jedynki występują w obu liczbach, w innych przypadkach przepisuje cyfry, np. gdy a=101011₂, a b=10101₂ to a^b=111110₂

Reprezentowanie podzbiorów

Gdy zbiór K ma n elementów, to liczba jego podzbiorów wynosi 2ⁿ. Każda liczba od 0 do 2ⁿ -1 będzie odpowiadała jakiemuś podzbiorowi, a liczba jej cyfr w zapisie binarnym będzie najwięcej wynosiła n. Każda taka cyfra będzie nam mówiła, czy dany element w rozpatrywanym podzbiorze występuje, np. 1001 w 2 mówi nam, że w tym podzbiorze występują tylko elementy 1 i 4. Jeśli nie ma jakichś cyfr z przodu, to elementy im odpowiadające w podzbiorze się nie znajdują.

---

Sprawdzanie, czy w grafie istnieje ścieżka Hamiltona

Jak wiemy ścieżka Hamiltona musi przejść przez wszystkie wierzchołki grafu dokładnie raz i może zaczynać się i kończyć w dowolnych. Uzyskanie takiej ścieżki jest możliwe tylko wtedy, gdy graf jest spójny.
Będziemy rozpatrywać podzbiory wierzchołków grafu, z tym, że wiemy, że wcześniej rozpatrzyliśmy ten sam podzbiór tylko bez jednego wybranego elementu. W podzbiorze istnieje ścieżka Hamiltona pomiędzy wierzchołkami p i q należacymi do tego podzbioru, gdy jest taka krawędź (p,k) należąca do grafu, że w rozpatrywanym podzbiorze bez p istnieje ścieżka Hamiltona pomiędzy k i q, gdzie ki q mogą być dowolne
Sprawdzanie zaczniemy od podzbioru wierzchołków S reprezentowanego przez 1 i tak aż do 2ⁿ -1, gdzie n to liczba wierzchołków grafu. Zauważmy, że na pewno rozpatrzyliśmy potrzebny nam podzbiór K, ponieważ będzie to podzbiór S bez jednego elementu, czyli liczba mu odpowiadająca będzie mniejsza od liczby odpowiadającej S, gdyż po prostu w zapisie binarnym nie będzie w pewnym miejscu jedynki w porównaniu do liczby S.

Algorytm:

 H[S][p][q] – tablica w której określamy, czy w podzbiorze S istnieje ścieżka Hamiltona prowadząca od wierzchołka p do q
 for i=1 to n H[{i}][i][i]=true;
 for S=1 to 2 do n-tej -1
    for p,q należących do podzbioru S
        for k=1 to n//sprawdzamy inne wierzchołki
            jeśli istnieje krawędź (p,k) należąca do grafu i k należy do podzbioru S oraz H[S-{p}][k][q]=true to H[S][p][q]=true
                //S-{p} to podzbiór S bez wierzchołka p

---

Wieże

Zaczniemy od rozpatrywania mniejszych podproblemów, czyli mniejszych szachownic, przy czym kolumny tych szachownic nie muszą się ze sobą stykać. Szachownice te będą się składały z k kolumn o wysokości k – wtedy możemy na nich ustawić k wież, tak, by się nie szachowały.
Gdy chcemy ułożyć wieżę z kolumny i na k-tym miejscu możemy to zrobić wtedy, gdy miejsce to nie jest dziurawe oraz, gdy wieża należy do aktualnie rozpatrywanego podzbioru. Liczba ułożeń wież tego podzbioru będzie równa temu, co już wcześniej wyliczyliśmy plus liczbie ułożeń podzbioru bez wieży z kolumny i, bo tyle wynosi liczba ułożeń rozpatrywanego podzbioru, gdy wieża z kolumny i stale zajmuje k-ty wiersz. Tę wieżę możemy tam spokojnie umieścić, gdyż podzbiór bez wieży z kolumny i ma k-1 elementów, czyli był rozpatrywany do k-1 wiersza.

Przykładowa plansza, szukamy liczby ułożeń na szachownicy złożonej z kolumn 1,2,3 i 5.
Na pole niebieskie próbujemy wstawić wieżę, zielone to pola wcześniej rozważone.

Algorytm:

n – liczba wież
P[S] – liczba ułożeń wież dla podzbioru S
A[i][j] – mówi nam, czy w i-tym wierszu na j-tym miejscu można stanąć, czy nie, A[i][j]=true, gdy można tam stanąć
P[0]=1 //by można było dla podzbiorów jednoelementowych łatwo nadać wartość 1, jeśli dana wieża może stanąć w pierwszym wierszu
for S=1 to 2 do n-tej -1
    P[S]=0 //na razie jeszcze nic nie obliczyliśmy
    k=|S| //k to liczność zbioru S, w praktyce możemy sprawdzić ilość jedynek w zapisie binarnym liczby S
    for i=1 to n
        jeśli i należy do S i A[k][i]=true to P[S]=P[S]+P[S-{i}]

Oczywiście wynikiem dla całej szachownicy jest P[2ⁿ -1], gdyż 2ⁿ -1 reprezentuje całą szachwonicę.