Efektywność programów

Część programistyczna: Wybrane elementy języka C++

W części programistycznej omawiamy jeszcze trzy elementy języka C++, które nie pojawiły się wcześniej w kursie, a o istnieniu których po prostu warto wiedzieć. Są to także ostatnie brakujące elementy potrzebne do rozpoczęcia pracy w kursie algorytmiki. Komentarz do lekcji i część techniczna są poświęcone tematyce efektywności algorytmów i programów. Tę lekcję można więc traktować jako paszport do świata algorytmiki.

Typ rzeczywisty double

Zobacz tekst nagrania

Pierwszym z elementów będą liczby rzeczywiste. Napiszemy program, który wczytuje kwotę pieniędzy i oprocentowanie lokaty w skali roku i wypisze kwotę, jaka po roku będzie znajdować się na lokacie. Do rozwiązania tego zadania użyjemy typu rzeczywistego double. Liczby rzeczywiste w C++ zapisujemy w formie ułamków dziesiętnych, a część całkowitą i ułamkową rozdzielamy kropką dziesiętną (a nie przecinkiem!).

#include <iostream>

using namespace std;

int main() {
    double kwota, procent;
    cin >> kwota >> procent;
    cout << kwota + kwota * procent / 100.0 << endl;
}

Dla kwoty 100 zł i oprocentowania 4% wynikiem programu jest 104 zł, a dla kwoty 123 zł i oprocentowania 3.5% wynik to 127.305 zł.

Przy wypisywaniu liczb rzeczywistych dobrze jest określić, ile cyfr po kropce chcemy wypisać. Liczba zostanie wtedy zaokrąglona do tylu cyfr po kropce. W tym celu trzeba dołączyć plik nagłówkowy iomanip, służący do manipulowania wyjściem. Funkcja setprecision ustawia liczbę cyfr dziesiętnych do wypisania – w przypadku kwoty w złotówkach będą to dwie cyfry po kropce. Jeśli nie podamy liczby cyfr, które chcemy, by program wypisał po przecinku, domyślnie wypisywane jest maksymalnie 6 cyfr, wliczając cyfry przed kropką dziesiętną, a jeśli przy tym liczba przekroczy 6 cyfr, zostanie wypisana w tzw. notacji naukowej, której znaczenia tutaj nie będziemy wyjaśniać.

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    double kwota, procent;
    cin >> kwota >> procent;
    cout << setprecision(2) << fixed;
    cout << kwota + kwota * procent / 100.0 << endl;
}

Uwaga: Zwracamy uwagę na konieczność użycia słówka fixed. Bez niego liczba podana w funkcji setprecision będzie traktowana jako łączna liczba cyfr do wypisania, wraz z cyframi przed kropką.

Na liczbach rzeczywistych można wykonywać standardowe działania dodawania, odejmowania, mnożenia oraz dzielenia "/". Oprócz tego dostępnych jest wiele funkcji matematycznych, takich jak pierwiastek kwadratowy ( sqrt), podnoszenie do danej potęgi ( pow(liczba,wykładnik)), funkcje trygonometryczne ( sin, cos, tan), wartość bezwzględna ( abs), całość z liczby ( floor), zaokrąglenie do najbliższej liczby całkowitej ( round), logarytm dwójkowy, dziesiętny i naturalny ( log2, log10, log) itd. Wszystkie te funkcje są dostępne w pliku nagłówkowym cmath.

Jako skromną ilustrację tych możliwości języka C++ napiszmy program, który oblicza długość przeciwprostokątnej trójkąta prostokątnego na podstawie długości przyprostokątnych z twierdzenia Pitagorasa i wypisuje wynik z pięcioma cyframi po kropce. Pamiętajmy, że oprócz cmath wciąż musimy dołączyć plik nagłówkowy iomanip.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    double a, b;
    cin >> a >> b;
    cout << setprecision(5) << fixed;
    cout << sqrt(a * a + b * b) << endl;
}

