Metody - algorytmy rekurencyjne i
biblioteka metod

Przegląd zagadnień

W rozdziale tym oprócz przedstawienia pojęcia rekurencji i sposobu tworzenia
biblioteki metod, zostaną pokazane metody konstruowania algorytmów, za
pomocą których można rozwiązać rozmaite problemy. Jeden ze sposobów
budowania algorytmów został zaprezentowany i nazwany w laboratorium do
rozdziału ósmego. Był to tzw. algorytm zachłanny (greedy algorithm).
Algorytm ten podejmuje działanie, które wydaje się w danej chwili najlepsze,
nie uwzględniając, czy podjęte kroki nie prowadzą w ślepą uliczkę, czy
uzyskamy satysfakcjonujący wynik końcowy.

Po skończeniu tego rozdziału studenci powinni potrafić:



Definiować pojęcie rekurencji.



Rozpoznawać problemy, gdzie można zastosować rekurencję



Tworzyć bibliotekę metod.

Pojęcie rekurencji

Przez rekurencję lub inaczej rekursję (recursion), w tym rozdziale, będziemy
rozumieć zdolność funkcji (metody) do wywołania samej siebie. Tak naprawdę
pojęcie rekurencji nie odnosi się tylko do konstruowania metod.
Rekurencyjnym może być dowolny przedmiot - rzecz, jeżeli częściowo składa
się z siebie samego. Pewne rekurencyjne struktury danych zostaną
przedstawione w rozdziale dwunastym i trzynastym.

Metodę nazywamy bezpośrednio rekurencyjną, jeżeli jej definicja zawiera
odwołanie do samej siebie. Metodę nazywamy pośrednio rekurencyjną, jeżeli
zawiera odwołanie do metody, która ją wywołuje bezpośrednio lub pośrednio,
czyli przez łańcuch wywołań.

Metody rekurencyjne używane są często do algorytmów opartych na strategii
"dziel i zwyciężaj". Polega ona na rozwiązaniu zadania, przez podzielenie go na
mniejsze części o tej samej postaci co zadanie pierwotne. Następnie podzadania
dzielimy w ten sam sposób na coraz mniejsze, aż ich rozmiar stanie się
wystarczająco mały, aby rozwiązanie wydało się oczywiste lub można było go
łatwo rozwiązać przy pomocy innej metody. Po znalezieniu rozwiązań zadań
cząstkowych, konieczne jest nieraz ich scalenie, aby uzyskać rozwiązanie
całego zadania. Według strategii "dziel i zwyciężaj" działa algorytm
wyszukiwania binarnego (połówkowego), które było tematem laboratorium w
rozdziale siódmym, chociaż nie zastosowano tam rekurencji. Niektóre
algorytmy oparte na strategii "dziel i zwyciężaj" można łatwo rozwiązać bez
konieczności używania metod rekurencyjnych. Opierają one się na użyciu
instrukcji pętli i nazywamy je rozwiązaniami iteracyjnymi.

W celu demonstracji strategii "dziel i zwyciężaj" rozważmy zadanie obliczenia
silni. Jak już wspominano wcześniej w tym kursie, silnię dla liczby n całkowitej

nieujemnej oznaczamy znakiem wykrzyknika i określamy następującym
wzorem:

Metoda iteracyjna obliczająca silnię może być zaimplementowana w
następujący sposób:

static ulong Silnia(ushort n)
{

ulong iloczyn = 1;

for(uint i=2;i<=n;i++)

iloczyn *= i;

return iloczyn;

}

Silnie możemy zdefiniować również rekurencyjnie:

Stosując powyższy wzór otrzymujemy następującą metodę rekurencyjną

static ulong Silnia(ushort n){

if(n == 0 || n == 1)

return 1;

return n * Silnia(n-1);

}

Między metodami rekurencyjnymi a instrukcjami iteracyjnymi istnieje pewne
podobieństwo. Dla wywołań rekurencyjnych występuje też zagrożenie
wykonywania nieskończonych obliczeń. Konieczne jest więc zapewnienie, że w
pewnym momencie wywołania rekurencyjne się kończą i metoda zwraca
wynik, czyli rozważenia tzw. problemu stopu.















,...

3

,

2

,

1

*

)

1

(

*

...

*

2

*

1

0

1

!

n

dla

n

n

n

dla

n















,...

3

,

2

,

1

)!

1

(

*

0

1

!

n

dla

n

n

n

dla

n

Przykład - Wieże Hanoi

Przykładem użycia strategii "dziel i zwyciężaj" w połączeniu z wywołaniem
rekurencyjnym jest algorytm rozwiązujący starożytną łamigłówkę, pochodzącą
z Tybetu, znaną jako Wieże Hanoi. Treść tej łamigłówki jest następująca.
Mamy trzy pręty i n krążków o różnych średnicach, które są nanizane są na
pierwszy pręt w porządku malejących średnic tworząc wieżę. Chcemy
przenieść krążki z pierwszego pręta na drugi, przy pomocy pręta trzeciego
stosując następujące zasady:



w każdym kroku można przenieść dokładnie jeden krążek



krążek nie może być nigdy nałożony na krążek o mniejszej średnicy

Nazwijmy odpowiedni pręt pierwszy jako źródło, pręt drugi jako cel, pręt trzeci
jako tmp. Rozwiązanie jest trywialne, gdy na pręcie źródło jest nanizany tylko
jeden krążek. Przenosimy wtedy krążek z pręta źródło na pręt cel. W przypadku
gdy na pręcie źródło jest nanizanych więcej krążków, należy najpierw przenieś
n-1 krążków na pręt tmp, przy pomocy pręta cel, gdzie n jest liczbą krążków.
Po wykonaniu tego zadania na pręcie źródło zostaje jeden krążek, który
przenosimy na pręt cel. Następnie przenosimy n-1 krążków z pręta tmp, na pręt
cel przy pomocy pręta źródło. Oczywiście nasuwa się pytanie jak przenieść te
n-1 krążków. Postępujemy w sposób identyczny jak w przypadku n krążków, to
znaczy, jeżeli n-1 jest równe jeden, to przenosimy dany krążek na odpowiedni
pręt. W przypadku gdy n-1 jest większe od jeden, to najpierw przenosimy n-2
krążków, z pręta który pełni rolę źródła na pręt pełniący rolę pręta
pomocniczego. Zostaje wtedy nam jeden krążek do przeniesienia, co jest
zadaniem trywialnym. Następnie przenosimy n-2 krążków z pręta pełniącego
rolę pomocniczą na pręt pełniący w danym kroku rolę źródła.

Implementację tego algorytmu można znaleźć w programie WizeHanoi, który
stanowi część rozwiązania Kurs\Demo\Modul10\Modul10.sln, gdzie
Kurs jest katalogiem, gdzie skopiowano pliki kursu.

Nadużywanie rekurencji

Użycie rekurencji niesie z sobą niestety dodatkowe koszty. Są nimi
spowolnienie wykonywania programu (wywołanie funkcji wymaga
dodatkowych kroków) oraz zwiększa objętość danych przechowywanych na
stosie programu. Argumentem uzasadniającym użycie metod rekurencyjnych
jest czytelność algorytmów zbudowanych z ich użyciem. Podsumowując,
unikajmy rekurencji, jeżeli istnieje oczywiste rozwiązanie iteracyjne.

Rekurencja niestety ma jeszcze jedną wadę, wynikającą ze strategii "dziel i
zwyciężaj". Dzieląc zadanie na podzadania, można doprowadzić, że część
podzadań będzie identycznych i duża część obliczeń będzie powtórnie
rozwiązywała już rozwiązane problemy. W celu demonstracji tego problemu
rozważmy tzw. liczby Fibonacciego (liczby Fibonacciego rzędu 1). Liczby
Fibonacciego są definiowane w następujący sposób:

Bezpośrednie skorzystanie z tego wzoru prowadzi do metody:

static ulong Fib(ushort n)
{

if(n<2)

return n;

return Fib(n-1)+Fib(n-2);

}



















2

)

2

(

)

1

(

2

)

(

n

dla

n

Fib

n

Fib

n

dla

n

n

Fib

Załóżmy, że chcemy obliczyć Fib(5). W tym celu musimy obliczyć Fib(4) i
Fib(3), ale aby obliczyć Fib(4) również liczymy Fib(3)). Drzewo wywołań dla
Fib(5), z zaznaczeniem tym samym kolorem wywołać metody dla tych samych
argumentów zostało przedstawione na slajdzie.

