Kurs: Kurs wstępu do programowania KONKURS

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

Tablice dwuwymiarowe


Zobacz tekst nagrania

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

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

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 przypisane do tej lekcji:
1. Koło
2. Ostatnia cyfra
3. Dwa markety