Pomoce:

Biblioteka procedur obsługi konsoli znakowej - newconio


Stos

Shay Alkalay Stack

Stos (ang. stack) jest jedną z częściej używanych struktur danych w programowaniu - stosuje go olbrzymia liczba algorytmów. Na stosie dane umieszczamy w sposób sekwencyjny. Pobieramy je również ze stosu sekwencyjnie (tzn. jedna za drugą), jednakże w kierunku odwrotnym do wpisania. Dobrym przykładem stosu może być zwykły stos książek lub czasopism - kładziemy je po kolei jedne na drugich. Ściągamy te, które są na wierzchu.

Do prostej realizacji stosu potrzebujemy dwóch rzeczy:

- tablicy, która będzie przechowywała dane umieszczone na stosie,

- zmiennej, w której będziemy przechowywali pozycję zapisu na stos. Zmienna ta nosi nazwę wskaźnika stosu (ang. stack pointer).

Przed rozpoczęciem pracy ze stosem wskaźnik stosu powinien być zainicjowany na 0. Umówmy się, że wskaźnik stosu zawiera numer komórki tablicy, w której możemy umieścić dane. Pierwszą komórką stosu jest komórka o indeksie 0, dlatego właśnie zerujemy wskaźnik stosu, aby wskazywał na tę komórkę.

Operacja zapisu na stos będzie polegała na umieszczeniu danej w komórce, którą adresuje wskaźnik stosu, po czym zwiększamy o jeden stan wskaźnika. W wyniku będzie on wskazywał komórkę o indeksie 1. To następne miejsce, gdzie na stosie można umieścić nową daną.

 



Zapis danych na stos

W miarę zapisu danych stos "rośnie" w górę. Liczbę danych przechowywanych na stosie zawiera wskaźnik stosu. Na powyższym obrazku wskaźnik stosu ma wartość 2, co oznacza, iż stos przechowuje dwie dane. Wskaźnik stosu wskazuje na komórkę o indeksie 2, która nie zawiera danych. Stos jest pusty wtedy, gdy wskaźnik stosu ma wartość 0.

Operacja odczytu danej ze stosu (który musi coś zawierać) polega na zmniejszeniu wskaźnika stosu o 1. Wtedy będzie on wskazywał komórkę, w której ostatnio umieściliśmy dane. Komórkę tę odczytujemy. Po odczycie komórkę możemy potraktować jako pustą.

 



Odczyt danych ze stosu

Przy odczycie danych stos "maleje" w dół. Operację odczytywania danych można prowadzić, aż do osiągnięcia przez wskaźnik stosu wartości 0. Wtedy stos jest pusty i dalszy odczyt nie ma sensu.

Podsumujmy:

stos[n] - tablica o n komórkach, w której realizujemy stos
ws - wskaźnik stosu

Inicjalizacja

ws = 0;

Zapis na stos

stos[ws++] = dane;

Odczyt ze stosu

dane = stos[--ws];

 

Poniższy program demonstruje prosty stos w tablicy. Zapisuje on na stosie 5 pseudolosowych liczb, a następnie je odczytuje ze stosu.

 

// Przykładowy stos
// (C)2010 ILO w Tarnowie
// KOŁO INFORMATYCZNE
//-----------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    int stos[5];
    int ws = 0;   // wskaźnik stosu

    srand(time(NULL)); // inicjujemy generator liczb pseudolosowych

    // zapisujemy na stos 5 przypadkowych liczb

    while(ws < 5)
    {
        int dane = rand() % 100;  // liczby pseudolosowe 0..99

        cout << "Zapis  ws = " << ws << " : " << dane << endl;

        stos[ws++] = dane;
    }

    cout << endl;

    // odczytujemy dane ze stosu

    while(ws > 0)
    {
        int dane = stos[--ws];

        cout << "Odczyt ws = " << ws << " : " << dane << endl; 
    }

    return 0;
}

 

Zapis  ws = 0 : 85
Zapis  ws = 1 : 65
Zapis  ws = 2 : 36
Zapis  ws = 3 : 17
Zapis  ws = 4 : 82

Odczyt ws = 4 : 82
Odczyt ws = 3 : 17
Odczyt ws = 2 : 36
Odczyt ws = 1 : 65
Odczyt ws = 0 : 85

 

Wieże Hanoi

Wieże Hanoi (ang. The Towers of Hanoi) są łamigłówką wymyśloną w 1883 roku przez matematyka francuskiego Edouarda Lucasa. Łamigłówka ta zbudowana jest z deseczki, na której znajdują się trzy patyczki w równych odstępach. Na pierwszym patyczku nasunięte są drewniane krążki o coraz mniejszych średnicach.

 

 

Celem jest przesunięcie wszystkich krążków z patyczka 0 na patyczek 2 wg następujących reguł:

  • naraz można przenosić tylko po jednym krążku,

  • krążek zdjęty z patyczka musi być nasunięty na jeden z pozostałych dwóch patyczków,

  • krążek można nasunąć na patyczek, jeśli jest on pusty lub zawiera krążek większy.

Łamigłówkę tę można prosto rozwiązać wykorzystując zasady rekurencji.

Załóżmy, że mamy jeden krążek. Wtedy rozwiązanie jest oczywiste - krążek przenosimy z patyczka 0 na 2 i zadanie jest zakończone:

 

 

Teraz przyjmijmy, że nasza wieża składa się z dwóch krążków. Startowym jest patyczek 0, a docelowym jest patyczek 2.

 

 

