Matura - programowanie w C++

Mikroprocesor komputera komunikuje się z pamięcią poprzez złącza, które są widoczne u spodu modułu pokazanego na obrazku powyżej. Oczywiście nie będziemy wchodzić w szczegóły techniczne, wyjaśnimy jedynie podstawy działania pamięci.

Bity przechowywane w pamięci są zorganizowane w grupy po 8 bitów, które nazywamy bajtami. Bajty przechowywane są w numerowanych komórkach. Numery komórek nazywamy adresami. Wygląda to następująco:

Komórek w pamięci jest bardzo dużo (współcześnie miliardy), adresy są zatem zwykle duże. W języku C++ przyjęto, że adres 0 (NULL) nie wskazuje żadnej komórki. Oczywiście fizyczna komórka o adresie 0 może istnieć w przestrzeni adresowej komputera, ale w C++ nie jest używana.

Mikroprocesor komunikuje się z pamięcią za pomocą tzw. magistral (ang. buses). Magistrala jest grupą linii sygnałowych (linie sygnałowe przenoszą sygnały - w przypadku współczesnych komputerów są to sygnały binarne kodowane napięciami: 5V stan wysoki 1, 0V stan niski 0).

Mamy trzy rodzaje magistral:

• magistrala adresowa (ang. address bus)
• magistrala danych (ang. data bus)
• magistrala sterująca (ang. control bus)

Powyższy rysunek przedstawia sposób dostępu mikroprocesora do modułu pamięci za pomocą magistral. Nie sugeruj się grubością magistral – to tylko schemat poglądowy.

Magistralą adresową mikroprocesor przekazuje adres komórki pamięci, do której chce uzyskać dostęp. Adres jest w postaci dwójkowej, a każda linia magistrali przekazuje 1 bit tego adresu. Od liczby linii adresowych zależy rozmiar przestrzeni adresowej, czyli liczby komórek, które procesor jest w stanie zaadresować. Przestrzeń ta we współczesnych komputerach sięga wielu gigabajtów (miliardów komórek).

Magistrala danych jest dwukierunkowa, tzn. mogą nią biegnąć informacje od procesora do pamięci lub odwrotnie. Dane są binarne. Szerokość magistrali zależy od fizycznych parametrów komputera, współcześnie jest to zwykle 64 bity (w mikroprocesorach 64 bitowych).

Magistrala sterująca określa tryb pracy pamięci: odczyt lub zapis danych. Składa się najczęściej tylko z kilku linii sterujących.

Teraz krótko opiszemy uproszczony sposób pracy pamięci komputerowej (w rzeczywistości jest to dużo bardziej skomplikowane).

Zapis danych do pamięci

Gdy procesor potrzebuje zapisać informację w pamięci, wykonuje następujące czynności:

• Umieszcza binarny adres komórki na magistrali adresowej.
• Umieszcza dane dla wybranej komórki na magistrali danych.
• Na magistralę sterującą przesyła polecenie zapisu (ang. memory write). W efekcie pamięć odczytuje informację z magistrali danych, wyszukuje komórkę o adresie na magistrali adresowej i umieszcza informację w bitach wybranej komórki.

Odczyt danych z pamięci

Gdy mikroprocesor potrzebuje odczytać informację z pamięci, wykonuje następujące czynności:

• Na magistrali adresowej umieszcza binarny adres komórki pamięci, z której ma być odczytana informacja.
• Na magistralę sterującą przesyła polecenie odczytu (ang. memory read). W efekcie pamięć odszukuje komórkę o adresie na magistrali adresowej i umieszcza jej zawartość na magistrali danych.
• Procesor odczytuje informację z magistrali danych.

Jeśli chcesz poznać więcej informacji na temat pamięci, to przeczytaj osobny artykuł w naszym serwisie:

Pamięć

Do zapamiętania:

• Budowa pamięci
• Magistrale
• Zapis i odczyt danych

Program komputerowy składa się z ciągu instrukcji umieszczonych w pamięci operacyjnej. Mikroprocesor wykonując program adresuje te instrukcje i pobiera je z komórek pamięci, po czym rozpoznaje pobraną instrukcję i wykonuje określoną przez nią operację.

Jeśli chciałbyś głębiej poznać to zagadnienie i pobawić się prostym komputerem, to proponuję przejść do artykułu "Przykładowa Maszyna Cyfrowa II".

