Przykład 1: Min

Możliwości oferowane przez funkcje omówimy na przykładach. Oto pierwszy z nich – funkcja obliczająca minimum z dwóch liczb całkowitych:

int min(int a, int b) {
    if (a < b)
        return a;
    else
        return b;
}

W pierwszym wierszu mamy tzw. nagłówek funkcji, w którym podajemy nazwę funkcji, jej parametry (argumenty) i typ wyniku funkcji. Powyższa funkcja o nazwie min przyjmuje dwa parametry, \(a\) i \(b\), oba typu int. Wynikiem funkcji jest również liczba typu int. Dalej, między nawiasami klamrowymi znajduje się tzw. wnętrze funkcji. Fragment programu występujący we wnętrzu powyższej funkcji widzieliśmy już wielokrotnie, jest to rzeczywiście obliczanie minimum z dwóch liczb. Wynik funkcji opatrzony jest słowem kluczowym return. Jeśli \(a<b\), to wynikiem funkcji jest \(a\), a w przeciwnym razie \(b\). Czasem mówi się także, że funkcja zwraca \(a\) (odpowiednio \(b\), w zależności od przypadku).

Gdy już umieścimy jakiś fragment programu w postaci funkcji, możemy później tę funkcję wielokrotnie wywoływać w kodzie programu. Wywołanie funkcji polega na tym, że w miejsce jej parametrów umieszczamy jakieś konkretne wartości odpowiedniego typu i możemy oczekiwać, iż funkcja wykona dla tych wartości fragment kodu znajdujący się w jej wnętrzu i da odpowiedni wynik. Na przykład następujący fragment programu wypisze liczbę 3.

cout << min(3, 5) << endl;

Jeśli zamiast wartości w parametrach funkcji umieścimy jakieś wyrażenia, funkcja również wykona się, ale najpierw obliczy wartości tych wyrażeń. Przykładowo w tym fragmencie programu:

int x, y, z;
cin >> x >> y >> z;
cout << min(x + y, y * z);

najpierw zostaną obliczone wartości wyrażeń \(x+y\) oraz \(y-z\), a następnie zostaną one podstawione w miejsce parametrów funkcji min.

Przykład 2: Liczby pierwsze

Jedno z zadań do samodzielnego rozwiązania w poprzedniej lekcji polegało na napisaniu programu sprawdzającego, czy wczytana liczba całkowita jest liczbą pierwszą. Również taki fragment programu możemy umieścić w funkcji. Jeśli w jakimś innym programie będziemy chcieli sprawdzić, czy jakaś liczba jest liczbą pierwszą, wystarczy przekopiować poniższą funkcję do tego nowego programu i potem ją wywoływać.

bool czy_pierwsza(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;
    return true;
}

Powyższa funkcja przyjmuje tylko jeden parametr, a jej wynikiem jest wartość typu logicznego bool. Funkcja działa tak, że zmienna \(i\) przebiega kolejne liczby naturalne począwszy od dwójki. Jeśli przy którejś z nich natrafi na liczbę będącą dzielnikiem liczby \(n\), to funkcja zwróci wartość false i się zakończy. Jeśli natomiast funkcja przejdzie wszystkie wartości aż do \(n-1\) i mimo tego nie znajdzie żadnego dzielnika liczby \(n\), pętla zakończy się, a wynikiem funkcji będzie true.

Działanie funkcji kończy się zatem przy pierwszym napotkanym return. A co jeśli działanie funkcji skończy się, a wciąż nie natrafimy na słowo return? Byłoby tak na przykład wtedy, gdybyśmy zapomnieli w powyższej funkcji o końcowym return true. Wówczas wynik funkcji w takim przypadku byłby niezdefiniowany – zupełnie tak, jak w przypadku zmiennej, której nie ustawiliśmy żadnej wartości. Może to być trudny do wykrycia błąd.

Jeśli chcesz poćwiczyć pisanie funkcji z innymi typami argumentów, napisz funkcje: czy_samogloska sprawdzającą, czy dana litera jest samogłoską, oraz czy_palindrom sprawdzającą, czy dany napis jest palindromem (patrz zadanie 2 z poprzedniej lekcji).

Przykład 3: Suma w tablicy

Parametrem funkcji może także być tablica. Oto funkcja, która oblicza sumę elementów w tablicy.

#include <iostream>
using namespace std;

int suma(int t[], int n) {
    int wyn = 0;
    for (int i = 0; i < n; i++)
        wyn += t[i];
    return wyn;
}

int main() {
    int n;
    cin >> n;
    int t[n];
    for (int i = 0; i < n; i++)
        cin >> t[i];
    cout << suma(t, n) << endl;
}

W parametrze funkcji rozmiar tablicy musi być stałą albo możemy go w ogóle nie podawać, jak w funkcji powyżej. Wówczas musimy także podać osobnym w parametrze liczbę elementów tablicy. Gdy uruchomimy ten program dla danych:

3
1 2 3

jego wynikiem będzie 6. Natomiast gdybyśmy zapomnieli o instrukcji return wyn, program mógłby zwrócić dowolną wartość. U nas akurat było to 0. (Jest to dosyć częsty błąd: obliczamy wynik funkcji, ale zapominamy go zwrócić).

Przykład 4: Funkcja main

Nie po raz pierwszy okazuje się, że nowość, którą wprowadzamy w lekcji, tak naprawdę już stosowaliśmy wcześniej, tylko o tym nie wiedzieliśmy. Otóż główna funkcja programu, od której zaczyna się jego wykonywanie – funkcja main – jest niczym innym jak zwykłą funkcją bez parametrów, której wynikiem jest liczba całkowita typu int.

Jest jedna różnica między funkcją main a innymi funkcjami. Otóż w funkcji main nie trzeba zwracać wyniku za pomocą return. Wówczas wynikiem funkcji jest 0, co oznacza, że program zakończył się poprawnie.

Przykład 5: Zliczanie cyfr liczby

Kolejny z przykładów to funkcja wyznaczająca liczbę cyfr danej liczby całkowitej. Ten fragment programu również pojawił się już wcześniej – w lekcji 5. Zapisany w postaci funkcji może np. wyglądać tak:

#include <iostream>
using namespace std;
 
int liczba_cyfr(int n) {
    if (n == 0)
        return 1;
    int wyn = 0;
    while (n > 0) {
        wyn++;
        n /= 10;
    }
    return wyn;
}

int main() {
    int n;
    cin >> n;
    cout << liczba_cyfr(n) << endl;
}

Pierwsza ciekawa rzecz w tym przykładzie jest taka, że znów mocno korzystamy z faktu, że funkcja kończy się po napotkaniu pierwszego return. To oznacza, że w podanej instrukcji warunkowej nie musimy używać części else. Jeśli \(n=0\), funkcja da w wyniku 1 i natychmiast zakończy się.

Jest też druga, ciekawsza rzecz występująca w tym programie. Otóż w trakcie obliczeń modyfikujemy wartość jej parametru \(n\)! W funkcji parametr możemy traktować po prostu jako jeszcze jedną zmienną. Co jednak stanie się po wywołaniu tej funkcji? Jaką wartość otrzymamy, gdy na samym końcu programu wypiszemy zmienną \(n\)?

Okazuje się, że wartość \(n\) nie zmieni się w wyniku wywołania funkcji. Gdybyśmy chcieli, aby wartość ta zmieniła się, musielibyśmy przekazać tę zmienną przez referencję. Robi się to tak, że przed nazwą danego parametru wpisuje się znak &:

int liczba_cyfr(int &n) {

Przy takim zapisie funkcji wypisana na końcu zmienna \(n\) ma już wartość 0. Jest to może ciekawe, ale w tym przykładzie kompletnie bezużyteczne – dużo lepiej wydaje się zachować w programie początkową wartość zmiennej \(n\). Sensowne wykorzystanie referencji pokażemy w kolejnym przykładzie.

Jeśli przekazujemy parametr przez referencję, to musimy pamiętać, aby przy wywołaniu funkcji w miejsce parametru umieścić zmienną (lub np. element tablicy). Nie może to być np. liczba ani wyrażenie arytmetyczne.

Przykład 6: Swap

Gdy zacznie się na poważnie programować np. z użyciem tablic, często wykonywaną operacją staje się zamiana wartości dwóch zmiennych. Może to być także zamiana wartości na dwóch pozycjach w tablicy. Gdyby chcieć zamienić wartości zmiennych całkowitych \(a\) oraz \(b\), moglibyśmy napisać tak:

int a, b;
cin >> a >> b;
a = b;
b = a;
cout << a << " " << b << endl;

Jednak ten fragment programu nie działa! Zauważmy, że po pierwszym przypisaniu wartości obu zmiennych są równe, więc drugie przypisanie nic nie zmieni. W wyniku pierwszego przypisania tracimy wartość zmiennej \(a\). Aby jej nie stracić, musimy użyć trzeciej zmiennej, w której zapamiętamy początkową wartość zmiennej \(a\).

int a, b;
cin >> a >> b;
int c = a;
a = b;
b = c;
cout << a << " " << b << endl;

Ze względu na częste występowanie operacji zamiany w programach, dobrze jest także umieścić ją w postaci funkcji. Użyjemy w niej przekazywania parametrów przez referencję.

void swap(int &a, int &b) {
    int c = a;
    a = b;
    b = c;
}

Funkcja ta ewidentnie nie zwraca żadnego wyniku, co oznaczamy, podając jako typ wyniku słówko void.

Warto na koniec wspomnieć, że jeśli parametrem funkcji jest tablica, elementy tej tablicy są automatycznie podawane przez referencję.

Przykład 7: Będzie dalej

Dotychczas omawiane przykłady funkcji dawały w wyniku pojedynczą liczbę lub nawet wartość logiczną, jednak nic bardziej skomplikowanego. Jak moglibyśmy sobie poradzić, gdybyśmy chcieli podać w wyniku nie jedną, lecz np. kilka liczb? Albo np. liczbę i jakiś napis? Można by w tym celu używać przekazywania parametrów przez referencję, jednak jest to dosyć zakręcone. Możemy też wprowadzić typ złożony. Służy do tego celu słówko struct.

struct osoba {
    string imie;
    int wiek, wzrost;
    bool czy_kobieta;
};

W powyższym przykładzie określiliśmy nazwę typu złożonego – osoba, oraz elementy, z których składa się typ, tzw. pola. Każdy z tych elementów ma swoją nazwę i typ. Tutaj są to: jedno pole typu string, dwa pola typu int oraz jedno pole typu bool.

Odtąd możemy deklarować zmienne typu osoba. Do poszczególnych pól takich zmiennych odwołujemy się, podając nazwę pola po kropce. Np.:

osoba o;
o.imie = "Ania";
o.czy_kobieta = true;
cout << o.imie << endl;

Taką zmienną możemy więc traktować jako kombinat kilku zmiennych różnych typów. Struktur można używać do przechowywania kilku połączonych informacji w jednym miejscu. Można także się nimi posłużyć w celu przechowywania wyniku funkcji złożonego z wielu elementów. Dobrzy przykład takiego zastosowania znajduje się w komentarzu do lekcji (ułamki).

#include <algorithm>

#include <cstdlib>

#include <iostream>
using namespace std;

int suma(int t[], int n) {
    int wyn = 0;
    for (int i = 0; i < n; i++)
        wyn += t[i];
    return wyn;
}

int min(int t[], int n) {
    int wyn = t[0];
    for (int i = 1; i < n; i++)
        if (t[i] < wyn)
            wyn = t[i];
    return wyn;
}

int main() {
    int n;
    cin >> n;
    int t[n];
    for (int i = 0; i < n; i++)
        cin >> t[i];
    cout << suma(t, n) << endl
         << min(t, n)  << endl;
}

#include <iostream>
using namespace std;

const int MAX_N = 1000000;

int t[MAX_N];
int n;

int suma() {
    int wyn = 0;
    for (int i = 0; i < n; i++)
        wyn += t[i];
    return wyn;
}

int min() {
    int wyn = t[0];
    for (int i = 1; i < n; i++)
        if (t[i] < wyn)
            wyn = t[i];
    return wyn;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> t[i];
    cout << suma() << endl
         << min()  << endl;
}

Chcemy napisać funkcję \(NWD\) zgodną z następującą specyfikacją:

Funkcja NWD

Argumenty:
dodatnie liczby całkowite \(a\), \(b\)

Wynik:
największy wspólny dzielnik liczb \(a\), \(b\)

Jeden z najprostszych algorytmów obliczania największego wspólnego dzielnika polega na przeglądaniu kolejnych potencjalnych dzielników liczb \(a\) i \(b\), poczynając od 2 (wiadomo, że 1 dzieli bez reszty obie liczby), aż do mniejszej z tych liczb i zapamiętaniu największego dzielnika, który dzieli obie liczby bez reszty. Jednak można to zrobić sprytniej.

Euklides był greckim matematykiem, który żył na przełomie czwartego i trzeciego wieku przed naszą erą. Jest znany jako autor Elementów, w których zajmował się geometrią i teorią liczb. Algorytm obliczania największego wspólnego dzielnika dwóch dodatnich liczb całkowitych został opisany w Księdze 7. Elementów. Według wybitnego, współczesnego informatyka Donalda Knutha, algorytm zaproponowany przez Euklidesa jest najstarszym algorytmem, który został przedstawiony w postaci ogólnej, a nie tylko przez przykłady.

Współcześnie algorytm Euklidesa można opisać następująco. Jeśli \(a\) jest podzielne bez reszty przez \(b\), to największym wspólnym dzielnikiem jest \(b\). W przeciwnym razie mamy, że \(a = q \cdot b + r\), gdzie \(q\) mówi, ile razy całkowicie \(b\) mieści się w \(a\), natomiast \(r\) jest resztą z dzielenia \(a\) przez \(b\). Wówczas wiemy, że \(0 \le r < b\). Kluczowym spostrzeżeniem jest, że każdy wspólny dzielnik liczb \(a\) i \(b\) musi być wspólnym dzielnikiem liczb \(b\) i \(r\) (i na odwrót). Innymi słowy \(NWD(a,b) = NWD(b,r)\). Zatem nasze poszukiwania \(NWD\) możemy kontynuować dla pary liczb \(b\) i \(r\), przy czym rolę \(a\) pełni teraz \(b\), a rolę \(b\) reszta \(r\). Widać, że za każdym razem drugi element pary maleje, ale zawsze jest nie mniejszy od zera. Tak więc po wykonaniu skończonej liczby opisanych kroków znajdziemy poszukiwany największy wspólny dzielnik. Można wykazać, że liczba tych kroków nigdy nie przekroczy \(2\log_2(a+b)\). Oto funkcja w C++ będąca realizacją opisanej idei:

int NWD(int a, int b) {
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

Oto przykład działania tej funkcji:

\(a\)	\(b\)	\(r\)
24	42	24
42	24	18
24	18	6
18	6	0

Raz napisana poprawnie funkcja może być wykorzystana w innych algorytmach. Możemy być wtedy pewni, że jeżeli pozostała część algorytmu jest poprawna, to cały algorytm będzie poprawny. Funkcję \(NWD\) wykorzystamy do napisania funkcji obliczającej najmniejszą wspólną wielokrotność dwóch liczb całkowitych dodatnich. Najmniejszą wspólną wielokrotnością dodatnich liczb całkowitych \(a\), \(b\) nazywamy najmniejszą dodatnią liczbę całkowitą \(w\), którą dzielą bez reszty \(a\) i \(b\). Liczbę \(w\) oznaczamy przez \(NWW(a,b)\). Zauważmy, że jako wielokrotność \(a\) i \(b\) moglibyśmy wziąć ich iloczyn \(a \cdot b\). Może to nie być najmniejsza wspólna wielokrotność, gdyż każdy dzielnik \(a\) i \(b\) występuje w tym iloczynie dwukrotnie, tzn. w kwadracie. Aby uniknąć tych powtórzeń, wystarczy podzielić iloczyn przez \(NWD(a,b)\). Otrzymujemy bardzo prostą funkcję:

int NWW(int a, int b) {
    return a * b / NWD(a, b);
}

Na koniec napiszemy funkcje, których celem jest wykonywanie operacji arytmetycznych na dwóch ułamkach zwykłych. Ułamek zwykły składa się z trzech elementów: licznika, mianownika i kreski ułamkowej symbolizującej znak dzielenia. Licznik i mianownik są liczbami całkowitymi. Jeśli ułamek jest ujemny, to przyjmujemy, że licznik jest ujemny, a mianownik dodatni. Mianownik nigdy nie może być równy zero. Będziemy zawsze żądali, żeby nasze ułamki były nieskracalne, tzn. żeby największym wspólnym dzielnikiem licznika i mianownika było zawsze 1. Przypomnijmy sobie podstawowe operacje na ułamkach:

\(\frac{a}{b} + \frac{c}{d} = \frac{a \cdot d + b \cdot c}{b \cdot d}\), \(\frac{a}{b} - \frac{c}{d} = \frac{a \cdot d - b \cdot c}{b \cdot d}\)

Zauważmy w tym miejscu, że odejmowanie dwóch ułamków można wyrazić przy pomocy dodawania: \(\frac{a}{b} - \frac{c}{d} = \frac{a}{b} + \frac{-c}{d}\).

\(\frac{a}{b} \cdot \frac{c}{d} = \frac{a \cdot c}{b \cdot d}\), \(\frac{a}{b} : \frac{c}{d} = \frac{a \cdot d}{b \cdot c}\). Uwaga: przy dzieleniu \(c \ne 0\)!

Naszym celem będzie napisanie czterech funkcji Suma, Roznica, Iloczyn, Iloraz, których zadaniem jest wykonywanie operacji na ułamkach, odpowiednio, +, -, * i :. W tym materiale napiszemy i omówimy tylko funkcje Suma i Roznica, napisanie pozostałych pozostawiamy Czytelnikowi.

Przede wszystkim musimy zdecydować, w jaki sposób będziemy reprezentowali ułamki zwykłe. Żeby określić ułamek zwykły wystarczy znać jego licznik i mianownik. Wiemy już, że język C++ pozwala grupować powiązane logicznie zmienne w struktury (typ struct). W naszym przypadku użyjemy struktury:

struct ulamek {
    int licznik, mianownik;
};

Możemy już przystąpić do napisania funkcji Suma. Funkcja Suma będzie miała dwa argumenty typu ulamek. Jej wynikiem będzie ułamek będący sumą argumentów. Ponieważ wynik ma być ułamkiem nieskracalnym, do skrócenia licznika i mianownika użyjemy funkcji \(NWD\), pamiętając jednak, że jej argumenty muszą być dodatnie. Oto stosowna funkcja.

ulamek Suma(ulamek u1, ulamek u2) {
    ulamek w; // ułamek wynikowy
    w.licznik = u1.licznik * u2.mianownik + u2.licznik * u1.mianownik;
    w.mianownik = u1.mianownik * u2.mianownik;
    //skracanie ułamka wynikowego
    if (w.licznik == 0)
        w.mianownik = 1;
    else {
        int x; // zmienna pomocnicza do obliczania NWD
        if (w.licznik < 0)
            x = NWD(-w.licznik, w.mianownik);
        else
            x = NWD(w.licznik, w.mianownik);
        w.licznik /= x;
        w.mianownik /= x;
    }
    return w;
}

Jeśli dobrze napiszemy jedną funkcję, to inne można łatwo przez nią wyrazić. Poniżej wyrażamy funkcję Roznica za pomocą funkcji Suma.

ulamek Roznica(ulamek u1, ulamek u2) {
    u2.licznik = -u2.licznik;
    return Suma(u1, u2);
}

Jako zadanie do domu spróbuj napisać funkcje Iloczyn i Iloraz.

W większości pętli, które dotychczas pisaliśmy, pojawiały się instrukcje i++ lub i--. W języku C++ dostępne są także instrukcje ++i oraz --i. Czym one się różnią od tych wcześniejszych?

Aby to zrozumieć, trzeba wiedzieć, że każde przypisanie ma w języku C++ wartość. Wartością tą jest prawa strona przypisania. A zatem przypisanie możemy traktować jako funkcję zwracającą wynik przypisania. Przykładowo, wskutek wykonania instrukcji:

int a, b, c;
a = b = c = 1;

wszystkie trzy zmienne uzyskują wartość \(1\). Działa to tak, że najpierw zmiennej \(c\) przypisujemy wartość 1. Wynikiem przypisania \(c=1\) jest prawa strona, czyli \(1\), i w przypisaniu \(b=(c=1)\) zmienna \(b\) uzyskuje wartość \(1\) (w powyższym wyrażeniu mogliśmy pominąć nawiasy). Na końcu to samo dzieje się ze zmienną \(a\).

Tak samo jak zwykłe przypisanie, również przypisania skrócone zwracają pewną wartość. Jaka to wartość? Otóż taka sama, jak gdyby zamiast przypisania skróconego wpisać równoważne mu pełne przypisanie. Poniższy program:

int a, b;
b = 7;
a = b += 7;

działa więc tak samo jak:

int a, b;
b = 7;
a = b = b + 7;

czyli po jego wykonaniu każda ze zmiennych \(a\), \(b\) ma wartość 14.

Wyjątkiem od tej reguły są wspomniane na wstępie instrukcje zwiększania i zmniejszania zmiennej o jeden. Instrukcja ++i działa dokładnie tak jak i+=1: zwiększa \(i\) o 1 i w wyniku daje rzeczywiście nową wartość. Natomiast instrukcja i++ również zwiększa \(i\) o 1, ale w wyniku daje starą (niezwiększoną) wartość zmiennej \(i\). Podobnie sprawa ma się z instrukcjami --i oraz i--.

Których z tych instrukcji warto zatem używać? Jeśli po prostu chcemy zwiększyć (lub zmniejszyć) wartość zmiennej o 1, obie instrukcje działają tak samo, jednak instrukcja i++ (odpowiednio i--) jest trochę mniej efektywna, a to dlatego, że musi przechowywać choć przez chwilę zarówno starą, jak i nową wartość zmiennej. Dlatego w pętlach takich jak dotychczas lepiej jest stosować instrukcje ++i i --i. Natomiast są pewne sytuacje, w których instrukcje i++ i i-- mogą być wygodne w użyciu. Przykładowo, poniższy program oblicza dokładnie wartość \(2^n\), bez konieczności używania dodatkowej zmiennej sterującej \(i\):

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int pot2 = 1;
    while (n--)
        pot2 *= 2;
    cout << pot2 << endl;
}

Aby zrozumieć, dlaczego tak jest, trzeba wiedzieć, że warunki występujące w instrukcji if czy pętli while mogą w C++ być także typu całkowitego. Wartość 0 interpretowana jest jako fałsz, a dowolna niezerowa (dodatnia lub ujemna) wartość jako prawda. Jeśli wczytamy \(n=10\), to wartości \(n\) będą maleć od 10 aż do 0. Gdy \(n=1\), pętla wykona się po raz ostatni (dziesiąty), gdyż wartością n-- będzie wtedy wciąż 1.

Dobrym przykładem na wykorzystanie tej ostatniej sztuczki jest też krótszy zapis warunku, że liczba \(a\) nie jest podzielna przez liczbę \(b\):

if (a % b) // to samo co: if (a % b != 0)
    ....

Po przeczytaniu tej sekcji możesz mieć poczucie, że wprowadzone tu elementy języka C++ bardziej utrudniają pisanie i rozumienie programów, niż je ułatwiają. To po części prawda – program najeżony różnymi takimi sprytnymi instrukcjami może być kompletnie nieczytelny. Jednak rozsądne używanie instrukcji takich jak powyżej może czasami przyczynić się do krótszego zapisu niektórych elementów programów i tak naprawdę zwiększyć jego czytelność. Wszystko zależy tu od wyczucia.