Notka dziewiąta, w której poznajemy tablice i zamieniamy zmienne miejscami

Zadanie na dzisiaj.

Zadanie 7: Kserokopiarka 2

Przedszkolanka kazała dzieciom na zadanie domowe przynieść listę ich ulubionych liczb.
– Tomku, zapomniałam o zadaniu domowym! – powiedziała Kasia – czy mogłabym spisać liczby od ciebie?
– Dobrze – powiedział Tomek – tylko pozmieniaj trochę, żeby się nie skapnęła.

Wejscie

W pierwszej linijce standardowego wejścia, znajduje się liczba naturalna n (1 ≤ n ≤ 10⁶) oznaczająca liczbę liczb na liście Tomka. W następnych n linijkach, znajdują się liczby a_i spełniające -10⁹ ≤ a_i ≤ 10⁹. Są to liczby na liście Tomka.

Wyjście

Na standardowym wyjściu należy wypisać tę samą listę liczb, w przeciwnej kolejności.

Przykład

Dla danych wejściowych

Poprawnym rozwiązaniem jest

15
14
-3

Ze wszystkich nudnych zadań na świecie. To wydaje mi się najnudniejsze. Ale nauczy nas dwóch ważnych koncepcji w informatyce. Więc fajnie. Ciekawsze zadania umieszczę pod koniec notki.

W notce czwartej rozwiązywaliśmy zadanie “Niech stanie się prostokąt”. Dla przypomnienia, w zadaniu tym należało odpowiedzieć czy da się połamać jeden z trzech patyczków na dwie części w ten sposób, aby dało się ułożyć z nich prostokąt. W zadaniu tym zakładaliśmy, że długości patyczków są podane w kolejności niemalejącej. Rozwiązaniem tego zadania był następujący program:

#include <iostream>

using namespace std;

int main()
{
    int a, b, c;
    
    cin >> a >> b >> c;
    
    if (a + b == c or (a == b and c % 2 == 0) or (b == c and a % 2 == 0))
    {
        cout << "TAK" << endl;
    }
    else
    {
        cout << "NIE" << endl;
    }

    return 0;
}

Czytelnik, który rozwiązywał Zadania do samodzielnego rozwiązywania pod notką siódmą (czyli wszyscy, bo wszyscy moi Czytelnicy sumiennie rozwiązują zadania do samodzielnego rozwiązywania), pewnie dostrzegł, że zadanie Construct a Rectangle z Codeforces, nie posiada założenia o tym, że długości patyczków podawane są w kolejności niemalejącej. Rozwiązanie tej zagadki jest proste. Dodałem to założenie do treści zadania, bo dzięki niemu zadanie jest prostsze. Bez niego, warunek kiedy możemy zbudować prostokąt się komplikuje i wygląda tak:


#include <iostream>

using namespace std;

int main()
{
    int a, b, c;
    
    cin >> a >> b >> c;
    
    if (a + b == c or a + c == b or b + c == a or (a == b and c % 2 == 0) or (b == c and a % 2 == 0) or (a == c and b % 2 == 0))
    {
        cout << "TAK" << endl;
    }
    else
    {
        cout << "NIE" << endl;
    }

    return 0;
}

Wygląda strasznie i nieczytelnie. Gdybyśmy tylko mogli przestawić sobie te zmienne w ten sposób, aby były one ustawione niemalejąco… Hmmm…

Do przestawiania zmiennych miejscami najlepiej nadaje się analogia z krzesełkami w kinie. Wyobraź sobie, że siedzisz w kinie i chcesz się zamienić miejscami ze swoim sąsiadem. Nie możecie oboje wstać i próbować się minąć, bo jest za mało miejsca między rzędami krzesełek. Na szczęście jest jedno wolne miejsce koło was. Taka zagadka. Jak możecie się przesiąść. Rozwiązanie w następnym akapicie.

Aby się przesiąść, jedno z was, załóżmy, że Ty, musi się przesiąść na wolne krzesełko. Następnie twój kolega może się przesiąść na Twoje miejsce a na samym końcu ty możesz się przesiąść na miejsce swojego kolegi.

Jakby ktoś chciał zrobić lepsze rysunki do tej serii, to zapraszam…

