1. óra - Ismétléses variáció
Elmélet > Algoritmusok > Kombinatorikai algoritmusok
Címkék > Óra

1. óra

(2008.09.16.)

Az idei első nagyobb gondolati egység: kombinatorikus algoritmusok. Variációk, kombinációk, permutációk, partíciók, fák, gráfok szerepelnek majd a feladatokban.

A Mester (D. E. Knuth) nyomán a következő kérdéseket fogjuk vizsgálni az egyes kombinatorikai objektumoknál:

Létezés: Van-e valamilyen feltételeknek megfelelő $X$ objektum?
Konstrukció: Ha van, hogyan lehet ilyet gyorsan találni?
Megszámlálás: Hány különböző ilyen $X$ létezik?
Generálás: Hogyan lehet az összes megfelelő $X_1, X_2, X_3, \ldots$ objektumot bejárni?
Optimalizáció: Melyik $X_i$-re lesz $f(X)$ maximális vagy minimális?

Ismétléses variációk

Első órán a legegyszerűbb esettel foglalkozunk: hogyan lehet előállítani az $n$ hosszúságú 0-1 sorozatokat. Egy iteratív és egy rekurzív megoldást adunk.

Számolás kettes számrendszerben

A 0-1 sorozatot egy kettes számrendszerbeli számnak fogjuk fel. A csupa nulla sorozatból indulunk, és mindig növeljük eggyel a "számot". A növelés úgy történik, hogy a legkisebb helyiértéken növelünk, majd végigkövetjük az esetleges átviteleket.

a[1..n] := 0
Ciklus 2^n-szer
    bejárás( a[ ] ) // az aktuális variációval megcsináljuk, ami a dolgunk

    i := 1                  // következő variáció generálása
    Ciklus
        c := (a[i] + 1) div 2       // átvitel
        a[i] := (a[i] + 1) mod 2    // növelés
        i := i + 1
    amíg c > 0
    Ciklus vége
Ciklus vége

Ha jobban megfigyeljük, mi történik kettes számrendszerben, az eggyel növeléskor, kaphatunk egy másik változatot: az eggyel növelés minden egyből nullát "csinál" az első nulláig, amit egyesre vált.

a[1..n] := 0
Ciklus
   bejár( a [ ] )
amíg (Növel())
Ciklus vége

Függvény Növel
   i := 1
   Ciklus amíg a[i] = 1 és i <= n
      a[i] := 0
      i := i + 1
   Ciklus vége
   Ha i <= n
   akkor
      a[i] = 1
      Növel := igaz
   különben
      Növel := hamis
   Elágazás vége
Függvény vége

Rekurzív felsorolás

Az első üres helyre beírunk 0-t és 1-et is, és mindkét esetben feltöltjük a többi üre helyet egy rekurzív hívással.

Eljárás rek(i)
    Ha i = 0 akkor bejár( a[ ] )
    különben
        a[i] := 0; rek(i-1)
        a[i] := 1; rek(i-1)
    Elágazás vége
Eljárás vége

A generálás a következő hívással kell indítani:

rek(n)

Feladat

Fej vagy írás?