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ń:

 

        a6      
    c7          
a6              
          a6    
              c7
  a6            
      c7        
            c7  

 

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

Najpierw w pierwszym wierszu ustawimy hetmana na pierwszym polu szachownicy:

 

1 a6              
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 a6              
2     c7          
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 a6              
2     c7          
3         a6      
4                
5                
6                
7                
8                

 

I analogicznie postępujemy w wierszu czwartym:

 

1 a6              
2     c7          
3         a6      
4   a6            
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         a6      
2     c7          
3 a6              
4           a6    
5               c7
6   a6            
7       c7        
8             c7  

 

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       a6        
3                
4                
5             a6  
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...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

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