Metodę obliczającą liczby Fibonacciego, zarówno wersję rekurencyjną jak i
iteracyjną, można znaleźć w programie Fibonacci, który stanowi część
rozwiązania Kurs\Demo\Modul10\Modul10.sln, gdzie Kurs jest
katalogiem, gdzie skopiowano pliki kursu.

W celu uniknięcia powtórnych obliczeń, kiedy podzadanie mogą zawierać te
same podzadania, zamiast strategii "dziel i zwyciężaj" stosuje się
programowanie dynamiczne. W algorytmach opartych o programowanie
dynamiczne każde zadanie (problem) rozwiązuje się raz, a następnie jego
rezultat zapisuje się w pewnej tablicy, unikając dzięki temu powtórnego
rozwiązywania tego samego zadania.

Algorytmy z powrotami

Z metodami rekurencyjnymi jest związana pewna grupa algorytmów zwanych
"algorytmami z powrotami" (backtracking algorithms). Przy rozwiązywaniu
niektórych problemów, możemy podjąć różne kroki w bieżącej sytuacji. Jeżeli
wybrany krok (decyzja), nie prowadzi do rozwiązanie, musimy mieć możliwość
powrotu do miejsca (stanu programu), gdzie możliwe było dokonanie innego
wyboru i sprawdzenie innej drogi. Ogólny schemat algorytmów z powrotami
przedstawiony jest na slajdzie. Spróbujemy go zastosować do problemu
zwanego znalezieniem drogi skoczka szachowego. Problem polega na obejściu
szachownicy w taki sposób, że każde pole będzie dokładnie raz odwiedzone, Po
szachownicy można poruszać zgodnie z regułami ruchu skoczka szachowego.

3

2

8

1

5

4

7

6

Rys. Możliwe do wykonania ruchy skoczka

Rozwiązanie problemu znalezienia drogi skoczka szachowego znajduje się w
programie DrogaSkoczka, który stanowi część rozwiązania
Kurs\Demo\Modul10\Modul10.sln, gdzie Kurs jest katalogiem,
gdzie skopiowano pliki kursu.

W wymienionym programie dopuszczalne ruchy skoczka zawarte są w tablicy
mozliweRuchySkoczka. Po obliczeniu pozycji skoczka po wykonaniu
danego ruchu, następuje sprawdzenie czy pozycja jest prawidłowa, czyli czy nie
"skoczyliśmy" poza szachownicę. Jeżeli pozycja jest prawidłowa to sprawdzane
jest, czy czasem pole już nie było odwiedzone. Informacja o tym czy pole było
odwiedzone czy nie, przechowywane jest w tablicy odwiedzonePola.
Tablica zawiera tyle elementów ile jest pól na szachownicy. Element tablicy
odwiedzonePola[0,0] odpowiada polu a1, element
odwiedzonePola[0,1] odpowiada polu a2, element
odwiedzonePola[1,0] odpowiada polu b1 itd. Element tablicy
zawierający wartość zero oznacza, że odpowiadające mu pole nie było jeszcze
odwiedzone. Wartość elementu tablicy różna od zera oznacz numer ruchu, w
którym dane pole było odwiedzone. Jeżeli pole nie było odwiedzone,
ustawiamy wartość odpowiedniego elementu tablicy odwiedzonePola, na
numer aktualnego ruchu. Potem sprawdzamy czy cel został osiągnięty, czyli
czy pole na które "skoczyliśmy" jest ostatnim polem na szachownicy do
odwiedzenia. Osiągnięcie celu komunikujemy przez przekazanie do metody
wywołującej wartości true.. Gdy cel jeszcze nie został osiągnięty,
sprawdzamy czy z bieżącej pozycji jest możliwe osiągnięcie celu, przez
rekurencyjne wywołanie metody Sprawdz. Osiągnięcie celu jest oznajmiane
przez przekazanie przez metodę Sprawdz wartości true.. Jeżeli metoda
Sprawdz zwróci wartość false, oznacza że z bieżącego stanu nie ma drogi
prowadzącej do celu. Cofamy więc ruch i przechodzimy do następnego
możliwego ruchu. Jeżeli nie ma już więcej możliwych ruchów, oznacza to, że
dotychczasowe ruchy skoczka nie prowadzą do celu, musimy się więc cofnąć -
wychodzimy z metody przekazując wartość false.

Demo: utworzenie biblioteki funkcji

Pewne metody mogą być używane w wielu programach. Możemy w tym celu
utworzyć podzespół w postaci biblioteki dll i dołączyć ją do programu
głównego. Biblioteka może być dołączana niezależnie do wielu programów.

