Opole, dn. 31 marca 2004

Laboratorium Algorytmów i Struktur Danych

Temat:

Analiza algorytmu wyszukiwania „ścieżek”

Autor: Dawid Najgiebauer

Informatyka, sem. II, grupa lab. 11

Prowadzący: dr inż. Jan Sadecki

1. Temat

Napisz program, który sprawdzi, czy jest możliwe przejście wszystkich krawędzi i przekątnych ścian sześcianu w taki sposób, aby na żadnej z nich nie przebywać dwa razy.

2. Analiza, projektowanie

Celem badania jest wykonanie algorytmu sprawdzania, czy możliwe jest „chodzenie” po sześcianie zgodnie z warunkami zadania.

Na potrzeby algorytmu zostanie stworzony wirtualny sześcian - tablica dwuwymiarowa (mapa) reprezentująca możliwe „ścieżki”. Tablica będzie miała rozmiar 8x8 (a więc liczba wierzchołków); każdej parze odpowiadać będzie ścieżka. Celem ułatwienia pracy algorytmu ścieżka przykładowo 1-2 odpowiada i jest równoznaczna ścieżce 2-1, a więc informacje będą powielone. Tablica będzie zawierać liczby, które reprezentować będą odpowiednio: 0 - brak połączenia; 1 - połączenie istnieje i nie było wykorzystane; 2 - połączenie istnieje i było wykorzystane.

1. Implementacja algorytmu

void szukaj(int stp)

{

if (sprawdz()) exit(1);

for(int i=0;i<8;i++)

{

if (mapa[stp][i]==1)

{

mapa[stp][i]=2;

mapa[i][stp]=2;

szukaj(i);

mapa[stp][i]=1;

mapa[i][stp]=1;

}

}

}

3. Wyniki i wnioski z badania

Dzięki zastosowaniu rekurencji w łatwy sposób możliwe było uzyskanie wypisywania liczby w postaci binarnej, gdzie pierwszą cyfrę tej liczby poznajemy dopiero przy ostatnim dzieleniu, drugą - przy przedostatnim itd.

4 Dawid Najgiebauer

Temat 5

Temat 3

STOP

Jest

Nie ma

I++

mapa[stp][I]=2

mapa[I][stp]=2

szukaj(I)

mapa[stp][I]=2

mapa[I][stp]=2

T

N

mapa[stp][I]==1

N

I<8

I=0

N

T

czy wszystkie wykorzystano?

szukaj(stp)

---