Vissza

Backtraking
  1. Helyezzünk el n királynőt egy nxn méretű sakktáblán úgy, hogy ne üssék egymást (ne legyenek ugyanabba a sorba, oszlopba, illetve átlón). ( Pszeudokód )
  2. Generáljuk ki az {1, 2, ... , n} halmaz:
    p-szeres Descartes-szorzatának elemeit
    pl. n=3, p=2: {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2),(3,3)}
    összes permutációit
    pl. n=3: {(1,2,3), (1,3,2),(2,1,3), (2,3,1), (3,1,2), (3,2,1)}
    p-ed rendű variációit
    pl. n=3, p=2: {(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)}
    p-ed rendű kombinációit
    pl. n=3, p=2: {(1,2), (1,3),  (2,3)}
    összes részhalmazát
    pl. n=3: { {}, {1}, {2}, {3}, {1,2}, {1,3},  {2,3}, {1,2,3}}
    összes partícióját
    pl. n=3:
    {1,2,3}
    {1,2}{3}
    {1,3}{2}
    {1}{2,3}
    {1}{2}{3}
  3. Adottak a1, a2, ... , an értékű pénzérmék, mindenik típusból bármennyi. Írjuk ki az összes lehetséges módot, ahogy egy s összeg kifizethető a pénzérmék segítségével.
Fel.1.
backtracking (x[], n, k)
  ha megoldas (x, n, k) akkor kiir (x, k-1) // ha k==n
  kulonben
     minden i = 0..n-1 végezd el
        // előállítjuk elő x[k]-ban az Ak halmaz i-edik elemét:
        x[k] = i
        ha megfelelo(x, k) akkor backtracking (x, n, k+1)
        vege ha
     vege minden
  vege ha

megfelelo(x[],k)
   minden i=0..k-1 végezd
   //ne legyenek ugyanabban az oszlopban és ugyanazon az átlón
   ha x[i] == x[k] vagy (k - i) == abs( x[k] - x[i]) akkor
     return HAMIS
   vege ha
   vege minden
  return IGAZ
vege megfelelo