W celu zademonstrowania tworzenia biblioteki funkcji napisz bibliotekę
obliczającą pola powierzchni różnych figur. Gotowy program jest dostępny w
katalogu Kurs\Demo\Modul2\Modul2.sln projekty Biblioteka i
TestBiblioteki, gdzie Kurs jest katalogiem gdzie skopiowano pliki
kursu

1. Uruchom Visual Studio.

Naciśnij przycisk Start systemu Windows, wybierz Wszystkie Programy
następnie Microsoft Visual Studio 2005/ Microsoft Visual Studio 2005.

2. Utwórz nowy projekt

a. Z menu File wybierz New/Project...

b. W oknie dialogowym New Project określ następujące właściwości:

i. typu projektu: Visual C#/Windows

ii. szablon: Class Library

iii. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\

iv. nazwa projektu: Biblioteka.

v. nazwa rozwiązania: Demo10

3. Zmień nazwę klasy z Class1 na Pole.

a. Zwróć uwagę, że jeżeli chcemy, aby metody tej klasy były

dostępne dla innych programów (podzespołów), przed nazwą
klasy musi pojawić się słowo public.

4. Zmień nazwę pliku Class1.cs na Pole.cs.

a. W oknie Solution Explorer z menu kontekstowego związanego z

elementem reprezentującym plik Class1.cs wybierz Rename.

b. Zmień tekst Pole.cs na Pole.cs

5. Dodaj do klasy Pole:

a. Metodę Kwadrat zwracającej pole kwadratu i przyjmującą jako

argument długość jego boku.

b. Metodę Kolo zwracającej pole koła i przyjmującą jako argument

długość jego promienia.

public class Pole

{

public static double Kwadrat(double a)

{

return a * a;

}

public static double Kolo(double r)

{

return Math.PI * r * r;

}

}

Przypomnij, że definicja metody, które mają być wywołane z metod
należących do innych klas, musi się rozpoczynać od słowa public.

6. Skompiluj program.

7. Dodaj do bieżącego rozwiązania nowy projekt Nowy program będzie

korzystał z metod zawartych w programie Biblioteka.

a. Z menu File wybierz Add/New Project...

b. W oknie dialogowym Add New Project określ następujące właściwości:

i. typu projektu: Visual C#/Windows

ii. szablon: Console Application

iii. nazwa projektu: TestBiblioteki.

8. Uczyń nowo utworzony projekt projektem startowym

a. Zaznacz projekt TestBiblioteki w okienku Solution Explorer i z menu

kontekstowego wybierz Set as StartUp Project.

9. Podłącz do programu TestBiblioteki, podzespół Biblioteka.

a. W okienku Solution Explorer, z menu kontekstowego związanego z

elementem reprezentującym projekt TestBiblioteki wybierz Add
Reference...

b. W okienku Add Reference przejdź do zakładki Projects, zaznacz

projekt Biblioteka i naciśnij OK.

10. W okienku Solution Explorer, rozwiń folder References znajdujący się w

projekcie TestBiblioteki. Pokaż, że znajduje się w nim odwołanie do
podzespołu Biblioteka.

11. Pokaż, że można skorzystać z metod zdefiniowanych w podzespole

Biblioteka w programie TestBiblioteki.

a. Do metody Main dodaj następujący kod:

Console.Write("Podaj długość boku kwadratu: ");
double bok =

Convert.ToDouble(Console.ReadLine());

Console.WriteLine("Pole kwadratu wynosi {0}.",

Biblioteka.Pole.Kwadrat(bok));

b. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka.

W tym celu u góry pliku Program.cs dodaj następującą linijkę

using Biblioteka;

c. W dalszej części metody Main dodaj następujący kod:

Console.Write("\nPodaj długość promienia: ");
double promien =

Convert.ToDouble(Console.ReadLine());

Console.WriteLine("Pole koła wynosi {0}.",

Pole.Kolo(promien));

Console.ReadKey();

12. Skompiluj i uruchom program.

Pytania sprawdzające

1. Co to jest rekurencja?

Odp.
Rekurencja jest to zdolność funkcji (metody) do wywołania samej siebie lub
bardziej ogólnie, definicja pojęcia (obiektu) w której wykorzystuje się
definiowane pojęcie.

2. Na czym polega strategia "dziel i rządź"?

Odp.
Strategia "dziel i rządź" projektowania algorytmu, polega rozwiązaniu
zadania, przez podzielenie go na mniejsze części o tej samej postaci co
zadanie pierwotne. Następnie podzadania dzielimy w ten sam sposób na
coraz mniejsze, aż ich rozmiar stanie się wystarczająco mały, aby
rozwiązanie wydało się oczywiste lub można było go łatwo rozwiązać przy
pomocy innej metody. Po znalezieniu rozwiązań zadań cząstkowych,
konieczne jest nieraz ich scalenie, aby uzyskać rozwiązanie całego zadania.

3. Na czym polega programowanie dynamiczne?

Odp.
W algorytmach opartych o programowanie dynamiczne każde zadanie
(problem) rozwiązuje się raz, a następnie jego rezultat zapisuje się w pewnej
tablicy, unikając dzięki temu powtórnego rozwiązywania tego samego
zadania.

Laboratorium

Ćwiczenie 1:
Napisz bibliotekę dll, która zawiera metodę sortującą tablicę liczb całkowitych.
Sortowanie ma się ma odbywać algorytmem zwanym sortowaniem szybkim
(quick sort). W sortowaniu szybkim wybieramy pewną wartość x, która dzieli
nam tablicę na dwie części a[0], a[1]...a[q] oraz a[q+1]...a[n-1] i jest spełniony
warunek:

Następnie każdą z podtablic dzielimy na dwie części w podobny sposób, jak
poprzednio z tym, że dobieramy inny wartości x dzielącej podtablice. Dzielenie
kończymy, gdy podtablica zwiera tylko jednakowe wartości. Algorytm
sortowanie szybkie jest przykładem strategii "dziel i rządź".

Schemat blokowy metody sortowania szybkiego znajduje się w pliku
Kurs\Lab\Modul10\Start\QuickSort.gif, gdzie Kurs jest
katalogiem gdzie skopiowano pliki kursu.

1. Uruchom Visual Studio

Naciśnij przycisk Start systemu Windows, wybierz Wszystkie Programy
następnie Microsoft Visual Studio 2005/ Microsoft Visual Studio 2005.

2. Utwórz nowy projekt

a. Z menu File wybierz New/Project...

b. W oknie dialogowym New Project określ następujące właściwości:

i. typu projektu: Visual C#/Windows

q

j

dla

x

j

a

q

i

dla

x

i

a









]

[

]