Rozwiązaniem będzie przeniesienie najpierw wierzchniego krążka na patyczek pomocniczy 1 (robimy to rekurencyjnie poprzednim sposobem przyjmując patyczek startowy 0 i docelowy 1). Następnie krążek większy przenosimy na patyczek docelowy 2 i znów rekurencyjnie przenosimy mniejszy krążek z patyczka pomocniczego 1 na docelowy 2.

 


Jeśli krążków jest 3, to najpierw dwa pierwsze przenosimy na patyczek 1, stosując powyższą metodę przy założeniu, że wyjściowym patyczkiem jest patyczek 0, a docelowym patyczek 1. Teraz przenosimy krążek największy z patyczka startowego 0 na docelowy 2. Pozostaje nam rekurencyjnie przenieść dwa pozostałe krążki z patyczka 1 (który przyjmujemy jako startowy) na patyczek docelowy 2.

 

 

Dla większej liczby krążków problem przyjmuje ten sam schemat postępowania:

n - liczba krążków do przeniesienia
A - patyczek startowy
B - patyczek pomocniczy
C - patyczek docelowy

przenieś(A,C,B,n)

    jeśli n > 1, to przenieś(A,B,C,n-1)
    przesuń krążek z patyczka A na patyczek C
    jeśli n > 1, to przenieś (B,C,A,n-1)

 

Wg tego schematu pracuje poniższy program rozwiązujący zagadkę wież Hanoi dla różnej liczby krążków. W programie wykorzystaliśmy naszą bibliotekę newconio do animacji przekładanych krążków.

 

// Wieże Hanoi
// (C)2010 ILO w Tarnowie
// KOŁO INFORMATYCZNE
//-----------------------

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

using namespace std;

const int MAXK = 5;                                 // liczba krążków
const int L = 7 + 6 * MAXK;                         // długość planszy
const int X = (80 - L) / 2;                         // pozycja x planszy
const int Y = 5 + MAXK;                             // pozycja y planszy
const int XP[3] = {X+MAXK+1,X+3*MAXK+3,X+5*MAXK+5}; // Pozycje x patyczków
const int PAUZA = 5;                                // opóźnienie ruchu

int wieza[3][MAXK];                                 // wieże Hanoi, czyli stosy
int w[3];                                           // wskaźniki stosów

int licznik;                                        // zlicza przesunięte krążki

// Rysuje podstawę wież z patyczkami
//----------------------------------
void plansza()
{
    fillrect(177,0x46,X,Y,X+L-1,Y);
    for(int i = 0; i < 3; i++)
      fillrect(179,15,XP[i],Y-MAXK,XP[i],Y-1);
}

// Rysuje krążek
// x,y - pozycja środka krążka
// r   - promień
// k   - kolor
//----------------------------
void krazek(int x, int y, int r, int k)
{
    putxy(' ',0,x-r-1,y);
    putxy(' ',0,x+r+1,y);
    fillrect(177,k,x-r,y,x-1,y);
    fillrect(177,k,x+1,y,x+r,y);
}

// Dodaje krążek do patyczka
//--------------------------
void dodaj(int p, int k)
{
    wieza[p][w[p]++] = k;
    krazek(XP[p],Y-w[p],k,(k % 8) + 0xf8);
}

// Zdejmuje krążek z patyczka
//---------------------------
int zdejmij(int p)
{
    krazek(XP[p],Y-w[p],MAXK,0);
    return wieza[p][--w[p]];
}

// Przesuwa krążek z patyczka A na B dokonując animacji
//-----------------------------------------------------
void przesunAB(int A, int B)
{
    int k,x,i,d,kolor;

    k = zdejmij(A);  // zdejmujemy krążek ze stosu A

    kolor =(k % 8) + 0xf8;
    x = XP[A];

    // przesuwamy krążek w górę z patyczka A

    for(i = Y-w[A]-2; i >= 3; i--)
    {
        krazek(x,i,k,kolor);
        krazek(x,i+1,k,0);
        delay(PAUZA);
    }

    // przesuwamy krążek w poziomie do patyczka B

    if(x > XP[B]) d = -1; else d = 1;

    while(x != XP[B])
    {
        x += d;
        krazek(x,3,k,kolor);
        putxy(' ',0,x,3);
        delay(PAUZA);
    }

    // opuszczamy krążek w dół na patyczek B

    for(i = 4; i < Y-w[B]; i++)
    {
        krazek(x,i,k,kolor);
        krazek(x,i-1,k,0);
        delay(PAUZA);
    }

    dodaj(B,k);  // umieszczamy krążek na stosie B

    textattr(15);
    gotoxy(39,1);
    cout << ++licznik;
}

// Przesuwa rekurencyjnie n krążków
//---------------------------------
void przesun(int A, int C, int B, int n)
{
    if(n > 1) przesun(A,B,C,n-1); // wywołanie rekurencyjne
    przesunAB(A,C);               // animujemy przesuwany krążek
    if(n > 1) przesun(B,C,A,n-1); // wywołanie rekurencyjne
}

//---------------
// PROGRAM GŁÓWNY
//---------------

int main()
{
    _cinit();
    cursoroff();
    textattr(7); clrscr();

    plansza();  // rysujemy planszę

    for(int i = 0; i < 3; i++) w[i] = 0;      // inicjujemy stosy

    for(int i = MAXK; i > 0; i--) dodaj(0,i); // umieszczamy krążki na patyczku 0 

    licznik = 0;

    przesun(0,2,1,MAXK);  // przesuwamy rekurencyjnie krążki

    while(!kbhit());      // czekamy na klawisz
    cursoron();
    return 0;
}

 

Wykorzystując ten program, sprawdź ile krążków jest przesuwanych dla wieży Hanoi o wysokości n.

 



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.