W komputerze nie ma możliwości przechowywać nieskończenie wielu cyfr po przecinku, dlatego każda liczba rzeczywista jest pamiętana z pewnym przybliżeniem – a zatem najmniej ważne cyfry w zapisie mogą zostać pominięte. W obliczenia na liczbach rzeczywistych wkradają się zatem bardzo drobne błędy, które wraz z wykonywaniem kolejnych obliczeń mogą się nawarstwiać. Dobre rozumienie reprezentacji liczb rzeczywistych w komputerze, zakresów typów rzeczywistych oraz błędów przybliżeń wymaga pewnego doświadczenia. Dlatego na początkowym etapie nauki programowania, na którym się obecnie znajdujesz, mamy dla Ciebie bardzo prostą radę: używaj liczb rzeczywistych w swoich programach tylko, jeśli są one konieczne.

Tablice dwuwymiarowe

Zobacz tekst nagrania

Czasem dane do programu występują w naturalny sposób w formie tabelki. Wtedy do ich przechowywania można użyć tablicy dwuwymiarowej. Taką tablicę deklaruje się podobnie do tablicy jednowymiarowej:

int t[100][100];

Elementy tej tablicy wyglądają tak: \(t[i][j]\) dla \(i\) i \(j\) od 0 do 99 włącznie.

Jako przykład rozważmy wyniki sprawdzianu w danej klasie: dla każdego ucznia wiemy, ile punktów uzyskał za każde zadanie. Powiedzmy, że mamy \(n\) uczniów i \(m\) zadań. Dla \(n=3\) i \(m=4\) dane do programu wyglądają tak:

3 4
2 0 5 1
3 3 1 4
0 0 5 5

Wtedy te dane możemy umieścić w tablicy dwuwymiarowej za pomocą zagnieżdżonych pętli for:

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int spr[n][m];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> spr[i][j];
}

Czyli dla tych danych mamy \(spr[0][0]=2\), \(spr[0][1]=0\), \(spr[0][2]=5\), \(spr[0][3]=1\), dalej \(spr[1][0]=3\), \(spr[1][1]=3\) itd.

Gdy już wczytamy takie dane, możemy dla każdego z uczniów obliczyć sumę punktów ze sprawdzianu:

    for (int i = 0; i < n; ++i) {
        int suma = 0;
        for (int j = 0; j < m; ++j)
            suma += spr[i][j];
        cout << suma << endl;
    }

Podobnie, dla każdego z zadań możemy obliczyć średni wynik uczniów z tego zadania:

    cout << endl;
    cout << setprecision(2) << fixed;
    for (int i = 0; i < m; ++i) {
        int suma = 0;
        for (int j = 0; j < n; ++j)
            suma += spr[j][i];
        cout << double(suma) / n << endl;
    }

Wynikiem tego programu dla danych powyżej jest

8
11
10

1.67
1.00
3.67
3.33

W C++ podobnie jak tablice dwuwymiarowe zachowują się tablice napisów, czyli tablice elementów typu string. Tutaj również mamy podwójne indeksy służące do dostępu do pojedynczych znaków napisów.

Zilustrujemy to sympatycznym przykładem szachowym. Wieża w szachach to figura, która atakuje wszystkie pola znajdujące się w tym samym wierszu i w tej samej kolumnie co ona. Napiszemy program, który wczyta zawartość szachownicy \(n imes n\), na której znajduje się pewna liczba wież, i wypisze TAK, jeśli jakiekolwiek dwie wieże na tej szachownicy atakują się, a NIE w przeciwnym przypadku. Przykładowo, dla danych:

4
..W.
W...
....
...W

odpowiedzią jest NIE, a dla danych:

4
..W.
W...
..W.
...W

odpowiedź brzmi TAK.