W języku C++ wyglądałoby to tak:

int ty = 17;
int kolega = 100;

cout << ty << " " << kolega << endl;

                         // ty = 17  kolega = 100
int puste_miejsce = ty;  // ty = 17  kolega = 100  puste_miejsce = 17
ty = kolega;             // ty = 100 kolega = 100  puste_miejsce = 17
kolega = puste_miejsce;  // ty = 100 kolega = 17   puste_miejsce = 17

cout << ty << " " << kolega << endl;

Program wypisze na ekranie:

17 100
100 17

Zatem zamieniliśmy dwie zmienne ze sobą miejscami. W komentarzach po prawej stronie umieściłem zawartość zmiennych po wykonaniu danej instrukcji.

Istnieją jeszcze dwie metody zamiany ze sobą zmiennych, nie wymagające dodatkowej zmiennej. Są to raczej ciekawostki i nie polecam ich stosowania. Jedna z nich opiera się na dodawaniu i wygląda tak:

int ty = 17;
int kolega = 100

ty = ty + kolega;     // ty = 117 kolega = 100
kolega = ty - kolega; // ty = 117 kolega = 17
ty = ty - kolega;     // ty = 100 kolega = 17

To jest fajne miejsce aby powiedzieć o dwóch koncepcjach programistycznych. Po pierwsze, co się stanie jeśli obie zmienne są duże. W notce szóstej mówiliśmy, że liczby typu int nie mogą być większe niż 2³¹-1. Co się stanie zatem jeśli do zmiennej, która przechowuje taką wartość, dodamy 1? Komputer wybuchnie? Program się wykrzaczy? Otworzymy bramy do Mordoru? Otóż okazuje się, że otrzymamy wartość ujemną! -2³¹ aby być dokładnym. Mówimy, że zmienna się “przekręciła”. Czy to znaczy, że powyższy program nie zamieni dwóch zmiennych miejscami jeśli ich wartości są za duże? Otóż jeśli uruchomicie ten program na dużych wartościach, okaże się że zmienne zostaną zamienione, bo nastąpi ponowne przekręcenie się licznika…. takie “odkręcenie”.

Drugim pojęciem o jakim chciałem powiedzieć przy tej okazji, jest niezdefiniowane zachowanie. Choć powyższy program zadziała wam na komputerze, zadziała na komputerze kolegi i możliwie, że nigdy nie spotkacie się z sytuacją w której ten program nie zadziała… to taka sytuacja jest możliwa. Język C++ bowiem nie precyzuje co się powinno stać gdy do dużej liczby naturalnej dodajemy inną dużą liczbę naturalną. Może się zatem zdarzyć, że dziwne kompilatory na dziwnych komputerach, mogą tak skompilować nasz program, że nie zadziała on z naszą intencją. To jest kolejna rzecz, którą możecie dopisać sobie do listy rzeczy do sprawdzenia w dniu testowym. Co się dzieje, gdy do 2³¹-1 dodamy 1.

Kolejnym trikowym sposobem na zamianę dwóch zmiennych miejscami jest użycie operatora xor (w języku C++ operator ^ oznacza xor, a nie potęgowanie).

int ty = 17;
int kolega = 100;

ty     = ty ^ kolega;
kolega = ty ^ kolega;
ty     = ty ^ kolega;

Zabawny jest ten program, bo trzy razy wykonujemy tę samą (zdawałoby się) instrukcję. Operacji xor przyjrzymy się bliżej, kiedy będziemy mówić o operacjach bitowych. Aby zrozumieć jak działa powyższy kod, wystarczy znać następujące własności operacji xor:

a ^ b = b ^ a (przemienność)
a ^ (b ^ c) = (a ^ b) ^ c (łączność)
0 ^ a = a (zero jest elementem neutralnym operacji xor)
a ^ a = 0 (a to chyba nie ma nazwy).

Pierwsza operacja podstawia pod zmienną ty wartość (17 ^ 100). Kolejna instrukcja podstawia pod zmienną kolega wartość (17^100) ^ 17. Wartość ta jest równa:

(17 ^ 100) ^ 17 = (100 ^ 17) ^ 17 = 100 ^ (17 ^ 17) = 100 ^ 0 = 100