Gdy w programie zostaje napotkane wywołanie funkcji, mikroprocesor wykonuje "skok" do adresu zawierającego pierwszą instrukcję tej funkcji i rozpoczyna wykonywanie jej kodu. Ale pojawia się tutaj problem. Po wykonaniu kodu funkcji procesor powinien powrócić do miejsca za wywołaniem. Ponieważ funkcja może być wielokrotnie wywoływana w różnych miejscach programu, adresy powrotu będą różne. Należy je zatem zapamiętać. Do tego celu służy właśnie stos (ang. stack). Jest to struktura danych tworzona przez procesor w pamięci komputera. Możesz ją sobie wyobrazić jako stos książek. Gdy wstawiamy coś na stos, to trafia to na szczyt. Gdy pobieramy coś ze stosu, to bierzemy kolejno ze szczytu.

Przykład: Zapisujemy na stosie trzy dane: kolejno dane 1, dane 2 i dane 3.

Dane 1 trafią na szczyt stosu. Szczyt przesunie się w pamięci.

Dane 2 również trafią na szczyt stosu, czyli znajdą się ponad danymi 1.

Dane 3 trafiają na szczyt stosu. Zwróć uwagę, iż na stosie są one w odwrotnej kolejności:

Jeśli teraz pobierzemy kolejno dane ze szczytu stosu, to otrzymamy je w odwrotnej kolejności:

Zauważ, iż na szczycie stosu znajduje się zawsze dana, która została tam umieszczona ostatnio. Do czego to się przydaje? Otóż zastosowanie stosu jest ogromne. Na stosie umieszczane są nie tylko adresy powrotne, ale również zmienne lokalne, parametry i wyniki funkcji. Jak to wygląda?

Gdy w programie komputer napotyka wywołanie funkcji, umieszcza na stosie parametry funkcji oraz adres powrotny, który wskazuje następną instrukcję w programie za wywołaniem funkcji. Następnie procesor wykonuje skok do kodu funkcji, który może zarezerwować na stosie miejsce na zmienne lokalne, jeśli kod funkcji takie zawiera. Wykonany jest kod funkcji. Gdy kod jest zakończony, procesor usuwa ze stosu wszystkie zmienne lokalne (dlatego przestają one istnieć w programie). Na stos jest przesyłany wynik funkcji (jeśli taki jest), po czym procesor wykonuje skok pod adres powrotny, który wskazuje kod programu wywołującego funkcję (tuż za jej wywołaniem). Kod ten pobiera wynik i usuwa wszystkie dane, które trafiły na stos przy wywołaniu funkcji, w ten sposób stos zostaje wyczyszczony i jest gotowy na kolejne wywołanie.

Jeśli w trakcie wykonywania funkcji wystąpi kolejne wywołanie funkcji, to jej dane trafią na szczyt stosu ponad danymi funkcji podstawowej. Dzięki temu nie będą się nawzajem zakłócać. Przeanalizujmy prosty program:

// Rekurencja
//----------------

#include <iostream>

using namespace std;

void f(int a)
{
    cout << "Poziom: " << a << endl;
    if(a < 9) f(a + 1);
}

int main()
{
    f(0);

    return 0;
}

Poziom: 0
Poziom: 1
Poziom: 2
Poziom: 3
Poziom: 4
Poziom: 5
Poziom: 6
Poziom: 7
Poziom: 8
Poziom: 9

W programie znajduje się pojedyncza funkcja z jednym parametrem:

void f(int a)
{
    cout << "Poziom: " << a << endl;
    if(a < 9) f(a);
}

Funkcja wyświetla wartość parametru, następnie sprawdza jego wartość i jeśli parametr jest mniejszy od 9, ponownie wywołuje samą siebie lecz z parametrem zwiększonym o 1. Nic skomplikowanego, jak widać. Teraz przeanalizujmy zawartość stosu w czasie pracy tego programu.

Zaczynamy od funkcji głównej, w której jest wywołanie funkcji f( ) z parametrem 0: Na stos trafia adres powrotny z f( ) do main( ) oraz parametr 0:

Następnie komputer przechodzi do kodu funkcji f( ) i zaczyna go wykonywać. Wypisuje w oknie konsoli wartość parametru, po czym sprawdza, czy parametr jest mniejszy od 9. Przy pierwszym wywołaniu parametr a ma wartość 0, zatem warunek a < 9 jest prawdziwy i instrukcja if wywoła funkcję f( ) z parametrem zwiększonym o 1. Ponieważ jest to wywołanie z kodu funkcji f( ) to na szczyt stosu trafi nowy adres powrotny oraz parametr a = 1. Stos będzie wyglądał następująco:

Zwróć uwagę, iż poprzednie dane są wciąż na stosie, ponieważ funkcja f( ) wywołana z main( ) nie zakończyła jeszcze pracy, lecz wywołała samą siebie. Nastąpiło tzw. wywołanie zagnieżdżone (ang. nested call). Komputer wykonuje kod funkcji f( ) z nowym parametrem a = 1. Zauważ, iż przy takim wywołaniu kod funkcji f( ) jest taki sam, lecz dane na stosie są inne, dlatego funkcja może się wykonywać inaczej. Po wypisaniu parametru a sprawdzana jest jego wartość przez instrukcję if i jeśli jest wciąż mniejsza od 9, to nastąpi kolejne wywołanie zagnieżdżone f( ) z parametrem o 1 większym, czyli 2. Stos będzie wyglądał następująco:

Proces ten będzie kontynuowany, aż do wywołania f( ) z parametrem 9. Stos przyjmie wtedy postać:

Co stanie się teraz? Jesteśmy na 10 wywołaniu funkcji f( ), a parametr a = 9. Funkcja wyświetli wartość parametru w oknie konsoli, po czym nastąpi przejście do instrukcji warunkowej if. Tym razem warunek a < 9 będzie fałszywy i instrukcja if nie dokona kolejnego wywołania funkcji f( ). Bieżąca funkcja f( ) zakończy działanie. Komputer wróci za miejsce wywołania tej funkcji na niższy poziom, po czym usunie ze stosu adres powrotny i dane. Stos będzie wyglądał następująco:

Wciąż program znajduje się w funkcji f( ) w tym miejscu:

...
if(a < 9) f(a + 1);X
                   ^

a zatem na końcu funkcji f( ). Ponieważ nie ma dalszych instrukcji, funkcja f( ) kończy działanie i wraca za miejsce wywołania na niższy poziom, a dane ze stosu są usuwane. Proces ten będzie kontynuowany, aż do powrotu do funkcji głównej main( ), po czym program zakończy się.

Do zapamiętania:

• Stos, umieszczanie danych na stosie, pobieranie danych ze stosu.
• Adresy powrotne z wywołań funkcji i ich umieszczanie na stosie wraz z parametrami i resztą danych funkcji.
• Kończenie pracy funkcji, powrót pod adres powrotny i usuwanie ze stosu danych funkcji.
• Wywołanie zagnieżdżone.

// Rekurencja nieskończona
//------------------------

#include <iostream>

using namespace std;

void f(void)
{
    f();
}

int main()
{
    f();

    return 0;
}

Process returned -1073741571 (0xC00000FD)

Co się stało? W pewnym momencie system przerywa wykonywanie tego programu i zwraca kod błędu 0xC00000FD. Sprawdźmy, co oznacza ten błąd:

0xC00000FD - STACK OVERFLOW (przepełnienie stosu)

Stos został w całości zapełniony adresami powrotnymi i przy kolejnym wywołaniu funkcji f( ) komputer nie mógł już zapisać na stosie jej adresu powrotnego. Dlatego program zakończył się z błędem. Na to musimy uważać przy rekurencji.

Po co nam rekurencja? Otóż okazuje się, iż wiele problemów upraszcza się przy jej zastosowaniu. Na przykład policzmy rekurencyjnie silnię. Definicja jest rekurencyjna:

Jak to odczytać? Prosto: 0! = 1, natomiast dla argumentów większych lub równych 1: n! = n · (n - 1)! Widzisz tutaj rekurencję? Spróbujmy obliczyć 6! wg definicji:

6! = 6 · (6 - 1)! = 6 · 5!

Teraz rozwijamy kolejne silnie, aż dojdziemy do przypadku 0!:

6! = 6·(5·4!) = 6·5·4! 
6! = 6·5·(4·3!) = 6·5·4·3!
6! = 6·5·4·(3·2!) = 6·5·4·3·2!
6! = 6·5·4·3·(2·1!) = 6·5·4·3·2·1!
6! = 6·5·4·3·2·(1·0!) = 6·5·4·3·2·1·1 = 720

Tworząc funkcję rekurencyjną, najpierw sprawdzamy warunek zakończenia rekurencji, a dopiero później wywołujemy rekurencyjnie funkcję, ale ze zmienionym argumentem. W przeciwnym razie ryzykujemy wpadnięcie w nieskończoną rekurencję, co zakończy się błędem przepełnienia stosu.

Przeanalizujmy poniższy program:

// Rekurencja
// Silnia
//------------

#include <iostream>

using namespace std;

unsigned long long silnia(unsigned n)
{
    // Sprawdzamy warunek wyjścia z rekurencji

    if(!n) return 1;

    // Wchodzimy w rekurencję

    return n * silnia(n - 1);
}

int main()
{
    int n;
    cout << "Obliczanie silni" << endl
         << "----------------" << endl << endl
         << "n = ";
    cin >> n;
    cout << endl
         << "silnia(" << n << ") = "
         << silnia(n) << endl << endl;

    return 0;
}

Obliczanie silni
----------------

n = 15

silnia(15) = 1307674368000