Oto program. Zauważ, że napisy wczytuje się inaczej niż tablice (prościej).

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int n;
    cin >> n;
    string szach[n];
    for (int i = 0; i < n; ++i)
        cin >> szach[i];
    bool atak = false;

    for (int i = 0; i < n; ++i) {
        int ile = 0;
        for (int j = 0; j < n; ++j)
            if (szach[i][j] == 'W')
                ++ile;
        if (ile > 1)
            atak = true;
    }

    for (int i = 0; i < n; ++i) {
        int ile = 0;
        for (int j = 0; j < n; ++j)
            if (szach[j][i] == 'W')
                ++ile;
        if (ile > 1)
            atak = true;
    }

    if (atak)
        cout << "TAK" << endl;
    else
        cout << "NIE" << endl;
}

W programie tym nie udało nam się uniknąć przykrego przeklejania dłuższego fragmentu kodu. Jest to zjawisko niepożądane, gdyż łatwo w ten sposób wprowadzić do programu jakąś usterkę: albo zapominając zmienić coś w trakcie przeklejania, albo też później, gdy poprawiamy pierwszy fragment programu, a zapomnimy to samo poprawić w drugim. Aby tego uniknąć, możemy tu napisać funkcję sprawdzającą, czy w którymś wierszu jakieś dwie wieże atakują się. Następnie możemy wywołać tę funkcję dwukrotnie, a między jej wywołaniami odbić całą szachownicę symetrycznie względem przekątnej. Szczegóły analizy tego programu pozostawiamy uczestnikom kursu.

#include <iostream>
#include <algorithm>
using namespace std;

int n;
string szach[1000];

bool czy_szach() {
    for (int i = 0; i < n; ++i) {
        int ile = 0;
        for (int j = 0; j < n; ++j)
            if (szach[i][j] == 'W')
                ++ile;
        if (ile > 1)
            return true;
    }
    return false;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> szach[i];
    bool atak = czy_szach();

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            swap(szach[i][j], szach[j][i]);

    atak = atak || czy_szach();

    if (atak)
        cout << "TAK" << endl;
    else
        cout << "NIE" << endl;
}

Pętla do while

Na koniec króciutko omówimy brakującą do kompletu pętlę do while. Podobnie jak pętla while, ta pętla również składa się z warunku i instrukcji, tylko zapisanych na odwrót:

do
    instrukcja;
while (warunek);

Rzeczywiście, w działaniu pętla ta różni się tym od pętli while, że tutaj najpierw wykonujemy instrukcję, a dopiero później sprawdzamy warunek. Kontynuujemy działanie tak długo, jak długo warunek w momencie sprawdzenia jest prawdziwy. W szczególności oznacza to, że w tej pętli instrukcja zawsze wykona się co najmniej raz.

Jako prosty przykład napiszemy program, który z wejścia wczytuje liczby całkowite aż do napotkania zera i sumuje je. Ten program widzieliśmy już wcześniej przy okazji pętli while, jednak napisany za pomocą tej nowej pętli wychodzi nieco krótszy.

#include <iostream>
using namespace std;

int main() {
    int suma = 0;
    do {
        int a;
        cin >> a;
        suma += a;
    } while (a != 0);
    cout << suma << endl;
}

Pętlę do while można zastosować właściwie wszędzie tam, gdzie pętli while. Tylko od wygody programisty zależy, której z tych pętli postanowi w danym miejscu użyć.

Komentarz: Złożoność czasowa

Komputery niewątpliwie potrafią liczyć szybciej niż ludzie, ale tylko wtedy, gdy ludzie je odpowiednio zaprogramują. Gdybyśmy jednak zlecili komputerowi pracę do wykonania, a na odpowiedź czekali wieki, to komputer okazałby się bezużyteczny. Dlatego algorytmicy starają się projektować nowe algorytmy lub usprawniać istniejące tak, żeby ich czas wykonywania przez komputer był jak najkrótszy. Czasami jest to jednak niemożliwe, ponieważ rozwiązywany problem algorytmiczny ze swojej natury nie da się szybko rozwiązać, nawet na coraz to szybszych komputerach. Więcej, istnieją problemy, które wydają się bardzo naturalne do rozwiązania przez komputer, ale o których wiadomo, że do ich rozwiązania komputer jest "za głupi". Żeby zrozumieć wagę projektowania "szybkich" algorytmów rozważmy raz jeszcze zadanie o wieżach Hanoi z pierwszej lekcji.