Pierwsza równość wynika z przemienności, druga z łączności, trzecia z własności, która chyba nie ma nazwy, a ostatnia z faktu, że zero jest elementem neutralnym operacji xor. Zatem pod zmienną kolega podstawiliśmy wartość 100. W ostatniej instrukcji podstawiamy pod zmienną ty wartość (17^ 100) ^ 100. Jest to wartość równa:

(17 ^ 100) ^ 100 = 17 ^ (100 ^ 100) = 17 ^ 0 = 17

Zatem wartość ty jest teraz równa 17. Operacja xor, podobnie jak operacja modulo (liczenie reszty z dzielenia) odgrywa zdumiewająco dużą rolę w programowaniu konkursowym.

Wracając do naszego zadania. Możemy teraz poprzestawiać sobie zmienne a, b oraz c w tej sposób, aby stały one w porządku niemalejącym. Robi to poniższy kod.


#include <iostream>

using namespace std;

int main()
{
    int a, b, c, t;
    
    cin >> a >> b >> c;

    if (a > b)
    {
        t = a;
        a = b;
        b = t;
    }

    if (b > c)
    {
        t = b;
        b = c;
        c = t;
    }

    if (a > b)
    {
        t = a;
        a = b;
        b = t;
    }
    
    if (a + b == c or (a == b and c % 2 == 0) or (b == c and a % 2 == 0))
    {
        cout << "TAK" << endl;
    }
    else
    {
        cout << "NIE" << endl;
    }

    return 0;
}

Początkujący programiści mogą mieć problem, aby zapamiętać w jakiej kolejności należy robić przypisania, aby dwie zmienne zamieniły się miejscami. Ja zapamiętuję to w ten sposób, że musimy zacząć od zmiennej tymczasowej (wolnego siedzenia w kinie). Następnie możemy użyć dowolnej z dwóch zmiennych. Np. t = a; Następnie jako pierwsza musi nastąpić zmienna której dopiero co użyliśmy: a = b; i później znów następuje zmienna której dopiero co użyliśmy b = t. Taki łańcuszek powstaje: t a a b b t.

W powyższym kodzie zmienne a oraz b musimy zamienić dwukrotnie ze sobą miejscami, gdyż po zamianie zmiennych b i c, może okazać się, że a jest większe niż b. Dzieje się tak, gdy zmienna c jest najmniejsza z wszystkich trzech. Wszystkie trzy zamiany będziemy musieli wykonać, jeśli dane były podane na wejściu w kolejności malejącej.

Kiedy już wiemy jak zamieniać dwie zmienne miejscami, możemy omówić funkcję swap, która… zamienia dwie zmienne miejscami. Można zapytać więc, czemu uczyliśmy się jak zamieniać dwie zmienne miejscami, skoro w C++ jest funkcja do tego. Wydaje mi się, że niezwykle istotne jest aby wiedzieć jak działa to, czego używamy. Funkcja swap działa w ten sposób, że wykonuje trzy proste przypisania. Co jednak, gdy zmienna to duża baza danych i takie proste przypisania (a więc skopiowanie jednej bazy do innej zmiennej) jest bardzo czasochłonne? Wtedy cała funkcja swap może działać bardzo długo, czego nie wiedzielibyśmy, gdybyśmy nie wiedzieli w jaki sposób działa funkcja swap. Problem ten rozwiązano w C++11 w którym wprowadzono pojęcie wartości wygasających (prędko o nich nie będzie, jeśli w ogóle). Aby móc używać funkcji swap, należy na początku programu dodać #include <algorithm>. Zatem nasz program można napisać krócej:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int a, b, c, t;
    
    cin >> a >> b >> c;

    if (a > b)
    {
        swap(a, b);
    }

    if (b > c)
    {
        swap(b, c);
    }

    if (a > b)
    {
        swap(a, b);
    }
    
    if (a + b == c or (a == b and c % 2 == 0) or (b == c and a % 2 == 0))
    {
        cout << "TAK" << endl;
    }
    else
    {
        cout << "NIE" << endl;
    }

    return 0;
}