Program składa się z funkcji silnia( ), która wylicza rekurencyjnie wartość silni. Funkcja jest wywoływana z paramem typu unsigned, czyli całkowitym w 32-bitowym kodzie BNC. Funkcja zwraca wartość typu unsigned long long, czyli całkowitą BNC 64-bitową. Silnia rośnie bardzo szybko i wynik obliczeń przekracza zakres liczb 64-bitowych BNC już dla niewielkich wartości parametru:

Zakres 64-bitowych liczb BNC: 0...

18'446'744'073'709'551'615

19! =

121'645'100'408'832'000

OK

20! =

2'432'902'008'176'640'000

OK

21! =

51'090'942'171'709'440'000

 za dużo

Dla parametru n =21 program zwróci bladną wartość (14197454024290336768), ponieważ wynik nie mieści się w 64-bitowej liczbie NBC i zostaje obcięty do ostatnich 64 bitów. Jeśli tego nie rozumiesz, wróć do początkowych rozdziałów o kodowaniu liczb.

Funkcja silnia( ) składa się z dwóch części. W pierwszej sprawdzamy warunek zakończenia rekurencji, czyli czy parametr n jest równy 0:

if(!n) return 1;

W takim przypadku funkcja kończy działanie i zwraca jako wynik wartość 1. Nie występuje tutaj wywołanie rekurencyjne.

W drugiej części pojawia się rekurencja:

return n * silnia(n - 1);

Zanim funkcja zakończy działanie i zwróci wynik, wywołuje samą siebie z parametrem n mniejszym o 1. Wynik nie zostanie zwrócony, aż wywołana funkcja nie wyliczy (n - 1)! W wywołanej funkcji występuje ten sam proces i silnia( ) jest rekurencyjnie wykonywana aż do osiągnięcia przez parametr wartości 0. Wtedy wywołania rekurencyjne kończą się i następują powroty z kolejnymi wartościami silni aż do poziomu podstawowego, w którym wyliczana jest ostateczna wartość silni i zwracana do programu głównego. Wygląda to następująco:

Kolorem czerwonym są oznaczone wywołania rekurencyjne, kolorem niebieskim są oznaczone powroty z wywołań rekurencyjnych z wynikiem funkcji. Z tego diagramu widać wyraźnie, iż funkcja podstawowa zakończy działanie dopiero po powrotach ze wszystkich wywołań rekurencyjnych. Przeanalizuj to dokładnie, aż wszystko będzie dla ciebie zrozumiałe.

Do zapamiętania:

• Zasada rekurencji.
• Przepełnienie stosu przy rekurencji nieskończonej.
• Tworzenie funkcji rekurencyjnej.
• Rekurencyjna funkcja obliczania silni.

K01: Dopóki b ≠ 0,
     wykonuj kroki K02...K04
K02:    r ← a mod b
K03:    a ← b
K04:    b ← r
K05: Zakończ

Przyjrzyj się dokładnie temu algorytmowi. Zapiszmy go w nieco innej postaci, która jest równoważna:

K01: Jeśli b = 0,
     to zakończ z wynikiem a
K02: r ← a mod b
K03: a ← b
K04: b ← r
K05: Wróć do kroku K01

Zwróć uwagę, iż znalezienie NWD wymaga wykonania cyklicznego tych samych operacji, aż do wykrycia, iż b = 0. Wtedy wykonywanie jest przerywane, a wynik znajduje się w a. Taką postać algorytmu da się łatwo przetworzyć na postać rekurencyjną:

Jeśli b = 0, to wynikiem jest a. W przeciwnym razie wynikiem jest NWD z parametrem a zamienionym na b, i parametrem b zamienionym na resztę z dzielenia a przez b.

Uruchom program:

// Rekurencja
// Algorytm Euklidesa
//-------------------

#include <iostream>

using namespace std;

unsigned NWD(unsigned a, unsigned b)
{
    // Sprawdzamy warunek wyjścia z rekurencji

    if(!b) return a;

    // Wchodzimy w rekurencję

    return NWD(b, a % b);
}

int main()
{
    unsigned a,b;
    cout << "Obliczanie NWD" << endl
         << "--------------" << endl << endl
         << "a b = ";
    cin >> a >> b;
    cout << endl
         << "NWD(" << a << "," << b << ") = "
         << NWD(a,b) << endl << endl;

    return 0;
}

Obliczanie NWD
--------------

a b = 36 24

NWD(36,24) = 12

W algorytmie wyjściowym występowała pętla, którą zastąpiliśmy rekurencją. Wersja rekurencyjna jest zwykle wolniejsza i zajmuje więcej pamięci (dlaczego?).

Do zapamiętania:

• Rekurencyjna wersja algorytmu Euklidesa