[

ii. szablon: Class Library

iii. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\

iv. nazwa projektu: QuickSort.

v. nazwa rozwiązania: Lab10

3. Zmień nazwę klasy z Class1 na QuickSort.

4. Zmień nazwę pliku Class1.cs na QuickSort.cs.

5. Dodaj do klasy QuickSort metodę Sortuj. Schemat działania metody

jest umieszczony w pliku QuickSort.gif.

public static void Sortuj(int[] tab,int lewy,int

prawy)

{
int i= lewy,j= prawy;
int x,tmp;
x = tab[(lewy + prawy)/2];
while(i<=j)
{
while(tab[i] < x)
i++;
while(x < tab[j])
j--;
if(i <= j)
{
tmp = tab[i];
tab[i] = tab[j];
tab[j] = tmp;
i++; j--;
}
else break;
}
if(lewy < j) Sortuj(tab, lewy,j);
if(i < prawy) Sortuj(tab,i, prawy);
}

6. Dodaj do klasy QuickSort metodę Sortuj. W odróżnieniu od

poprzedniej metody, ta przyjmuje tylko jeden argument - tablicę do
posortowania. Wewnątrz metody wywołaj poprzednio zdefiniowaną
metodę Sortuj z odpowiednimi parametrami.

public static void Sortuj(int[] tab)
{
Sortuj(tab, 0, tab.Length - 1);
}

7. Do rozwiązania dodaj nowy projekt, który przetestuje napisaną metodę

sortującą

a. Z menu File wybierz Add/New Project...

b. W oknie dialogowym Add New Project określ następujące

właściwości:

i. typu projektu: Visual C#/Windows

ii. szablon: Console Application

iii. nazwa projektu: TestSortowania.

c. Uczyń nowo utworzony projekt projektem startowym

d. Podłącz do programu TestSortowania, podzespół Sortowanie.

i. W okienku Solution Explorer, z menu kontekstowego

związanego z elementem reprezentującym projekt
TestSortowania wybierz Add Reference...

ii. W okienku Add Reference przejdź do zakładki Projects, zaznacz

projekt Sortowanie i naciśnij OK.

e. Zaznacz, że będziemy korzystać z przestrzeni nazw Sortowanie.

using Sortowanie;

f. Do metody Main dodaj kod testujący metodę Sortuj:

static void Main(string[] args)
{
int[] liczby = new int[10];
Random r = new Random();
Console.WriteLine("Tablica przed

¬sortowaniem:");

for (int i = 0; i < liczby.Length; i++)
{
liczby[i] = r.Next(0, 1001);
Console.Write("{0}, ", liczby[i]);
}
QuickSort.Sortuj(liczby);

Console.WriteLine("\n\nTablica po

¬sortowaniu:");

foreach(int i in liczby)
Console.Write("{0}, ", i);

Console.ReadKey();
}

8. Skompiluj i uruchom program.

Ćwiczenie 2:
Napisz program rozwiązujący problem ośmiu hetmanów. Problem ośmiu
hetmanów polega na umieszczeniu na szachownicy ośmiu hetmanów tak, aby
żaden nie był na drodze ruchu innego hetmana, czyli nie był pod biciem.
Hetman może poruszać się po polach kolumny, wiersza lub przekątnych do
których należy pole, na którym znajduje się hetman, co ilustruje poniższy
rysunek.:

Rys. Możliwe do wykonania ruchy hetmana.

Przy pisaniu programu skorzystaj ze schematu przedstawionego na slajdzie
"Algorytmy z powrotami", programu droga skoczka oraz następujących
wskazówek:



Metoda Sprawdz przyjmuje jako argument numer kolumny, na której
chcemy ustawić hetmana. Ustawiamy hetmana najpierw w pierwszej
kolumnie, w miejscu wybranym przez użytkownika, następnie
przechodzimy do następnej kolumny.
W następnych kolumnach, próbujemy ustawić hetmana na polu tej
kolumny, rozpoczynając od wiersz pierwszego. Jeżeli istnieje pole,
które jest nieatakowane przez pozostałych hetmanów, zaznaczamy je i
przechodzimy do następnej kolumny wywołując ponownie metodę
Sprawdz. Jeżeli metoda Sprawdz przekazała wartość true,
oznacza to że problem został rozwiązany. W przeciwnym wypadku
sprawdzamy następne wiersze, wcześniej odznaczając poprzednie pole
jako nieatakowane. Jeżeli żaden wiersz nie daje oczekiwanego
rezultatu, wychodzimy z metody (cofamy się) zwracając wartość
false..



W celu sprawdzenia czy pole jest nieatakowane skorzystaj z
pomocniczych tablic:

o Tablicy boolowskiej Wiersze, o liczbie pól równej liczbie

wierszy, element Wiersze [0] odpowiada wierszowi
pierwszemu, itd. Wartość false elementu oznacza, że
odpowiadający mu wiersz jest wolny, wartość true, że
wiersz jest zajęty

o

Dwóch tablic boolowskich dla przekątnych. Jedna tablica
będzie zawierać informacje o przekątnych biegnących z góry
na dół, druga o przekątnych z dołu do góry. Każdy element

tablicy odpowiada pojedynczej przekątnej. Podobnie jak
poprzednio, wartość false elementu oznacza, że
odpowiadająca mu przekątna jest wolna, wartość true, że
przekątna jest zajęta. Zauważ, że dla pól należących do jednej
przekątnej biegnącej z góry na dół, suma numeru jego
kolumny i wiersza jest stała, natomiast dla pól należących do
jednej przekątnej biegnącej z dołu do góry różnica numeru
jego kolumny i wiersza jest stała.



Informację gdzie ustawiono poszczególnych hetmanów, przechowuj w
tablicy liczb całkowitych. Indeks elementu tablicy oznacza numer
kolumny, wartość elementu tablicy zawiera numer wiersz, gdzie stoi
hetman

1. Dodaj do bieżącego rozwiązania nowy projekt

a. Z menu File wybierz Add/New Project...

b. W oknie dialogowym Add New Project określ następujące

właściwości:

i. typu projektu: Visual C#/Windows

ii. szablon: Console Application

iii. nazwa projektu: OsiemHetmanow.

2. Uczyń nowo utworzony projekt projektem startowym

a. Zaznacz projekt OsiemHetmanow w okienku Solution Explorer i z

menu kontekstowego wybierz Set as StartUp Project.

albo, gdy rozpoczynasz laboratorium od tego ćwiczenia

1. Uruchom Visual Studio

Naciśnij przycisk Start systemu Windows, wybierz Wszystkie Programy
następnie Microsoft Visual Studio 2005/ Microsoft Visual Studio 2005.

2. Utwórz nowy projekt

a. Z menu File wybierz New/Project...

b. W oknie dialogowym New Project określ następujące właściwości:

i. typu projektu: Visual C#/Windows

ii. szablon: Console Application

iii. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\

iv. nazwa projektu: OsiemHetmanow.

v. nazwa rozwiązania: Lab9

3. Do klasy Program dodaj stałą nazwaną RozmiarSzachownicy

reprezentującą rozmiar szachaownicy

const int RozmiarSzachownicy = 8;

4. Do klasy Program dodaj cztery tablice - zmienne współdzielone:

a. tablicę przechowującą informację czy dany wiersz jest zajęty

b. dwie tablice, jedną dla przekątnych z góry na dół, drugą dla

przekątnych z dołu do góry, zawierające informacje, czy dana
przekątna jest zajęta

c.

tablicę zawierającą informację, gdzie stoi hetman w poszczególnych
kolumnach

static byte[] kolumny =

new byte[RozmiarSzachownicy];

static bool[] wiersze =

new bool[RozmiarSzachownicy];

static bool[] przekatneDol =

new bool[2 * RozmiarSzachownicy - 1];

static bool[] przekatneGora =

new bool[2 * RozmiarSzachownicy - 1];

5. Do klasy Program dodaj metodę Sprawdz. Metoda Sprawdz

przyjmuje jako argument numer kolumny, na której chcemy postawić
hetmana oraz zwraca wartość boolowską.

static bool Sprawdz(int nrKolumny)
{
for(int wiersz =0; wiersz < RozmiarSzachownicy;

wiersz++)

{
if (wiersze[wiersz])
continue;
if (przekatneDol[wiersz + nrKolumny])
continue;
if (przekatneGora[wiersz - nrKolumny +

RozmiarSzachownicy - 1])

continue;
kolumny[nrKolumny] = (byte) (wiersz + 1);
wiersze[wiersz] = true;
przekatneDol[wiersz + nrKolumny] = true;
przekatneGora[wiersz - nrKolumny +

RozmiarSzachownicy - 1] = true;

if (nrKolumny == 7)
return true;
if (Sprawdz(nrKolumny + 1))
return true;
kolumny[nrKolumny] = 0;
wiersze[wiersz] = false;
przekatneDol[wiersz + nrKolumny] = false;
przekatneGora[wiersz - nrKolumny +

RozmiarSzachownicy - 1] = false;

}
return false;
}

6. Do klasy Program dodaj metodę WypiszRozwiazanie. Metoda

wypisuje jak należy ustawić hetmanów na szachownicy.

static void WypiszRozwiazanie()
{

char c = 'A';
for (int i = 0; i < RozmiarSzachownicy;

i++,c++)

{
Console.Write("{0}{1}, ", c, kolumny[i]);
}
}

7. W metodzie Main pobierz od użytkownika pozycję hetmana w pierwszej

kolumnie. Następnie wywołaj metodę Sprawdz, wcześniej zaznaczając
wybrane pole przez użytkownika jako zajęte. Jeżeli metoda Sprawdz
przekazała wartość true wywołaj metodę WypiszRozwiazanie, w
przeciwnym wypadku wypisz, że rozwiązanie nie istnieje.

static void Main(string[] args)
{
Console.Write("Podaj pozycje hetmana w

¬pierwszej kolumnie: wartość od 1 do {0}: ",

RozmiarSzachownicy);

int nrWiersza =

Convert.ToInt32(Console.ReadLine())-1;

kolumny[0] = (byte)(nrWiersza + 1);
wiersze[nrWiersza] = true;
przekatneDol[nrWiersza] = true;
przekatneGora[nrWiersza + RozmiarSzachownicy -

1] = true;

if(Sprawdz(1))
{
WypiszRozwiazanie();
}
else
{
Console.WriteLine("Rozwiązanie nie

¬istnieje!!!");

}
Console.ReadKey();
}

8. Skompiluj i uruchom program.