Zobacz tekst nagrania

Na ziemi wytyczono niewielkie koło, na jego obwodzie umieszczono trzy kołki. Na jeden z nich nałożono płaskie klocki w kształcie pierścieni. Każdy pierścień ma inną średnicę. Pierścienie zostały nałożone w kolejności od największego (na spodzie) do najmniejszego (na wierzchu). Pierścienie można przekładać z kołka na kołek, ale tylko pojedynczo, i nie wolno kłaść większego pierścienia na mniejszy. Przy tych ograniczeniach należy przełożyć wszystkie pierścienie na inny kołek (którykolwiek).

Algorytm

1. Usiądź wewnątrz koła.
2. Przenieś najmniejszy pierścień o jeden kołek w prawo.
3. Dopóki wszystkie pierścienie nie znajdą się na jednym kołku: 3.1 Wykonaj jedyne możliwe przeniesienie bez ruszania najmniejszego pierścienia; innymi słowy, przenieś mniejszy z pierścieni znajdujących się na wierzchach kołków niezawierających najmniejszego pierścienia na drugi z tych kołków. 3.2 Przenieś najmniejszy pierścień o jeden kołek w prawo.

Załóżmy, że mamy do przeniesienia \(n > 0\) pierścieni. Przyjmijmy, że jeden ruch w naszym algorytmie polega na przełożeniu jednego pierścienia pomiędzy wieżami. Ilu ruchów potrzebuje nasz algorytm do przełożenia wszystkich pierścieni? Oznaczmy liczbę wszystkich ruchów przez \(T(n)\). Jeśli mamy tylko jeden pierścień (\(n = 1\)), wystarczy tylko 1 ruch. Jeżeli \(n > 1\), to musimy najpierw przenieść \(n-1\) najmniejszych pierścieni w celu uwolnienia największego pierścienia. Na to potrzeba \(T(n-1)\) ruchów. Potem w jednym ruchu przenosimy największy pierścień, a na koniec musimy przenieść na wieżę z największym pierścieniem \(n-1\) najmniejszych pierścieni – znowu \(T(n-1)\) ruchów. Zatem liczbę ruchów wykonywanych przez nasz algorytm można wyrazić następującym układem równań:

\(T(1) = 1\); \(T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) +1\).

Nietrudno wykazać, że \(T(n) = 2^n - 1\). Dlaczego?

\(T(1) = 2^1 - 1 = 2 - 1 = 1\);

\(T(n) = 2 \cdot (2^{n-1} - 1) + 1 = 2\cdot 2^{n-1} - 2 + 1 = 2^n - 1\).

Legenda głosi, że mnisi w Tybecie mają do przełożenia 64 pierścienie i gdy je wszystkie przełożą, nastąpi koniec świata. Jeśli wykonanie jednego ruchu zabiera sekundę, to przełożenie wszystkich pierścieni zajęłoby \(2^{64}-1 = 18\,446\,744\,073\,709\,551\,615\) (ponad 18 trylionów) sekund, czyli około 584 miliardów lat.

Załóżmy teraz, że dany jest numer ruchu \(r\), \(0 \le r \le 2^n - 1\). Jak wygląda konfiguracja pierścieni na wieżach zaraz po wykonaniu ruchu o numerze \(r\)? Oczywiście moglibyśmy poprosić mnichów o wykonanie \(r\) ruchów naszego algorytmu i dostać pożądaną konfigurację, ale na odpowiedź moglibyśmy się nie doczekać do końca naszego życia. Czy jednak rzeczywiście musimy prosić mnichów o pomoc? Spróbujemy zaprojektować \u201cszybki\u201d algorytm, który pozwoli nam obliczyć pożądaną konfigurację. Żeby to jednak zrobić musimy dokładniej sprecyzować nasze zadanie. Przyjmijmy, że wieże są ponumerowane 0, 1 i 2. Na początku \(n\) pierścieni znajduje się na wieży o numerze 0. Kolejną wieżą w kierunku ruchu wskazówek zegara jest wieża o numerze 1, a następnie wieża o numerze 2. Przyjmijmy też, że pierścienie są ponumerowane od 1 do \(n\). Najmniejszym pierścieniem jest pierścień o numerze 1, pierścień o kolejnym rozmiarze ma numer 2, itd. aż do największego pierścienia, który będzie miał numer \(n\). Naszym celem będzie wyznaczenie dla każdego pierścienia numeru wieży, na której będzie się on znajdował po wykonaniu ruchu o numerze \(r\). Oto dokładna specyfikacja problemu:

