obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0

obrazek

Pomoce:

Biblioteka procedur obsługi konsoli znakowej - newconio

Rekurencja

Rekurencja powstaje wtedy, gdy funkcja wywołuje samą siebie do rozwiązania części problemu. Rekurencję często stosuje się w różnych algorytmach w informatyce (niektóre z nich bez rekurencji nie są w stanie efektywnie działać - np. algorytmy grafowe). Każde wywołanie funkcji w języku C++ odkłada na stosie procesora tzw. adres powrotny (miejsce w programie, do którego powraca procesor po wykonaniu kodu funkcji). Również wszystkie zmienne lokalne są tworzone na tym stosie. Zatem jeśli funkcja wywoływała by samą siebie w "nieskończoność", to już po kilkuset milionach wywołań stos procesora rozrósłby się na całą dostępną dla programu pamięć. Dlatego rekurencja musi posiadać ściśle określony koniec, tzn. zaprzestanie dalszych wywołań i zakończenie funkcji.

Dla przykładu utwórzmy program wyliczający rekurencyjnie silnię n!. Silnia n! to iloczyn kolejnych liczb naturalnych od 1 do n:

n! = 1 × 2 × ... × (n - 1) × n.

Np. 5! = 1 × 2 × 3 × 4 × 5 = 120

Silnię możemy zdefiniować rekurencyjnie:

1! = 1
n! = n × (n - 1)!

Zatem silnia np. 5! jest równa 5 × 4!. Aby ją policzyć musimy znaleźć 4!, co jest równe 4 × 3!. Postępując tak aż do jeden otrzymamy kolejne wartości silni, które później należy jedynie przez siebie przemnożyć:

5! = 5 × 4!
5! = 5 × 4 × 3!
5! = 5 × 4 × 3 × 2!
5! = 5 × 4 × 3 × 2 × 1! - koniec rekurencji, ponieważ 1! = 1.

// (C)2010 Koło Informatyczne I LO
//
// Silnia liczona rekurencyjnie
//--------------------------------

#include <iostream>

using namespace std;

unsigned long long silnia(unsigned long long n)
{
  if(n == 1) return 1;
  else       return n * silnia(n - 1);
}

int main()
{
    unsigned long long  n;

    cin >> n;

    cout << silnia(n) << endl;

    return 0;
}

Problem 8 hetmanów

Zadanie polega na rozmieszczeniu na szachownicy 8 hetmanów w taki sposób, aby się na wzajem nie atakowały. Dodatkowo będziemy sprawdzać liczbę takich układów dla szachownic o rozmiarze n × n. Poniżej mamy rysunek obrazujący jedno z ustawień:

Zadanie rozwiążemy rekurencyjnie w sposób następujący:

Najpierw w pierwszym wierszu ustawimy hetmana na pierwszym polu szachownicy:

1
2
3
4
5
6
7
8

Następnie przejdziemy do wiersza drugiego i znajdziemy w nim takie pole, które nie jest atakowane przez hetmana w wierszu pierwszym:

1
2
3
4
5
6
7
8

Postępując podobnie w wierszu trzecim znajdziemy pole, które nie atakują hetmany z wierszy 1 i 2:

1
2
3
4
5
6
7
8

I analogicznie postępujemy w wierszu czwartym:

1
2
3
4
5
6
7
8

Oraz w kolejnych wierszach postępujemy podobnie. Jeśli dotrzemy do 8 wiersza i postawimy w nim hetmana, to układ mamy gotowy i możemy go zaprezentować. Jeśli w danym wierszu nie możemy postawić hetmana, bo wszystkie pola są atakowane, to wracamy do poprzedniego wiersza i szukamy w nim nowego pola do postawienia hetmana, po czym wznawiamy wypełnianie wierszy hetmanami.

Zwróć uwagę, iż można ten proces sprowadzić do rekurencji:

Jeśli hetmany ustawione są we wszystkich wierszach szachownicy, to prezentujemy układ i kończymy rekurencję.

