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.

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);
}

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

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

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

1. typu projektu: Visual C#/Windows

2. szablon: Class Library

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

4. nazwa projektu: Biblioteka.

5. nazwa rozwiązania: Demo10

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

1. 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.

1. W oknie Solution Explorer z menu kontekstowego związanego z elementem reprezentującym plik Class1.cs wybierz Rename.

2. Zmień tekst Pole.cs na Pole.cs

5. Dodaj do klasy Pole:

1. Metodę Kwadrat zwracającej pole kwadratu i przyjmującą jako argument długość jego boku.

2. 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.

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

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

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. nazwa projektu: TestBiblioteki.

8. Uczyń nowo utworzony projekt projektem startowym

1. Zaznacz projekt TestBiblioteki w okienku Solution Explorer i z menu kontekstowego wybierz Set as StartUp Project.

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

1. W okienku Solution Explorer, z menu kontekstowego związanego z elementem reprezentującym projekt TestBiblioteki wybierz Add Reference...

2. 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.

1. 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));

2. 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;

3. 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

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

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

1. typu projektu: Visual C#/Windows

2. szablon: Class Library

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

4. nazwa projektu: QuickSort.

5. 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,uint lewy,uint
   prawy)
   {
   uint 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, (uint)tab.Length - 1);
   }

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

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

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

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. nazwa projektu: TestSortowania.

3. Uczyń nowo utworzony projekt projektem startowym

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

1. W okienku Solution Explorer, z menu kontekstowego związanego z elementem reprezentującym projekt TestSortowania wybierz Add Reference...

2. W okienku Add Reference przejdź do zakładki Projects, zaznacz projekt Sortowanie i naciśnij OK.

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

6. 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:

• 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

• 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

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

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

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. nazwa projektu: OsiemHetmanow.

2. Uczyń nowo utworzony projekt projektem startowym

1. 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

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

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

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

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

4. nazwa projektu: OsiemHetmanow.

5. 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:

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

2. 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

3. 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.
   

L

L

---