Dane

Liczba całkowita \(r\), \(0 \le r \le 2^n - 1\).

Wynik

Tablica liczb całkowitych \(wieza[0..n+1]\) taka, że \(wieza[i]\) to numer wieży, na której znajduje się pierścień o numerze \(i\) po wykonaniu ruchu \(r\).

W celu zaprojektowania naszego algorytmu wygodnie będzie prześledzić jego wykonanie dla \(n = 5\). Dla każdego ruchu zapiszemy, który pierścień jest przemieszczany w tym ruch oraz w jakim kierunku: znak '+' oznaczać będzie, że zgodnie z ruchem wskazówek zegara, natomiast znak '-' że przeciwnie do ruchu wskazówek zegara.

r	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
pierścień	1	2	1	3	1	2	1	4	1	2	1	3	1	2	1	5
kierunek	+	-	+	+	+	-	+	-	+	-	+	+	+	-	+	+

r	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
pierścień	1	2	1	3	1	2	1	4	1	2	1	3	1	2	1
kierunek	+	-	+	+	+	-	+	-	+	-	+	+	+	-	+

Co możemy zaobserwować?

• Na początku, przed wykonaniem pierwszego ruchu, wszystkie pierścienie znajdują się na wieży o numerze 0.
• Pierścień o numerze \(i\) jest przemieszczany po raz pierwszy w ruchu o numerze \(2^{i-1}\), a następnie co \(2^i\) ruchów, czyli że pierścień o numerze 1 co 2 ruchy, pierścień o numerze 2 co 4 ruchy, pierścień o numerze 3 co 8 ruchów, itd.
• Pierścienie o numerach nieparzystych wędrują zgodnie z ruchem wskazówek zegara, natomiast pierścienie o numerach parzystych przeciwnie do ruchu skazówek zegara.

Wiedząc to wszystko, łatwo już obliczyć numer wieży, na której znajdzie się pierścień o numerze \(i\) po wykonaniu \(r\) ruchów. Jeśli \(r<2^{i-1}\), pierścień ani razu nie został ruszony, więc znajduje się on wciąż na wieży 0. W przeciwnym razie pierścień został ruszony

\(1 + (r-2^{i-1})/2^i\)

razy, gdzie "/" oznacza dzielenie bez reszty. Przy tym, jeśli to był pierścień o numerze nieparzystym, to wędrował po kolejnych wieżach 0, 1, 2, 0, 1, 2, ..., a zatem znajduje się on teraz na wieży o numerze \(k % 3\) (reszta z dzielenia). W przeciwnym razie znajduje się na wieży o numerze \(3- k % 3\), modulo 3.

Zauważmy, że w tym algorytmie dla każdego pierścienia wykonujemy stałą liczbę operacji arytmetycznych, zatem łączna liczba operacji arytmetycznych będzie "proporcjonalna" do liczby pierścieni, która jest dużo mniejsza niż możliwa liczba ruchów.

Oto pełny program rozwiązujący nasze zadanie. Za obliczanie konfiguracji po \(r\) ruchach jest odpowiedzialna funkcja pozycja_hanoi, w której dodatkowo zadbaliśmy o ładne wypisywanie konfiguracji na poszczególnych wieżach. Wyodrębnienie tego fragmentu kodu w postaci funkcji pozwala np. przetestować działanie programu w pętli dla \(n=5\) i \(r=0,\ldots,31\).