W przeciwnym razie w wierszu i-tym szukamy kolejnych pól, które nie są atakowane przez hetmany z wierszy poprzednich. Dla każdego takiego pola wywołujemy rekurencyjnie ten sam algorytm z numerem wiersza o 1 większym od bieżącego.

Do reprezentowania szachownicy w pamięci komputera użyjemy prostej tablicy ph[] (pozycje hetmanów). Zwróć uwagę, że w każdej kolumnie może znajdować się dokładnie jeden hetman. Zatem komórki tej tablicy będą reprezentowały numer wiersza szachownicy, w którym w danej kolumnie znajduje się hetman, Na przykład:

ph	3	6	2	7	1	4	8	5
1
2
3
4
5
6
7
8

Umówmy się, iż brak hetmana w kolumnie będziemy zaznaczali liczbą 0. Sytuacja taka ma miejsce, gdy w danym wierszu nie umieściliśmy jeszcze hetmana.

Kolejnym problemem będzie ustalenie, czy dane pole w w-tym wierszu jest atakowane przez hetmany w wierszach poprzedzających. Wystarczy wykryć jedną taką sytuację, aby pole zostało zdyskwalifikowane. Po pierwsze wybieramy pola i-te w w-tym wierszu, dla których odpowiadająca im komórka ph[i] zawiera wartość 0. Jeśli jest tam inna wartość, to w danej kolumnie jest już hetman i na tym polu nie możemy postawić następnego. Gdy znajdziemy takie pole, to przeglądamy kolejne komórki ph[j]. Jeśli zawierają wartość różną od zera, to musimy sprawdzić, czy reprezentujący ją hetman nie atakuje naszego pola po przekątnej. Będzie tak, jeśli odległość w kolumnach od tego hetmana i naszego pola będzie równa odległości w wierszach - wtedy oba hetmany są na tej samej przekątnej szachownicy i się atakują:

	1	2	3	4	5	6	7	8
1
2
3
4
5
6
7
8

Odległość w kolumnach = 7 - 4 = 3
Odległość w wierszach = 5 - 2 = 3

// (C)2010 Koło Informatyczne I LO
//
// Problem hetmanów
//------------------

#include "newconio.h"
#include <iostream>

using namespace std;

const int N = 12;  // rozmiar szachownicy

int ph[N+1];       // tablica pozycji hetmanów

int licznik;       // zlicza znalezione układy hetmanów

// funkcja wypisuje szachownicę z hetmanami
//-----------------------------------------

void szachownica()
{
    gotoxy(0,0);
    textcolor(WHITE);
    cout << "\nPOZYCJA " << ++licznik << endl << endl;
    textcolor(BLACK);
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
           if((i + j) % 2) textbackground(YELLOW);
           else            textbackground(GREEN);

           if(ph[j] == i) cout << "H";
           else           cout << " ";
        }
        textbackground(BLACK);
        cout << endl;
    }
}

// Wyszukuje układ hetmanów,
// które nawzajem się nie atakują
//--------------------------------

void szukaj(int w)
{
  if(w > N) szachownica(); // koniec rekurencji, wszystkie hetmany ustawione
  else
  {
      for(int i = 1; i <= N; i++) // szukamy wolnego pola w wierszu w-tym
         if(ph[i] == 0)           // jeśli jest takie pole
         {
             bool t = true;       // to sprawdzamy, czy nie jest atakowane
             for(int j = 1; j <= N; j++)
               if(ph[j] && (abs(i-j) == w - ph[j]))
               {
                   t = false;     // jest atakowane, dalej już nie szukamy
                   break;
               }
            if(t)                 // jeśli pole nie jest atakowane  
            {
                ph[i] = w;        // ustawiamy na nim hetmana
                szukaj(w + 1);    // przechodzimy do następnego wiersza
                ph[i] = 0;        // usuwamy hetmana i szukamy kolejnego pola
            }
         }
  }
}


int main()
{
    _cinit();

    for(int i = 1; i <= N; i++) ph[i] = 0;

    licznik = 0;

    szukaj(1);   // rozpoczynamy od wiersza nr 1

    return 0;
}

Za pomocą tego programu zbadaj liczbę układów hetmanów dla szachownic o N = 4,5,6,7...

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe