Wieczorowe Studia Licencjackie Wrocław, 05.12.2006
Wstęp do programowania
Wykład nr 10
(w oparciu o notatki K. Lorysia z modyfikacjami)
Wędrówka skoczka po szachownicy
Problem polega na znalezieniu takiego ciÄ…gu ruchów skoczka na szachownicy n×n, aby przechodziÅ‚ on dokÅ‚adnie
raz przez każde pole szachownicy jeden raz. Stosujemy następującą metodę:
- ustalamy porządek między ruchami skoczka startującymi ze wskazanego pola (x,y),
- startując z pola startowego, przechodzimy do kolejnych pól wybierając z każdego pola pierwszy ruch,
który jest dozwolony (nie powoduje kolizji ani wyjścia poza szachownicę),
- w przypadku braku możliwości wykonania kolejnego kroku z danego pola, rezygnujemy ze skoku na to
pole i cofamy się do najbliższego pola, z którego można wykonać jeszcze inny ruch niż wybrany
dotychczas;
- dla każdego odwiedzonego pola pamiętamy numer ostatnio wykonanego ruchu startującego z tego pola;
po powrocie na dane pole wybieramy następny numer dozwolonego ruchu;
- pomocnicza zmienna przechowuje informację o liczbie odwiedzonych pól  łatwo pozwala ustalić czy
znalez
liśmy rozwiązanie (tzn. czy odwiedziliśmy już wszystkie pola).
Opis funkcji:
init()
Nadaje tablicom sz i droga wartości początkowe:
- wartość sz[i][j]=-1 oznacza, że pole (i,j) nie zostało jeszcze odwiedzone; sz[i][j]=k dla k z
przedziału 0..7 oznacza, że pole (i,j) zostało odwiedzone i po odwiedzeniu tego pola wybrany został
ruch[k]
- (droga[k][0], droga[k][1]) opisuje k-tą pozycję w drodze, którą aktualnie analizujemy
int nast(int x, int y)
- wynikiem jest najmniejszy numer ruchu z pola (x,y) na pole dotychczas nieodwiedzone, ale
rozważane są tylko ruchy o numerach większych od sz[x][y]
druk()
- wypisuje drogÄ™ opisanÄ… w tablicy ruch
przesun(int x, int y, int k)
- wykonuje skok o numerze k, startujÄ…cy z pola (x,y); wymaga to odpowiedniej aktualizacji
tablic sz i droga; zmienna globalna r oznacza liczbę odwiedzonych dotychczas pól.
cofnij(int x, int y)
- cofnięcie o jeden krok, anulowanie ruchu, który ustawiał skoczka na pozycji (x,y)
main()
- pętla poszukująca rozwiązania kończy działanie gdy
o (r=nm-1) co oznacza, że wszystkie pola zostały odwiedzone
o (r<0) co oznacza, że nie udało się znalez
ć rozwiązania (wszystkie możliwości startujące z pola
startowego zostały sprawdzone)
#include
przesun(int x, int y, int k)
#define n 8
{ sz[x][y]=k;
#define m 8
X=x+ruch[k][0];
#define nm n*m
Y=y+ruch[k][1];
r++;
int sz[n][m], droga[nm][2];
droga[r][0]=X;
int ruch[8][2]={{2,1},
droga[r][1]=Y;
{1,2},
}
{-1,2},
{-2,1},
{-2,-1},
cofnij(int x, int y)
{-1,-2},
{ sz[x][y]=-1;
{1,-2},
droga[r][0]=droga[r][1]=-1;
{2,-1}};
r--;
int X,Y; /*aktualna pozycja skoczka */
if (r>=0){
int r; /* liczba wykonanych skokow */
X=droga[r][0];
Y=droga[r][1];
}
init()
}
{ int i,j;
for (i=0;idruk()
for (j=0;j{int i;
for (i=1; idroga[i][0]=droga[i][1]=-1;
for (i=0; i X=Y=droga[0][0]=droga[0][1]=0;
cout << droga[i][0] <<  , <<
r=0;
droga[i][1] << endl;
}
}
int nast(int x, int y)
main()
{int s,xz,yz;
{int k,u=0;
s=sz[x][y];
init();
s++;
k = nast(X,Y);
while (s<8)
przesun(X,Y,k);
{ xz=x+ruch[s][0]; yz=y+ruch[s][1];
while (r>=0 && rif (xz<0 || xz>=n || yz<0 ||
{ k=nast(X,Y);
yz>=m || sz[xz][yz]!=-1) s++;
if (k<8) przesun(X,Y,k);
else break;
else cofnij(X,Y);
}
}
return s;
if (r==nm-1) druk();
}
else cout <<  Nie ma drogi ;
}
Zliczanie liczby dróg skoczka
Teraz chcemy zliczyć liczbę różnych rozwiązań dla zadania wędrówki skoczka po szachownicy. Rozwiązanie
oprzemy na poprzednim programie, wprowadzimy następujące modyfikacje:
- po znalezieniu drogi skoczka nie kończymy przeszukiwania, a jedynie zwiększamy licznik
określający liczbę rozwiązań;
while (r>=0)
- aby po znalezieniu drogi kontynuować poszukiwanie kolejnych rozwiązań, cofamy skoczka na
przedostatnie pole (takie cofnięcie w poprzednim programie oznaczało dalsze próby poszukiwania
dróg kontynuujących drogę prowadzącą do przedostatniego pola)
-
if (r==nm-1){
cofnij(X,Y); ile++; }
W efekcie, możemy wykorzystać poprzedni program, zmieniając jedynie funkcję main():
main()
{int k,u,ile=0;
init();
k=nast(X,Y);
przesun(X,Y,k);
while (r>=0)
{ k=nast(X,Y);
if (k<8){
przesun(X,Y,k);
if (r==nm-1){
cofnij(X,Y); ile++; }
}
else cofnij(X,Y);
}
printf("\n Liczba mozliwych ustawien: %d \n",ile);
}
Szukanie wyjścia z labiryntu
Zadanie
Dany jest labirynt w postaci tablicy rozmiaru n×m, pola o wartoÅ›ci  1 to korytarze, pola o wartoÅ›ci  2 to mury.
Wejście do labiryntu znajduje się w polu (1,1) a wyjście w polu (n,m). Z pola (i,j) przejść można tylko
do pól, które mają z nim wspólne krawędzie, czyli (i-1,j), (i+1,j), (i,j-1) oraz (i,j+1). Należy:
- sprawdzić czy istnieje droga prowadząca od wejścia do wyjścia z labiryntu;
- jeśli taka droga istnieje, wyznaczyć taką drogę.
Metoda rozwiÄ…zania:
- ustalamy porządek między ruchami ze wskazanego pola (x,y) (ruchy te można opisać zmianą
współrzędnych (-1,0), (1,0), (0,-1), (0,1));
- stosujemy przeszukiwanie z nawrotami, analogiczne do metody stosowanej przy poszukiwaniu drogi
skoczka.
- w każdym polu, wartość  1 traktujemy jak pole wolne, wartość  2 jako mur a wartość i z zakresu [0,3]
jako pole odwiedzone, z którego wyszliśmy wykonując ruch i;
- UWAGA: nie rozważamy dróg, które więcej niż jeden raz odwiedzają jakieś pole (mimo, że takie mogą
istnieć), bo takie drogi zawsze można skrócić.
Poniżej przedstawiamy program realizujący powyższą metodę:
- Warunkiem określającym znalezienie rozwiązania jest teraz przejście na pole o współrzędnych (n,m)
- W stosunku do programu wyszukującego drogę skoczka szachowego, zastosowaliśmy następującą
modyfikacjÄ™:
o Pole labiryntu nie mieści się w obrębie współrzędnych od (0,0) do (n-1,m-1) lecz od (1,1) do
(n,m)
o Wokół labiryntu  postawiliśmy mur , co oznacza wypełnienie wartościami  2 pól o pierwszej
współrzędnej ze zbioru {0,n+1} i drugiej współrzędnej ze zbioru {0,m+1}. W konsekwencji
warunek sprawdzający czy przejście na nowe pole jest dozwolone zmieniło swoją postać z:
(xz<0 || xz>=n || yz<0 || yz>=m || sz[xz][yz]!=-1)
na
(sz[xz][yz]!=-1)
ponieważ wyjście za szachownicę oznacza napotkanie  wirtualnego muru
Na przykład, labirynt postaci
-1 -2 -1 -1
-1 -1 -1 -2
-1 -2 -1 -1
reprezentować będziemy jako
-2 -2 -2 -2 -2 -2
-2 -1 -2 -1 -1 -2
-2 -1 -1 -1 -2 -2
-2 -1 -2 -1 -1 -2
-2 -2 -2 -2 -2 -2
Kod programu wyszukującego wyjście z labiryntu:
#include
#define n 4
int przesun(int x, int y, int k)
#define m 4
{ sz[x][y]=k;
#define nm (n+2)*(m+2)
X=x+ruch[k][0];
Y=y+ruch[k][1];
int sz[n+2][m+2], droga[nm][2];
r++;
int ruch[4][2]={{1,0},
droga[r][0]=X;
{0,1},
droga[r][1]=Y;
{-1,0},
}
{0,-1}};
int X,Y; /* aktualna pozycja
poszukiwacza */
int cofnij(int x, int y)
int r; /* liczba wykonanych ruchow */
{ sz[x][y]=-1; //lub sz[x][y]=-2;
FILE *fi;
droga[r][0]=droga[r][1]=-1;
r--;
// Dane:
if (r>=0){
// -2 mur
X=droga[r][0];
// -1 wolne pole
Y=droga[r][1];
}
int init()
}
{ int i,j;
void druk()
fi=fopen("labirynt.txt","r");
{int i;
FILE *fi;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
fi=fopen("labirynt.out","w");
fscanf(fi, "%d", &sz[i][j]);
for (i=0; i for (i=0; i<=n+1; i++)
fprintf(fi,"%d, %d \n", droga[i][0],
{ sz[i][0]=-2; sz[i][m+1]=-2; }
droga[i][1]);
for (i=0; i<=m+1; i++)
fclose(fi);
{ sz[0][i]=-2; sz[n+1][i]=-2; }
printf("\n Droga znaleziona\n");
for (i=1; i}
droga[i][0]=droga[i][1]=-1;
X=Y=droga[0][0]=droga[0][1]=1;
r=0; main()
fclose(fi); {int i,j,k,u,ile=0;
init();
}
k = nast(X,Y);
przesun(X,Y,k);
int nast(int x, int y)
while ((X!=n || Y!=m) && r>=0)
{int s,xz,yz;
{ k=nast(X,Y);
//sz[x][y] zawiera -1 dla pola wolnego
if (k<4)
s=sz[x][y];
przesun(X,Y,k);
s++;
else cofnij(X,Y);
while (s<4)
}
{ xz=x+ruch[s][0]; yz=y+ruch[s][1];
if (X==n && Y==m) druk();
if (sz[xz][yz]!=-1) s++;
else cout <<  Brak wyjscia";
else break;
}
return s;
}
}
Koszt przeszukiwania z nawrotami
Załóżmy, że wykonujemy przeszukiwanie z nawrotami w  grze w której:
- wykonać można n ruchów,
- w każdym ruchu wybrać można jedną z k możliwości.
Wówczas, w najgorszym przypadku, sprawdzić musimy kn możliwości.
Oznacza to w szczególności:
- 8nÅ"n możliwoÅ›ci w przypadku drogi konika szachowego na szachownicy n×n;
- nn możliwoÅ›ci w przypadku rozstawienia hetmanów na szachownicy o rozmiarze n×n.
W praktyce, przeszukiwanie z nawrotami pozwala znacznie ograniczyć liczbę badanych możliwości, np.:
- w przypadku drogi konika szachowego, nie kontynuujemy przeszukiwania drogi kończącej się na polu,
z którego nie można przejść do nowego pola;
- podobnie w przypadku przeszukiwania labiryntu.
Niemniej, analiza pozwalająca oszacować uzyskane oszczędności jest trudna.
UWAGA!
W przypadku wielu problemów istnieją rozwiązania dużo szybsze od przeszukiwania z nawrotami lub
przeszukiwanie z nawrotami zawsze działa szybko (tak jest na przykład dla zdefiniowanego powyżej
przechodzenia labiryntu).
Jeszcze dwa słowa a rekurencji, czyli ... rekurencja ogonowa
Przypomnijmy, że z wykonywaniem funkcji rekurencyjnych wiążą się
następujące koszty:
- obciążenie pamięci stosu, gdzie zapamiętujemy kolejne wywołania rekurencyjne: odpowiada
głębokości drzewa wywołań rekurencyjnych;
- wywołania rekurencyjne, w szczególności powtarzające te same obliczenia: odpowiada liczbie
węzłów w drzewie wywołań rekurencyjnych.
Poniżej zamieszczamy dwa przykłady funkcji rekurencyjnych, z którymi nie wiąże się zwiększona (z powodu
rekurencji) ilość obliczeń. Rzeczywiście, drzewa wywołań mają postać ścieżek. Niemniej, duża jest głębokość
wyprowadzenia (rzędu n).
int potega(int a, int n)
{
if (n==0) return 1;
return a * potega(a, n-1);
}
int silnia(int n)
{
if (n==0) return 1;
return n * silnia(n-1);
}
Charakterystyczną cechą powyższych funkcji jest:
- w treści występuje tylko jedno wywołanie rekurencyjne;
- wywołanie rekurencyjne jest ostatnią instrukcją w treści funkcji.
Rekursję spełniającą te własności nazywamy rekurencją ogonową.
Wiele kompilatorów pozwala na translacją rekurencji ogonowej, która unika zajętości pamięci związanej z całą
kaskadą wywołań rekurencyjnych.