#include <iostream>
using namespace std;

void pozycja_hanoi(int n, unsigned long long r) {
    int wieza[n + 1]; // konfiguracja pierścieni po r ruchach

    unsigned long long potega_2 = 1;
    for (int i = 1; i <= n; ++i) {
        if (r < potega_2) // potega_2 == 2^(i-1)
            wieza[i] = 0;
        else {
            unsigned long long k = 1 + (r - potega_2) / (2 * potega_2);
            if (i % 2 == 1)
                wieza[i] = k % 3;
            else
                wieza[i] = (3 - k % 3) % 3;
        }
        potega_2 *= 2;
    }

    // na koniec zadbajmy o ładne wypisywanie
    for (int w = 0; w < 3; ++w) {
        cout << w << ": ";
        for (int i = n; i >= 1; --i)
            if (wieza[i] == w)
                cout << i << " ";
        cout << endl;
    }
}

int main() {
    int n; // liczba pierścieni, n <= 63
    cin >> n;
    unsigned long long r; // liczba ruchów
    cin >> r;
    pozycja_hanoi(n, r);
}

Przykładowo, dla \(n=5\) i \(r=6\) wynikiem programu jest:

0: 5 4 1
1: 3 2
2:

Część techniczna: Wydajność programów

Przy rozwiązywaniu różnych problemów informatycznych zazwyczaj znamy jakieś ograniczenia na wielkość danych wejściowych. W treściach zadań kursu zawsze podajemy, z jak dużymi liczbami program musi sobie poradzić, jak długie mogą być napisy na wejściu itp. Pozwala nam to dobrać odpowiednie typy do przechowywania danych czy np. ustawić odpowiedni rozmiar tablic. Jednak ograniczenia te powinniśmy wziąć pod uwagę również pod kątem tego, czy nasz program będzie dostatecznie efektywny. Kontynuujemy tutaj temat rozpoczęty w Komentarzu pod kątem praktycznym.

Zobacz tekst nagrania

Powiedzmy, że mamy napisać program, który wczytuje liczbę naturalną \(n\) i wypisuje sumę liczb całkowitych od 1 do \(n\). Taki program pisaliśmy już w lekcji 6:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int suma = 0;
    for (int i = 1; i <= n; ++i)
        suma += i;
    cout << suma << endl;
}

Gdy uruchomimy nasz program kolejno dla \(n=100,1000,10\,000\), otrzymujemy następujące wyniki:

5050
500500
50005000

Gdy na wejściu podamy \(n=100\,000\), wynik programu może nas zaniepokoić:

705082704

Liczba wynikowa wyszła tu mniej "okrągła" niż poprzednio. Rzeczywiście, gdy uruchomimy nasz program dla \(n=200\,000\), otrzymamy wynik:

-1474736480

sugerujący, że w obliczeniach doszło do przekroczenia zakresu zmiennej \(suma\). Łatwo to poprawić, zmieniając typ zmiennej \(suma\) .

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long suma = 0;
    for (int i = 1; i <= n; ++i)
        suma += i;
    cout << suma << endl;
}

Teraz dla \(n=100\,000\) mamy już dużo sensowniejszy wynik:

5000050000

A co się stanie, gdy temu programowi podamy na wejściu \(n=1\,000\,000\,000\)? Wówczas też otrzymamy sensowny wynik, ale program będzie już działał zauważalnie długo (u nas kilka sekund). To dlatego, że aby obliczyć wynik, program musi wykonać aż \(n\) dodawań. Zauważmy, że wykonanie miliarda dodawań zajmuje komputerowi zaledwie kilka sekund! Jeśli jednak rozwiązywalibyśmy takie zadanie w MAIN 2 i autor zadania ustawiłby limit czasu działania programu na sekundę, zapewne program działałby za długo, co objawiłoby się komunikatem: "Przekroczenie limitu czasu".