Ostatnią rzeczą jaką dziś poznamy, są tablice. Zwróćmy uwagę, że aby rozwiązać dzisiejsze zadanie, musimy najpierw wczytać wszystkie dane z wejścia. Liczb na wejściu może jednak być nawet milion. Potrzebowalibyśmy zatem milion zmiennych aby to uczynić. I tu z pomocą przychodzą tablice. Poniższa instrukcja definiuje tablicę o milionie elementów:

int a[1000000];

int to oczywiście typ tablicy, a to nazwa tablicy, a liczba w kwadratowych nawiasach oznacza ilość elementów w tablicy. Taka tablica to tak jakbyśmy zdefiniowali właśnie milion zmiennych. Pierwsza z nich “ma nazwę” a[0], druga a[1], trzecia a[2], a milionowa a[999999]. Możemy je traktować tak jak traktujemy normalne zmienne:

a[19] = 0;
a[111] = a[2] + a[50];
int n = a[0] * 2;

A nawet lepiej, bo zamiast pisać a[4] = 0; możemy napisać:

a[2+2] = 0;

// albo

int i = 4;
a[i] = 0;

// lub nawet!:

a[0] = 4;
a[a[0]] = 0;

Dzięki takiej konstrukcji, tablice świetnie nadają się w pętli for. Poniższa funkcja zeruje wszystkie elementy w tablicy:

for (int i = 0; i < n; i++)
{
    a[i] = 0;
}

Z kolei następująca pętla, odwraca wszystkie elementy w tablicy:

for (int i = 0; i < n / 2; i++)
{
    int t = a[i];
    a[i] = a[n-i-1];
    a[n-i-1] = t;
}

Zwróć uwagę na to, że w powyższej pętli, idziemy jedynie do połowy wartości n. Zmienna n oznacza tutaj długość tablicy. Dlaczego idziemy w powyższej pętli jedynie do połowy n, a nie do końca n? Bo wtedy odwrócilibyśmy tablicę dwukrotnie! A więc na końcu naszej pętli, wszystkie elementy tablicy byłyby na swoim miejscu.

Skąd wiedziałem, że element a[i] należy zamienić z elementem a[n-i-1]? Jak to szybko policzyć? Pierwszy element tablicy to a[0], musi zostać on zamieniony z elementem ostatnim, czyli z a[n-1]. Jak podstawimy w powyższym kodzie i = 0 to zobaczymy, że faktycznie te dwa elementy zostaną ze sobą zamienione. W ten sposób szybko sprawdzam czy wzory się zgadzają. Dalej element a[1] muszę zamienić z elementem a[n-2]. Zatem indeks jednego elementu zwiększył się o jeden, a indeks drugiego elementu zmniejszył się o jeden. Zatem dodajemy do jednego indeksu i, a od drugiego odejmujemy i. I tak można dojść do wzorów.

Istnieje w języku C++ funkcja, która odwraca tablicę i nazywa się reverse. Trzeba dodać #include <algorithm> na początku programu i używa się jej tak:

reverse(a, a+n);

Mamy już wszystkie składniki, aby rozwiązać nasze zadanie. Przyjrzyj się uważnie w jaki sposób wczytujemy i wypisujemy dane.

#include <iostream>

using namespace std;

int main()
{
    int n;
    int a[1000000];

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    for (int i = 0; i < n / 2; i++)
    {
       int t = a[i];
       a[i] = a[n-1-i];
       a[n-1-i] = t;
    }

    for (int i = 0; i < n; i++)
    {
        cout << a[i] << endl;
    }

    return 0;
}

Możecie spróbować przepisać powyższy kod, aby użyć funkcji reverse, albo nawet aby w ogóle nie obracać tablicy! Po uruchomieniu programu, może się okazać, że program nie działa. Jeśli tak się zdarzy, wpiszcie w konsoli ulimit -s unlimited. Po co to, wytłumaczę wam, gdy będziemy mówili o funkcjach.

Zadania do samodzielnego rozwiązywania

Eshag loves big arrays (ranking 800)
Arrays (ranking 900)
Replace the Numbers (ranking 1900)
Exact Change (ranking 2000)
The Winter Hike (ranking 2100)

Rozwiązanie do replace the numbers znajduje się na blogu.

Notka dziewiąta, w której poznajemy tablice i zamieniamy zmienne miejscami