Okazuje się, że ten sam wynik można otrzymać dużo szybciej. Jeśli \(n\) jest parzyste, robimy to tak:

 1  +  2  + ... +  n/2
 n  + n-1 + ... + n/2+1
=======================
n+1 + n+1 + ... +  n+1 = (n+1)*n/2

Pewna znana anegdota głosi, że pewien nauczyciel matematyki w szkole podstawowej zlecił wszystkim uczniom klasy obliczenie sumy liczb od 1 do 100, aby mieć chwilę spokoju od lekcji. Tymczasem jeden z uczniów praktycznie natychmiast obliczył tę sumę, właśnie podanym wyżej sposobem, wprawiając nauczyciela w zdziwienie (i zapewne zakłopotanie). Według anegdoty uczniem tym był późniejszy wielki matematyk, Carl Friedrich Gauss.

Szczęśliwie otrzymany wzór działa także dla \(n\) nieparzystych, a do jego obliczenia wystarczy wykonać zaledwie kilka działań (zamiast miliarda działań jak poprzednio). Otrzymujemy następujący program, który kończy się błyskawicznie.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << (long long)(n + 1) * n / 2 << endl;
}

Ponieważ wynik musimy przechowywać w typie long long, przy jego obliczaniu używamy rzutowania typu int na long long. Warto tu zauważyć dwie rzeczy: (1) nazwa typu long long składa się z dwóch słów, więc trzeba było umieścić ją w nawiasie przy rzutowaniu; (2) przy obliczaniu iloczynu wystarczyło tylko jeden czynnik zrzutować na typ long long, a już całe wyrażenie obliczyło się w typie long long.

A co by było, gdyby ograniczeniem górnym na \(n\) było, powiedzmy, \(10^{12}\) albo \(10^{18}\)? Wówczas wzór działałby równie szybko jak wcześniej, tylko nie mielibyśmy do dyspozycji żadnego typu danych w C++, w którym zmieściłby się wynik. A co jeśli jednak koniecznie musielibyśmy napisać taki program? Podpowiedź, jak sobie z tym poradzić, daje zadanie 3 z poprzedniej lekcji.

I jeszcze drugi przykład. Przypomnijmy program z funkcją sprawdzającą, czy dana liczba naturalna jest liczbą pierwszą. Od razu przedstawmy go w wersji wykonującej wszystkie obliczenia w typie long long.

#include <iostream>
using namespace std;

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

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

Jak szybki jest ten program? Widzimy, że podobnie jak poprzednio wykonywanych tu z grubsza \(n\) operacji. Tym razem są to dzielenia. A zatem moglibyśmy się spodziewać, że dla \(n=1\,000\,000\,000\) program też będzie działać zauważalnie wolno. Tymczasem, gdy uruchomimy go dla takich danych, program działa natychmiastowo! Podobnie rzecz ma się, gdy \(n=10^{12}\) lub jest jeszcze większe. Jest tak dlatego, że gdy tylko program znajdzie jakiś dzielnik liczby \(n\), instrukcja return powoduje natychmiastowe przerwanie pętli for i program kończy się. Dla wszystkich wprowadzonych danych takim dzielnikiem było już \(i=2\).

Dużo inaczej sprawa wygląda, gdy np. takiego dzielnika w ogóle nie ma, czyli liczba \(n\) jest liczbą pierwszą. Wówczas dzielnie wykonamy wszystkie obroty pętli dla \(i=2,\ldots,n-1\). Gdy uruchomimy nasz program dla liczby \(n=1\,000\,000\,007\), która już jest liczbą pierwszą, na wynik będziemy musieli poczekać kilkanaście sekund. Lepiej nawet nie sprawdzać, ile czasu będzie to trwało dla liczb pierwszych rzędu \(10^{12}\) lub większych.

Czy możemy zatem jakoś usprawnić nasz program? Okazuje się, że tak. Ponadto, możemy do tego wykorzystać funkcję, którą dopiero co poznaliśmy!

Otóż jeśli liczba \(n\) nie jest liczbą pierwszą, to możemy ją przedstawić jako iloczyn dwóch liczb całkowitych różnych od 1. Czasem możemy to zrobić na kilka sposobów, np.:

36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6

Zauważmy jednak, że w każdym takim iloczynie mniejszy czynnik nie przekracza pierwiastka z \(n\). Jest to jasne: gdyby oba czynniki przekraczały \(\sqrt{n}\), to ich iloczyn byłby większy niż \(n\). Stąd wystarczy sprawdzić możliwe dzielniki \(i\) tylko do \(\sqrt{n}\), do obliczenia którego może posłużyć nam funkcja sqrt na liczbach rzeczywistych:

#include <iostream>
#include <cmath>
using namespace std;

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

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

Zauważmy, że teraz do przechowywania zmiennej \(i\) wystarczył nam typ int. Ten program działa już zdecydowanie lepiej, gdyż zamiast \(n\) dzieleń wykonuje ich tylko \(\sqrt{n}\). Przykładowo, \(\sqrt{1\,000\,000\,007} \approx 31\,623\) i rzeczywiście program dla takich danych (a nawet większych danych) działa bardzo szybko.

Uwaga: Pętlę for w powyższym programie można także było zapisać bez używania funkcji sqrt. Jednak do tego celu potrzebna jest pętla for ze sprytniej zapisanym warunkiem:

    for (long long i = 2; i * i <= n; ++i)

Celem tej części technicznej było pokazanie, że efektywność naszych programów może mieć duże znaczenie. Temu, jak pisać szybkie i poprawne programy, poświęcony jest drugi z kursów w MAIN 2, czyli kurs podstaw algorytmiki.

A przy okazji można by zadać sobie pytanie: Po co się ciągle zastanawiać nad tym, jaki typ danych jest potrzebny i jakie wykonać rzutowania, podczas gdy można by po prostu wszędzie używać największego możliwego typu, na przykład zawsze korzystać z typu całkowitego long long? Okazuje się, że mogłoby to mieć niedobre skutki dla efektywności naszych programów, a to z dwóch powodów:

1. Operacje na typie większym niż int są wykonywane wolniej niż na typie int. Nasz początkowy program z funkcją czy_pierwsza, zapisany z użyciem typu int, dla \(n=1\,000\,000\,007\) działa ze dwa razy szybciej niż ten sam program używający typu long long. (Ta uwaga niekoniecznie oznacza, że obliczenia na typie mniejszym niż int są zawsze szybsze niż obliczenia na typie int. Jest tak akurat dlatego, że typ int jest wygodny do obliczeń dla komputera.)
2. Różnica jest też widoczna w przypadku przechowywania w programie większej liczby danych, np. w tablicy. Jeśli mamy do zapamiętania milion liczb całkowitych, to w przypadku użycia typu 4-bajtowego int wykorzystamy łącznie \(4\,000\,000\) bajtów pamięci, czyli 4 megabajty (oznaczenie: 4 MB). Natomiast jeśli w tym samym miejscu zastosujemy typ 8-bajtowy long long, wykorzystamy już \(8\,000\,000\) B, czyli 8 MB. Ilość pamięci dostępnej dla rozwiązania danego zadania umieszczamy zawsze w nagłówku treści zadania.

Zadania

Oto kolejne zadania do samodzielnego rozwiązania. W ostatniej lekcji kursu, poświęconej już tylko aplikacjom graficznym, szykujemy dla Was miłą niespodziankę: Quiz. Będzie on złożony z pięciu dosyć prostych zadań, których celem jest podsumowanie materiału kursu. Jeśli nie udało Wam się rozwiązać jakichś wcześniejszych zadań, będziecie to mogli nadgonić w ramach następnej lekcji. Łącznie w kursie wystąpi 30 zadań punktowanych, czyli do zaliczenia kursu i uzyskania certyfikatu wystarczy rozwiązanie 18 zadań.

Koło

Ostatnia cyfra

Dwa markety

Taśma (*)