C++ · Etap 2 · Lekcja 07

Tablice w C++

Do tej pory każda zmienna trzymała jedną wartość. Tablica trzyma ich tyle, ile potrzebujesz — pięć, tysiąc albo milion — pod jedną nazwą, a do każdej dobierasz się po numerze. Zaczniemy od pierwszej tablicy na pięć liczb. Potem nauczysz się wczytywać i przeglądać tablice pętlą, szukać w nich i je zmieniać, używać kilku tablic naraz, zliczać wystąpienia, budować plansze dwuwymiarowe, a na koniec poznasz dwie olimpijskie sztuczki: sumy prefiksowe i sito Eratostenesa. Po każdej części czekają ćwiczenia ze sprawdzarką.

63 ćwiczenia w trakcie lekcji29 zadań w bazie na koniec92 ze sprawdzarką C++
Filmy z OKI

Wolisz obejrzeć?

Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 2 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

Co już umiesz i czego się nauczysz

Ta lekcja otwiera drugi etap kursu. Zakłada, że przerobiłeś cały pierwszy: Typy zmiennych, Input / Output, If / Else, While loop, For loop i Modulo. Najbardziej przyda się pętla for — tablica i for prawie zawsze chodzą w parze — oraz napisy. Napis to w gruncie rzeczy tablica znaków, więc zapis s[i] i liczenie pozycji od zera już znasz.

Po co nam coś nowego? Spróbuj napisać program, który wczyta 1000 liczb, a potem wypisze tylko te większe od średniej. Średnią poznasz dopiero po wczytaniu wszystkich liczb — a wtedy pierwszych już nie masz, bo każda trafiała do tej samej zmiennej i była zamazywana przez następną. Potrzebujesz miejsca na tysiąc liczb naraz. Tysiąc osobnych zmiennych to szaleństwo. Tablica załatwia to jedną linijką.

Uczymy się tak samo jak poprzednio: przepisuj przykłady do swojego edytora i uruchamiaj je, przy pytaniach „Co wypisze program?” najpierw rozrysuj sobie pudełka tablicy na kartce i licz w głowie, a dopiero potem sprawdzaj odpowiedź, i po każdej części rób ćwiczenia w sprawdzarce. Tablice to temat, do którego będziesz wracać w każdym kolejnym — nie spiesz się i rób przerwy po kolejnych częściach.

CZĘŚĆ 01–02

Pierwsza tablica

Pudełka z numerami, indeksy od zera, wczytywanie, wypisywanie i wypełnianie tablicy pętlą.

CZĘŚĆ 03–04

Przeglądanie i zmiany

Suma, maksimum, szukanie, sąsiedzi — a potem zamiana, odwracanie, przesuwanie, usuwanie i wstawianie.

CZĘŚĆ 05–06

Kilka tablic i liczniki

Tablice równoległe, tablice-ściągi, nowa tablica z wybranych elementów i tablica liczników.

CZĘŚĆ 07–08

Plansze i olimpiada

Tablice dwuwymiarowe i plansze, duże tablice globalne, sumy prefiksowe i sito Eratostenesa.

Przypomnienie: złota zasada sprawdzarki Sprawdzarka porównuje Twoje wyjście z oczekiwanym znak po znaku, więc wypisujesz dokładnie to, o co prosi zadanie — bez „Podaj liczbę:” i bez dodatkowych słów. Spacje na końcu wiersza są ignorowane, więc cout << t[i] << " " w pętli niczego nie psuje. Uważaj natomiast na spacje i znaki w środku wiersza i na wielkość liter.

Mapa lekcji

Pudełka z numerami

Zacznijmy od zadania, które da się zrobić tym, co już umiesz — ale z trudem. Wczytaj pięć liczb i wypisz je w odwrotnej kolejności. Pętla tu nie pomoże: żeby wypisać ostatnią liczbę jako pierwszą, trzeba najpierw zapamiętać wszystkie pięć. Zostaje pięć osobnych zmiennych:

piec_zmiennych.cpp
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
cout << e << " " << d << " " << c << " " << b << " " << a << "\n";
▶ Wejście
1 2 3 4 5
▶ Wyjście
5 4 3 2 1

Działa. Ale co, gdyby liczb było sto? Albo tyle, ile poda użytkownik? Musiałbyś wymyślić sto nazw zmiennych i sto razy napisać prawie to samo.

Pętla też nie pomoże, bo zmienne a, b, c, d, e mają różne nazwy. Pętla nie potrafi „wybrać” zmiennej po numerze obrotu — nie da się napisać „w trzecim obrocie wczytaj do trzeciej zmiennej”.

Właśnie tego brakuje: zmiennych, które mają numery zamiast różnych nazw.

Tablica: jedna nazwa, wiele pudełek

Z lekcji o typach pamiętasz, że zmienna to pudełko z nazwą, w którym leży jedna wartość. Tablica to cały rząd takich pudełek, ustawionych jedno obok drugiego. Cały rząd ma jedną nazwę, a pudełka różnią się numerem. Numer pudełka nazywamy indeksem i piszemy go w nawiasach kwadratowych: t[0], t[1], t[2] i tak dalej. Tablicę tworzysz tak:

tworzenie.cpp
int t[5];   // tablica t: pięć pudełek typu int
Pięć pudełek o numerach od 0 do 4. Na razie nic do nich nie włożyliśmy, dlatego są znaki zapytania.
Jak czytać zapis tablicy Na początku stoi typ pudełek — tu int, więc w każdym leży liczba całkowita. Potem nazwa tablicy — wymyślasz ją tak samo jak nazwę zmiennej. W nawiasach kwadratowych rozmiar: ile pudełek ma powstać. Wszystkie pudełka jednej tablicy mają ten sam typ.

Każde pudełko tablicy to zwyczajna zmienna typu int, tylko z nietypową nazwą: t[0], t[1]… Możesz do niej wczytać liczbę i ją wypisać. Przepiszmy nasz program na tablicę:

piec_w_tablicy.cpp
int t[5];
cin >> t[0] >> t[1] >> t[2] >> t[3] >> t[4];
cout << t[4] << " " << t[3] << " " << t[2] << " " << t[1] << " " << t[0] << "\n";
▶ Wejście
1 2 3 4 5
▶ Wyjście
5 4 3 2 1

Na razie niewiele zyskaliśmy — zamiast a, b, c piszemy t[0], t[1], t[2]. Ale jest jedna ogromna różnica: numer pudełka to liczba, a liczba może być zmienną.

Zamiast t[3] możesz napisać t[i], gdzie i to licznik pętli. W każdym obrocie i ma inną wartość, więc t[i] to za każdym razem inne pudełko. To jest cała magia tablic.

piec_z_petla.cpp
int t[5];
for (int i = 0; i < 5; i++) {
    cin >> t[i];          // kolejno: t[0], t[1], ..., t[4]
}
for (int i = 4; i >= 0; i--) {
    cout << t[i] << " ";  // od t[4] w dół do t[0]
}
cout << "\n";
▶ Wejście
1 2 3 4 5
▶ Wyjście
5 4 3 2 1
▶ Inne wejście
10 -3 7 7 0
▶ Wyjście
0 7 7 -3 10
obrótiinstrukcjaskutek
1.0cin >> t[0]t[0] = 1
2.1cin >> t[1]t[1] = 2
3.2cin >> t[2]t[2] = 3
4.3cin >> t[3]t[3] = 4
5.4cin >> t[4]t[4] = 5
—5warunek 5 < 5 fałszywy — koniec

Pierwsza pętla wczytuje liczby do kolejnych pudełek. Druga zaczyna od i = 4 i schodzi w dół, więc wypisuje od ostatniego pudełka do pierwszego.

Żeby obsłużyć 1000 liczb, wystarczy zmienić 5 na 1000 i 4 na 999. W części 2 zrobimy to porządnie — z liczbą elementów podaną na wejściu.

Numerujemy od zera

Pierwsze pudełko ma numer 0, a nie 1 — dokładnie tak samo jak pierwsza litera napisu to s[0]. Pomaga porównanie z blokiem mieszkalnym: najniższe piętro to parter, czyli piętro zero, a „pierwsze piętro” jest tak naprawdę drugie od dołu. Tablica o rozmiarze 5 ma pudełka od t[0] do t[4]. Pudełka t[5] nie ma.

int t[5] = {7, 3, 9, 2, 5}; — pierwszy element to t[0], ostatni to t[4]. Indeks jest zawsze o jeden mniejszy niż „który to z kolei”.
który elementindeksw tablicy powyżej
pierwszy0t[0] = 7
drugi1t[1] = 3
trzeci2t[2] = 9
k-tyk - 1np. czwarty: t[3] = 2
ostatni w tablicy rozmiaru nn - 1t[4] = 5
Rozmiar 5, ostatni indeks 4 Liczba w nawiasach przy tworzeniu tablicy to rozmiar — ile jest pudełek. Liczba w nawiasach przy używaniu to numer pudełka. Ostatnie pudełko ma numer o jeden mniejszy od rozmiaru. Napisanie int t[5];, a potem t[5] = 10; to najczęstszy błąd początkujących.

Wkładanie i wyjmowanie wartości

Pudełko tablicy zachowuje się dokładnie jak zwykła zmienna. Możesz do niego przypisać wartość znakiem =, wczytać ją przez cin, wypisać, użyć w działaniach, zwiększyć przez ++ albo +=. Prześledź ten program linijka po linijce:

pudelka.cpp
int t[5];
t[0] = 10;
t[1] = 20;
t[2] = t[0] + t[1];   // 10 + 20
t[3] = t[2] * 2;      // 30 * 2
t[4] = t[3] - 1;      // 60 - 1
cout << t[0] << " " << t[1] << " " << t[2] << " " << t[3] << " " << t[4] << "\n";
t[1]++;               // 20 zmienia się w 21
t[0] += 5;            // 10 zmienia się w 15
cout << t[0] << " " << t[1] << "\n";
▶ Wyjście
10 20 30 60 59 15 21
po linijcet[0]t[1]t[2]t[3]t[4]
int t[5];?????
t[0] = 10;10????
t[1] = 20;1020???
t[2] = t[0] + t[1];102030??
t[3] = t[2] * 2;10203060?
t[4] = t[3] - 1;1020306059
t[1]++;1021306059
t[0] += 5;1521306059

Fioletowa liczba to pudełko, które zmieniło się w danej linijce. Pozostałe trzymają swoje wartości — dokładnie jak zwykłe zmienne.

Wartości od razu przy tworzeniu

Zamiast przypisywać każde pudełko osobno, możesz podać wartości w klamrach { } już przy tworzeniu tablicy. Są tu cztery warianty, które warto znać:

klamry.cpp
int a[5] = {7, 3, 9, 2, 5};   // wszystkie pięć wartości
int b[5] = {7, 3};            // dwie podane, reszta to zera
int c[5] = {};                // same zera
int d[] = {4, 8, 15, 16};     // rozmiar 4 policzy kompilator
for (int i = 0; i < 5; i++) { cout << a[i] << " "; }
cout << "\n";
for (int i = 0; i < 5; i++) { cout << b[i] << " "; }
cout << "\n";
for (int i = 0; i < 5; i++) { cout << c[i] << " "; }
cout << "\n";
for (int i = 0; i < 4; i++) { cout << d[i] << " "; }
cout << "\n";
▶ Wyjście
7 3 9 2 5 7 3 0 0 0 0 0 0 0 0 4 8 15 16

a — podajesz tyle wartości, ile jest pudełek. Trafiają do nich po kolei: pierwsza do a[0], druga do a[1] i tak dalej.

b — wartości jest mniej niż pudełek. Brakujące pudełka dostają zera. Gdyby wartości było więcej niż pudełek, program się nie skompiluje.

c — puste klamry to najprostszy sposób na tablicę pełną zer. Zapamiętaj go, przyda się bardzo często.

d — puste nawiasy kwadratowe: kompilator sam policzy wartości w klamrach i zrobi tyle pudełek. Tu cztery.

Klamry działają tylko przy tworzeniu tablicy. Później zapis t = {1, 2, 3}; się nie skompiluje — wartości trzeba wpisywać do pudełek po kolei, najwygodniej pętlą. Tablicy nie da się też skopiować jednym znakiem =, ale o tym w części 4.

Śmieci w nowej tablicy

Co jest w pudełkach tablicy, do której nic nie włożyłeś? Tablica utworzona wewnątrz main zapisem int t[5]; nie jest wyzerowana. W pudełkach siedzą przypadkowe liczby, które akurat zostały w tym miejscu pamięci. Programiści nazywają je śmieciami.

smieci.cpp
int t[5];                 // bez klamer!
for (int i = 0; i < 5; i++) {
    cout << t[i] << " ";
}
▶ Przykładowe wyjście — u Ciebie będzie inne
0 0 -1795260672 32759 1
Zanim odczytasz — włóż Każde pudełko, z którego coś odczytujesz, musi wcześniej dostać wartość: przez cin, przez = albo przez klamry przy tworzeniu. Gdy potrzebujesz tablicy pełnej zer — na przykład na liczniki — pisz int t[5] = {};. W części 8 zobaczysz, że tablice tworzone poza main są wyzerowane same.

Indeks może być wyrażeniem

W nawiasach kwadratowych może stać nie tylko liczba, ale dowolne wyrażenie, które daje liczbę całkowitą: zmienna, działanie, a nawet wartość z innego pudełka. C++ najpierw liczy wyrażenie w nawiasach, a potem bierze pudełko o takim numerze.

indeksy.cpp
int t[6] = {5, 1, 4, 2, 0, 3};
int i = 2;
cout << t[i] << "\n";       // t[2]
cout << t[i + 1] << "\n";   // t[3] — następne pudełko
cout << t[i] + 1 << "\n";   // wartość t[2] powiększona o 1
cout << t[2 * i] << "\n";   // t[4]
cout << t[t[0]] << "\n";    // t[0] to 5, więc t[5]
▶ Wyjście
4 2 5 0 3

Dla i = 2: t[i] to niebieskie pudełko (wartość 4), a t[i + 1] — pomarańczowe obok niego (wartość 2).

Uważaj na różnicę: t[i + 1] to następne pudełko, a t[i] + 1 to wartość pudełka powiększona o jeden. Tu 2 i 5 — zupełnie inne liczby. Nawiasy kwadratowe pokazują, co jest numerem, a co działaniem na wartości.

Poza tablicą — najgroźniejszy błąd

Co się stanie, gdy sięgniesz po pudełko, którego nie ma — t[5] w tablicy pięcioelementowej albo t[-1]? C++ nie sprawdza indeksów. Nie zobaczysz komunikatu o błędzie. Program po prostu zajrzy do pamięci tuż obok tablicy, gdzie leży coś zupełnie innego — może inna zmienna, może nic ważnego. Odczyt da przypadkową liczbę, a zapis może po cichu zepsuć inną zmienną albo wysypać program.

Prawdziwe pudełka mają numery od 0 do 4. Czerwone t[5] i t[6] nie należą do tablicy — tam leży cudza pamięć.
poza.cpp
int t[5] = {7, 3, 9, 2, 5};
cout << t[5] << "\n";   // BŁĄD: nie ma pudełka t[5]
t[7] = 100;             // BŁĄD: zapis do cudzej pamięci
▶ Przykładowe wyjście — może być dowolne
32764
Dozwolone indeksy: od 0 do rozmiar − 1 Najgorsze w tym błędzie jest to, że czasem wszystko „działa” i wychodzi na jaw dopiero na innych danych — na przykład w sprawdzarce, jako zła odpowiedź albo błąd wykonania. Dlatego przy każdym t[cokolwiek] zadaj sobie pytanie: czy to „cokolwiek” na pewno jest między 0 a rozmiarem minus jeden? Szczególnie uważaj na t[i + 1] i t[i - 1] w pętlach — przy ostatnim albo pierwszym obrocie łatwo wyjść za brzeg.

Tablice innych typów

Pudełka tablicy mogą mieć dowolny typ, który znasz: double, char, string, bool czy long long. Zasada się nie zmienia — wszystkie pudełka jednej tablicy mają ten sam typ.

typy.cpp
double ceny[3] = {2.5, 4.99, 10};
char znaki[4] = {'k', 'o', 't', 'y'};
string imiona[3] = {"Ola", "Jan", "Ewa"};
bool obecny[3] = {true, false, true};
long long duze[2] = {5000000000, 7};
cout << ceny[1] << "\n";
cout << znaki[0] << znaki[1] << znaki[2] << "\n";
cout << imiona[2] << " i " << imiona[0] << "\n";
cout << obecny[1] << "\n";
cout << duze[0] * 2 << "\n";
▶ Wyjście
4.99 kot Ewa i Ola 0 10000000000

Tablica string to rząd pudełek, z których w każdym leży cały napis. Nie myl jej z jednym napisem, w którym każde „pudełko” to jedna litera.

Tablica bool przyda się do zaznaczania: kto jest obecny, która liczba już się pojawiła, które pole jest zajęte. cout wypisuje false jako 0, a true jako 1 — znasz to z lekcji o typach.

Tablica long long — gdy wartości mogą przekroczyć zakres int, czyli około 2 miliardów.

Tablica-ściąga: numer zamienia się w nazwę

W lekcji o if poznałeś switch, który dla numeru dnia tygodnia wypisywał jego nazwę — siedem przypadków case. Z tablicą napisów to jedna linijka: nazwy leżą w pudełkach, a numer dnia wskazuje pudełko. Dni numerujemy od 1, a pudełka od 0 — dlatego odejmujemy jedynkę.

dzien_tygodnia.cpp
string dni[7] = {"poniedzialek", "wtorek", "sroda", "czwartek",
                 "piatek", "sobota", "niedziela"};
int k;
cin >> k;                    // numer dnia: od 1 do 7
cout << dni[k - 1] << "\n";  // dzień numer k leży w pudełku k - 1
▶ Wejście
3
▶ Wyjście
sroda
▶ Inne wejście
7
▶ Wyjście
niedziela
dni_miesiaca.cpp
int dlugosc[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int m;
cin >> m;                       // numer miesiąca: od 1 do 12
cout << dlugosc[m - 1] << "\n";
▶ Wejście
2
▶ Wyjście
28
▶ Inne wejście
11
▶ Wyjście
30

Takie tablice-ściągi spotkasz bardzo często: nazwy miesięcy, ceny produktów, wartości monet. Zamiast pisać długi łańcuch if-ów, wkładasz odpowiedzi do pudełek i wyciągasz właściwą po numerze. W części 5 zbudujemy z nich zamianę liczb na rzymskie.

Numeracja od 1 → indeks od 0 Gdy coś jest numerowane od 1 (dni, miesiące, miejsca w kolejce, „k-ty element”), a tablica od 0, to rzecz numer k leży w pudełku k - 1. W drugą stronę: pudełko i to rzecz numer i + 1. Ten sam trik znasz z lekcji o modulo.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int t[4] = {8, 6, 4, 2};
cout << t[1];
Pokaż odpowiedź
6Indeksy zaczynają się od zera: t[0] to 8, a t[1] — drugie pudełko — to 6.
Co wypisze ten fragment?
int t[5] = {3, 1};
cout << t[0] + t[1] + t[4];
Pokaż odpowiedź
4Podaliśmy tylko dwie wartości, więc pozostałe pudełka — t[2], t[3] i t[4] — dostały zera. 3 + 1 + 0 = 4.
Co wypisze ten fragment?
int t[3] = {5, 7, 9};
t[0] = t[2];
t[2] = t[0] + 1;
cout << t[0] << " " << t[1] << " " << t[2];
Pokaż odpowiedź
9 7 10Najpierw t[0] dostaje wartość z t[2], czyli 9. Potem t[2] = t[0] + 1 = 9 + 1 = 10 — bo t[0] ma już nową wartość. t[1] się nie zmieniło.
Indeks z pudełka. Co wypisze ten fragment?
int t[5] = {4, 3, 2, 1, 0};
cout << t[t[1]];
Pokaż odpowiedź
1Najpierw środek: t[1] to 3. Potem bierzemy t[3], czyli 1.
Uwaga na nawiasy. Co wypisze ten fragment?
int t[4] = {10, 20, 30, 40};
int i = 1;
cout << t[i + 1] << " " << t[i] + 1;
Pokaż odpowiedź
30 21t[i + 1] to t[2], czyli 30 — następne pudełko. t[i] + 1 to 20 + 1 = 21 — wartość pudełka t[1] powiększona o jeden.
Tablica napisów. Co wypisze ten fragment?
string s[3] = {"ala", "ma", "kota"};
cout << s[2] << s[0];
Pokaż odpowiedź
kotaalas[2] to trzeci napis, „kota”, a s[0] — pierwszy, „ala”. Wychodzą sklejone, bo żadnej spacji nie wypisaliśmy.
Rozmiar policzony przez kompilator. Co wypisze ten fragment?
int t[] = {1, 1, 2, 3, 5, 8};
cout << t[5] - t[0];
Pokaż odpowiedź
7Kompilator policzył sześć wartości, więc tablica ma rozmiar 6, a ostatni indeks to 5: t[5] = 8. 8 − 1 = 7.
Kwiecień to miesiąc numer 4. Co wypisze program?
int dlugosc[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int m;
cin >> m;
cout << dlugosc[m] << " " << dlugosc[m - 1];
Wejście: 4
Pokaż odpowiedź
31 30Kwiecień leży w pudełku 3: dlugosc[3] = 30. A dlugosc[4] to już maj, który ma 31 dni — klasyczny błąd przesunięcia o jeden.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Wczytaj, wypisz, wypełnij

W części 1 pętla przechodziła po pudełkach od 0 do 4. Dokładnie tak samo przejdziesz po tablicy dowolnej długości. Zapamiętaj ten zapis — napiszesz go jeszcze setki razy:

Pętla po tablicy o n elementach for (int i = 0; i < n; i++) — licznik i przyjmuje wartości 0, 1, 2, …, n − 1, czyli dokładnie wszystkie indeksy tablicy o n elementach. Warunek to i < n, a nie i <= n: pudełko t[n] już nie istnieje.

Ile liczb? Tyle, ile poda wejście

W zadaniach prawie zawsze pierwsza liczba wejścia mówi, ile będzie danych. Treść brzmi na przykład tak: „W pierwszym wierszu liczba n (1 ≤ n ≤ 1000), w drugim n liczb całkowitych”. Jest tu mały kłopot: rozmiar tablicy trzeba podać, pisząc program, a n poznamy dopiero, gdy program działa. Rozwiązanie jest proste — robimy tablicę z zapasem, tak dużą, jak największe możliwe n z treści zadania. Używamy tylko pierwszych n pudełek, a reszta leży nieużywana.

wczytaj_wypisz.cpp
int t[1000];          // zapas: w zadaniu n jest co najwyżej 1000
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> t[i];      // wczytanie
}
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";   // wypisanie po kolei
}
cout << "\n";
for (int i = n - 1; i >= 0; i--) {
    cout << t[i] << " ";   // wypisanie od tyłu
}
cout << "\n";
▶ Wejście
4 10 20 30 40
▶ Wyjście
10 20 30 40 40 30 20 10

To trzy pętle, które będziesz pisać najczęściej. Porównaj je:

pętlapo co
for (int i = 0; i < n; i++)
cin >> t[i];
wczytuje n liczb do pudełek 0 … n − 1
for (int i = 0; i < n; i++)
cout << t[i];
wypisuje od pierwszego do ostatniego
for (int i = n - 1; i >= 0; i--)przechodzi od ostatniego do pierwszego

Pętla od tyłu startuje od n - 1 (ostatni indeks), a kończy na i &gt;= 0, żeby nie pominąć pudełka zero.

Z tysiąca pudełek używamy tylko pierwszych n = 4. Pozostałe istnieją, ale nic w nich nie trzymamy i nigdy do nich nie zaglądamy.
Rozmiar: stały i z zapasem Rozmiar w nawiasach musi być znany, zanim program ruszy: wpisana liczba albo stała const. Wygodnie jest nadać mu nazwę: const int MAX = 1005; i potem int t[MAX];. Zapas bierz z ograniczeń w treści zadania i dodaj kilka pudełek marginesu — nie zaszkodzą, a chronią przed pomyłką o jeden.
Rozmiar nie może przyjść z wejścia Może kusić, żeby najpierw wczytać n, a potem napisać int t[n];. Kompilator g++ na to pozwala, ale to nie jest prawdziwy C++: inne kompilatory zgłoszą błąd, a dla dużego n program może się wysypać. W tym kursie zawsze robimy tablicę z zapasem. Na tablicę o rozmiarze z wejścia przyjdzie czas w lekcji o vectorze.

Z numerami i tylko wybrane

Ludzie liczą od 1, a tablica od 0. Gdy chcesz wypisać listę z numerami, pudełko i wypisujesz z numerem i + 1:

lista.cpp
string imie[100];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> imie[i];
}
for (int i = 0; i < n; i++) {
    cout << i + 1 << ". " << imie[i] << "\n";
}
▶ Wejście
3 Ola Jan Ewa
▶ Wyjście
1. Ola 2. Jan 3. Ewa
fragment.cpp
int t[100];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> t[i];
}
int a, b;
cin >> a >> b;            // numery od 1
for (int i = a - 1; i <= b - 1; i++) {
    cout << t[i] << " ";  // od a-tego do b-tego
}
cout << "\n";
▶ Wejście
6 5 8 2 7 4 1 2 4
▶ Wyjście
8 2 7

W drugim programie użytkownik podaje numery od 1 — „od drugiego do czwartego elementu” — więc indeksy to a - 1 i b - 1. Tym razem warunek ma &lt;=, bo chcemy włącznie z pudełkiem b - 1.

A teraz coś, co często się myli. Porównaj dwie pętle, które wyglądają podobnie, ale robią coś zupełnie innego: jedna patrzy na numer pudełka, druga na wartość w pudełku.

indeks_czy_wartosc.cpp
int t[100];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> t[i];
}
// co drugie pudełko: indeksy 0, 2, 4, ...
for (int i = 0; i < n; i += 2) {
    cout << t[i] << " ";
}
cout << "\n";
// liczby o parzystej WARTOŚCI
for (int i = 0; i < n; i++) {
    if (t[i] % 2 == 0) {
        cout << t[i] << " ";
    }
}
cout << "\n";
▶ Wejście
6 5 8 2 7 4 1
▶ Wyjście
5 2 4 8 2 4
Pudełka o parzystych indeksach (niebieskie): 0, 2 i 4. Leżą w nich 5, 2 i 4.
Parzyste wartości (zielone): 8, 2 i 4. Leżą w pudełkach 1, 2 i 4.

Pierwsza pętla skacze co dwa pudełka (i += 2) i nie patrzy na wartości. Druga odwiedza każde pudełko i sprawdza, co w nim leży: t[i] % 2. Gdyby napisać i % 2 == 0, sprawdzałbyś numer pudełka — to też jest sposób na „co drugie pudełko”.

Wypełnianie tablicy wzorem

Tablica nie musi przychodzić z wejścia — program może wypełnić ją sam. Wystarczy w pętli przypisać każdemu pudełku wartość policzoną z numeru i:

wzory.cpp
int kw[10], niep[10];
for (int i = 0; i < 10; i++) {
    kw[i] = i * i;          // kwadraty: 0, 1, 4, 9, ...
    niep[i] = 2 * i + 1;    // nieparzyste: 1, 3, 5, ...
}
for (int i = 0; i < 10; i++) { cout << kw[i] << " "; }
cout << "\n";
for (int i = 0; i < 10; i++) { cout << niep[i] << " "; }
cout << "\n";
▶ Wyjście
0 1 4 9 16 25 36 49 64 81 1 3 5 7 9 11 13 15 17 19

Jedna pętla może wypełniać kilka tablic naraz — tu w każdym obrocie zapisujemy pudełko kw[i] i pudełko niep[i].

Zwróć uwagę na zapis int kw[10], niep[10]; — dwie tablice w jednej linijce, tak jak int a, b; tworzy dwie zmienne.

Element z poprzedniego elementu

Najciekawsze wzory korzystają z pudełek, które już wypełniliśmy. Weźmy potęgi dwójki: każda jest dwa razy większa od poprzedniej, więc p[i] = p[i - 1] * 2. Pierwsze pudełko trzeba ustawić osobno — p[0] nie ma poprzednika — dlatego pętla startuje od 1, a nie od 0. Gdyby zaczęła od 0, sięgnęłaby po p[-1], czyli poza tablicę.

potegi.cpp
long long p[63];
p[0] = 1;                     // 2 do potęgi 0
for (int i = 1; i < 63; i++) {
    p[i] = p[i - 1] * 2;      // dwa razy więcej niż poprzednia
}
cout << p[10] << "\n";
cout << p[62] << "\n";
▶ Wyjście
1024 4611686018427387904
p[4] (pomarańczowe) powstaje z p[3] (niebieskie): 8 · 2 = 16. Każde pudełko korzysta z sąsiada po lewej.

Tak samo zbudujesz ciąg Fibonacciego, który znasz z lekcji o pętlach: każdy wyraz to suma dwóch poprzednich. Tym razem trzeba ustawić dwa pierwsze pudełka, a pętlę zacząć od 2. Prześledź pierwsze obroty w tabelce:

fibonacci.cpp
long long f[91];              // indeksy od 0 do 90
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= 90; i++) {
    f[i] = f[i - 1] + f[i - 2];   // suma dwóch poprzednich
}
int q;
cin >> q;                     // ile pytań
for (int j = 0; j < q; j++) {
    int k;
    cin >> k;
    cout << f[k] << "\n";
}
▶ Wejście
3 10 50 90
▶ Wyjście
55 12586269025 2880067194370816120
if[i - 2]f[i - 1]f[i]
2011
3112
4123
5235
6358
…………

Tablica ma 91 pudełek, bo potrzebujemy indeksów od 0 do 90 — o jeden więcej niż największy indeks.

Zobacz, co tu zyskaliśmy: ciąg liczymy tylko raz, a potem na każde pytanie odpowiadamy jednym odczytem z tablicy. Przygotuj wszystko wcześniej, a potem odpowiadaj natychmiast — to bardzo olimpijski sposób myślenia. Wrócimy do niego w części 8.

Przecinki między elementami

Czasem zadanie każe wypisać elementy oddzielone przecinkiem i spacją, ale bez przecinka na końcu: [4, 8, 15]. Spacja na końcu wiersza nie przeszkadza sprawdzarce, ale przecinek już tak. Sztuczka: wypisuj separator przed każdym elementem oprócz pierwszego.

przecinki.cpp
int t[5] = {4, 8, 15, 16, 23};
cout << "[";
for (int i = 0; i < 5; i++) {
    if (i > 0) {
        cout << ", ";       // przed każdym oprócz pierwszego
    }
    cout << t[i];
}
cout << "]\n";
▶ Wyjście
[4, 8, 15, 16, 23]

W pierwszym obrocie i = 0, więc warunek i &gt; 0 jest fałszywy i przecinka nie ma. W każdym kolejnym obrocie przecinek stoi przed liczbą — dlatego po ostatniej liczbie już się nie pojawia.

Pętla for (int x : t)

Z lekcji o pętli for pamiętasz zapis for (char c : s), który przechodzi po wszystkich literach napisu. Tak samo możesz przejść po tablicy: for (int x : t) — „dla każdego x z tablicy t”. W każdym obrocie x to kopia kolejnego pudełka.

dla_kazdego.cpp
int t[5] = {4, 8, 15, 16, 23};
int suma = 0;
for (int x : t) {       // x to kolejno: 4, 8, 15, 16, 23
    suma += x;
}
cout << suma << "\n";
▶ Wyjście
66
Uwaga: przechodzi po wszystkich pudełkach Taka pętla odwiedza każde pudełko tablicy. Dla int t[1000]; i n = 4 obróci się 1000 razy — razem z nieużywanymi pudełkami pełnymi śmieci. Używaj jej tylko wtedy, gdy tablica jest wypełniona cała, jak tu. Przy tablicy z zapasem pisz zwykły for z warunkiem i < n. I jeszcze jedno: x jest kopią, więc zmiana x nie zmienia tablicy.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int t[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i += 2) {
    cout << t[i];
}
Pokaż odpowiedź
135Licznik przyjmuje wartości 0, 2 i 4, więc wypisujemy t[0], t[2] i t[4] — bez spacji, bo żadnej nie wypisujemy.
Co wypisze ten fragment?
int t[5] = {9, 8, 7, 6, 5};
for (int i = 4; i >= 1; i--) {
    cout << t[i];
}
Pokaż odpowiedź
5678Pętla kończy się na i = 1, więc t[0] (czyli 9) nie zostało wypisane. Żeby dojść do pierwszego pudełka, warunek musi brzmieć i >= 0.
Co wypisze ten fragment?
int t[5];
for (int i = 0; i < 5; i++) {
    t[i] = i * 3;
}
cout << t[4] + t[1];
Pokaż odpowiedź
15Pętla wpisuje 0, 3, 6, 9, 12. t[4] to 12, t[1] to 3, razem 15.
Co wypisze ten fragment?
int t[6];
t[0] = 1;
for (int i = 1; i < 6; i++) {
    t[i] = t[i - 1] * 3;
}
cout << t[5];
Pokaż odpowiedź
243Każde pudełko jest trzy razy większe od poprzedniego: 1, 3, 9, 27, 81, 243. To potęgi trójki, a t[5] to 3 do piątej.
Pudełko zmienione przed chwilą. Co wypisze ten fragment?
int t[4] = {2, 4, 6, 8};
for (int i = 1; i < 4; i++) {
    t[i] = t[i] + t[i - 1];
}
for (int i = 0; i < 4; i++) {
    cout << t[i] << " ";
}
Pokaż odpowiedź
2 6 12 20Ważne: gdy liczymy t[i], pudełko t[i - 1] zostało już zmienione w poprzednim obrocie. Dlatego 4 + 2 = 6, potem 6 + 6 = 12, potem 8 + 12 = 20. Każde pudełko to suma wszystkich elementów do niego włącznie — zapamiętaj ten pomysł na część 8.
Co jest nie tak z tą pętlą?
int t[4] = {1, 2, 3, 4};
for (int i = 1; i <= 4; i++) {
    cout << t[i] << " ";
}
Pokaż odpowiedź
2 3 4 i jakaś przypadkowa liczbaLicznik idzie od 1 do 4. Pomija t[0], a w ostatnim obrocie czyta t[4] — pudełko, którego nie ma. To dwa błędy naraz, typowe dla kogoś, kto liczy od 1. Poprawnie: for (int i = 0; i < 4; i++).
Skoki po tablicy. Co wypisze ten fragment?
int t[5] = {3, 0, 4, 1, 2};
int i = 0;
for (int k = 0; k < 3; k++) {
    i = t[i];
}
cout << i;
Pokaż odpowiedź
0Wartość z pudełka staje się nowym numerem pudełka. Start: i = 0. Potem t[0] = 3, t[3] = 1, t[1] = 0. Po trzech skokach i to 0.
Pary od końców. Co wypisze ten fragment?
int t[6] = {1, 2, 3, 4, 5, 6};
int n = 6;
for (int i = 0; i < n / 2; i++) {
    cout << t[i] + t[n - 1 - i] << " ";
}
Pokaż odpowiedź
7 7 7Pudełko n - 1 - i to pudełko „i-te od końca”. Pętla dodaje pierwszy z ostatnim (1 + 6), drugi z przedostatnim (2 + 5) i trzeci z trzecim od końca (3 + 4). Tego samego zapisu użyjemy w części 4 do odwracania tablicy.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Suma, maksimum, szukanie

W lekcjach o pętlach liczyłeś sumę, największą liczbę i liczniki „w locie” — każdą liczbę od razu po wczytaniu, bo potem już jej nie było. Z tablicą robisz to samo, ale dane zostają w pudełkach i możesz przejść po nich drugi, trzeci, dziesiąty raz. Dzięki temu rozwiążesz zadania, w których każdą liczbę trzeba porównać z czymś, co poznamy dopiero po przeczytaniu wszystkich.

Suma i średnia

Schemat jest ten sam co w lekcji o pętli while: zmienna na wynik przed pętlą, ustawiona na 0, i dodawanie w każdym obrocie. Różnica jest tylko taka, że dodajemy t[i], a nie świeżo wczytaną liczbę.

suma_srednia.cpp
int t[1000];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> t[i];
}
long long suma = 0;
for (int i = 0; i < n; i++) {
    suma += t[i];
}
cout << "suma: " << suma << "\n";
cout << "srednia: " << fixed << setprecision(2) << (double)suma / n << "\n";
▶ Wejście
5 4 8 15 16 23
▶ Wyjście
suma: 66 srednia: 13.20

Suma jest w long long: tysiąc liczb po miliard dałoby bilion, a to nie mieści się w int.

Przy średniej pamiętaj o pułapce z lekcji o typach: suma / n dla dwóch liczb całkowitych to dzielenie całkowite (66 / 5 = 13). Dlatego zamieniamy sumę na double zapisem (double)suma, a fixed i setprecision(2) dają dwa miejsca po przecinku.

Ile liczb jest większych od średniej?

A teraz zadanie ze wstępu, którego bez tablicy nie da się zrobić. W chwili, gdy wczytujesz pierwszą liczbę, nie znasz jeszcze średniej — poznasz ją dopiero po ostatniej. Z tablicą to proste: pierwsze przejście liczy średnią, drugie porównuje z nią każdą liczbę.

powyzej_sredniej.cpp
int t[1000];
int n;
cin >> n;
long long suma = 0;
for (int i = 0; i < n; i++) {
    cin >> t[i];
    suma += t[i];        // sumę liczymy już przy wczytywaniu
}
double sr = (double)suma / n;
int ile = 0;
for (int i = 0; i < n; i++) {   // drugie przejście
    if (t[i] > sr) {
        ile++;
    }
}
cout << ile << "\n";
▶ Wejście
5 4 8 15 16 23
▶ Wyjście
3
▶ Inne wejście
4 5 5 5 5
▶ Wyjście
0
Średnia to 13,2. Większe od niej są 15, 16 i 23 (zielone) — trzy liczby.

Przy samych piątkach średnia to dokładnie 5 i żadna liczba nie jest od niej większa — stąd 0.

Można też obejść się bez ułamków, sztuczką z lekcji o if: zamiast t[i] &gt; suma / n sprawdź t[i] * n &gt; suma — obie strony pomnożone przez n. Przy dużych liczbach licz to w long long: (long long)t[i] * n.

Licznik i suma z warunkiem

Ten sam schemat — zmienna przed pętlą, aktualizacja w środku — działa z dowolnym warunkiem. W jednym przejściu możesz liczyć kilka rzeczy naraz:

z_warunkiem.cpp
int t[8] = {3, -2, 7, 0, -5, 3, 3, 1};
int n = 8;
int dodatnie = 0, jak_pierwsza = 0, suma_ujemnych = 0;
for (int i = 0; i < n; i++) {
    if (t[i] > 0) {
        dodatnie++;
    }
    if (t[i] == t[0]) {
        jak_pierwsza++;           // t[0] też się liczy!
    }
    if (t[i] < 0) {
        suma_ujemnych += t[i];
    }
}
cout << dodatnie << " " << jak_pierwsza << " " << suma_ujemnych << "\n";
▶ Wyjście
5 3 -7

Dodatnich jest pięć: 3, 7, 3, 3 i 1 (zero nie jest dodatnie). Liczb równych pierwszej są trzy — razem z samą t[0], bo pętla zaczyna od i = 0. Ujemne to −2 i −5, ich suma to −7.

Trzy osobne if-y (a nie else if), bo jedna liczba może spełniać kilka warunków naraz — na przykład 3 jest dodatnia i równa pierwszej.

Największy element — i gdzie on jest

Największą wartość szukasz tak jak w lekcjach o pętlach, z jedną ważną zasadą: zaczynasz od pierwszego elementu, maks = t[0], a nie od zera, i przeglądasz od indeksu 1. Gdybyś zaczął od zera, to przy samych liczbach ujemnych program odpowiedziałby 0 — liczbą, której w ogóle nie ma w danych.

Często potrzebujesz nie tylko największej wartości, ale też jej miejsca. Wtedy zamiast wartości pamiętaj indeks: gdzie. Wartość zawsze odczytasz z t[gdzie].

maksimum.cpp
int t[7] = {4, 9, 2, 9, -1, 7, 2};
int n = 7;
int maks = t[0];               // start: pierwszy element, nie zero!
for (int i = 1; i < n; i++) {
    if (t[i] > maks) {
        maks = t[i];
    }
}
int gdzie = 0;                 // indeks największego
for (int i = 1; i < n; i++) {
    if (t[i] > t[gdzie]) {
        gdzie = i;
    }
}
cout << "maksimum: " << maks << "\n";
cout << "pozycja: " << gdzie + 1 << "\n";
▶ Wyjście
maksimum: 9 pozycja: 2
it[i]t[gdzie]t[i] > t[gdzie]?gdzie
start—4—0
194tak1
229nie1
399nie1
4−19nie1
579nie1
629nie1

Dziewiątka stoi w dwóch miejscach: w pudełkach 1 i 3. Przy i = 3 warunek 9 &gt; 9 jest fałszywy, więc zostaje pierwsza dziewiątka. Wypisujemy gdzie + 1, bo „pozycja” to numer liczony od 1.

Gdy zamienisz &gt; na &gt;=, równa wartość też podmieni indeks — dostaniesz ostatnią dziewiątkę, pozycję 4. Najmniejszy element znajdziesz tak samo, ze znakiem &lt;.

Szukanie: czy x jest w tablicy?

Szukanie to przeglądanie po kolei, aż trafisz na szukaną wartość. Gdy znajdziesz pierwszą, dalej nie ma po co szukać — przerywasz pętlę przez break, który znasz z lekcji o pętlach. Wynik zapisujemy w zmiennej gdzie, a na start dajemy jej wartość -1, która znaczy „nie znaleziono”. Żadne pudełko nie ma numeru −1, więc nie pomylisz jej z prawdziwą pozycją.

szukanie.cpp
int t[6] = {5, 3, 8, 3, 9, 1};
int n = 6;
int x;
cin >> x;
int gdzie = -1;                // -1 znaczy: jeszcze nie znaleźliśmy
for (int i = 0; i < n; i++) {
    if (t[i] == x) {
        gdzie = i;
        break;                 // pierwsze trafienie — koniec szukania
    }
}
if (gdzie == -1) {
    cout << "BRAK\n";
} else {
    cout << "pozycja " << gdzie + 1 << "\n";
}
▶ Wejście
3
▶ Wyjście
pozycja 2
▶ Inne wejście
7
▶ Wyjście
BRAK

Trójka występuje dwa razy, ale program wypisuje pozycję 2 — pierwszą, bo po trafieniu break kończy pętlę.

Dwie przydatne odmiany tego samego schematu:

Ostatnie wystąpienie — usuń break. Pętla przejdzie do końca, a gdzie będzie podmieniane przy każdym trafieniu, więc zostanie ostatnie. (Albo szukaj od końca z break.)

Ile razy wystąpiło — zamiast gdzie = i; break; napisz ile++; i przejdź całą tablicę.

Sąsiedzi: t[i] i t[i + 1]

Wiele zadań pyta o sąsiednie elementy: o ile wzrosła temperatura z dnia na dzień, ile razy wynik się poprawił, czy liczby idą w kolejności rosnącej. W każdym obrocie patrzymy wtedy na parę t[i] i t[i + 1]. Uwaga na koniec pętli: ostatnia para to t[n - 2] i t[n - 1], więc licznik kończy się na n - 2 — warunek brzmi i &lt; n - 1.

Para dla i = 3: t[3] = 2 i t[i + 1] = t[4] = 8. Różnica t[i + 1] − t[i] = 6 — tu był wzrost.
sasiedzi.cpp
int t[6] = {3, 5, 5, 2, 8, 9};
int n = 6;
int wzrosty = 0;
bool uporzadkowany = true;          // na razie nie widzieliśmy spadku
for (int i = 0; i < n - 1; i++) {   // ostatnia para: t[n-2] i t[n-1]
    cout << t[i + 1] - t[i] << " ";
    if (t[i + 1] > t[i]) {
        wzrosty++;
    }
    if (t[i + 1] < t[i]) {
        uporzadkowany = false;      // spadek psuje kolejność
    }
}
cout << "\n";
cout << "wzrostow: " << wzrosty << "\n";
cout << "uporzadkowany: " << uporzadkowany << "\n";
▶ Wyjście
2 0 -3 6 1 wzrostow: 3 uporzadkowany: 0

Sześć liczb daje tylko pięć par sąsiadów, dlatego różnic jest pięć.

Zmienna uporzadkowany to flaga z lekcji o if: zaczyna jako true i wystarczy jeden spadek, żeby zmieniła się na false. Tu spadek jest jeden — z 5 na 2.

Za ostatnim nie ma sąsiada Gdy w pętli używasz t[i + 1], przy warunku i < n ostatni obrót sięgnie po t[n] — poza tablicę. Tak samo z t[i - 1]: pętla musi zacząć od i = 1.

Każdy z każdym — dwie pętle

Czasem trzeba porównać każdy element z każdym innym: czy jakieś dwa są równe, ile par daje sumę k. W lekcji o pętli for poznałeś sposób na pary: druga pętla zaczyna się od j = i + 1. Dzięki temu każda para pojawia się dokładnie raz i nigdy nie porównujemy elementu z nim samym.

pary.cpp
int t[5] = {1, 2, 1, 2, 1};
int n = 5;
int pary = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {   // j zawsze za i
        if (t[i] == t[j]) {
            pary++;
        }
    }
}
cout << pary << "\n";
▶ Wyjście
4

Równe pary to pudełka (0, 2), (0, 4), (2, 4) — trzy jedynki — oraz (1, 3) — dwie dwójki. Razem 4.

Ile obrotów wykonuje taka podwójna pętla? Około n · n / 2. Dla n = 1000 to pół miliona — chwila. Ale dla n = milion byłoby to pół biliona obrotów, czyli wiele minut. W części 6 poznasz tablicę liczników, która takie zadania robi jedną pętlą.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int t[5] = {3, -1, 4, -1, 5};
int s = 0;
for (int i = 0; i < 5; i++) {
    s += t[i];
}
cout << s;
Pokaż odpowiedź
103 − 1 + 4 − 1 + 5 = 10. Liczby ujemne dodajemy tak samo jak dodatnie.
Co wypisze ten fragment?
int t[6] = {4, 7, 1, 4, 9, 5};
int ile = 0;
for (int i = 1; i < 6; i++) {
    if (t[i] > t[0]) {
        ile++;
    }
}
cout << ile;
Pokaż odpowiedź
3Porównujemy z pierwszą liczbą, czyli 4. Większe od niej są 7, 9 i 5. Druga czwórka nie jest większa — jest równa.
Zły start. Co wypisze ten fragment?
int t[3] = {-5, -2, -9};
int maks = 0;
for (int i = 0; i < 3; i++) {
    if (t[i] > maks) {
        maks = t[i];
    }
}
cout << maks;
Pokaż odpowiedź
0Żadna liczba nie jest większa od zera, więc maks zostaje 0 — a zera w ogóle nie ma w tablicy! Poprawny wynik to −2. Dlatego zawsze zaczynamy od maks = t[0].
Większe albo równe. Co wypisze ten fragment?
int t[5] = {4, 9, 2, 9, 1};
int g = 0;
for (int i = 1; i < 5; i++) {
    if (t[i] >= t[g]) {
        g = i;
    }
}
cout << g;
Pokaż odpowiedź
3Ze znakiem >= druga dziewiątka (w pudełku 3) też podmienia indeks, więc zostaje ostatnie wystąpienie największej wartości.
Szukanie z break. Co wypisze ten fragment?
int t[5] = {1, 7, 3, 7, 7};
int g = -1;
for (int i = 0; i < 5; i++) {
    if (t[i] == 7) {
        g = i;
        break;
    }
}
cout << g;
Pokaż odpowiedź
1Pierwsza siódemka leży w pudełku 1. Po trafieniu break kończy pętlę, więc dalszych siódemek program już nie widzi.
A bez break? Co wypisze ten fragment?
int t[5] = {1, 7, 3, 7, 7};
int g = -1;
for (int i = 0; i < 5; i++) {
    if (t[i] == 7) {
        g = i;
    }
}
cout << g;
Pokaż odpowiedź
4Bez break pętla idzie do końca, a każda kolejna siódemka nadpisuje g. Zostaje ostatnia — w pudełku 4.
Sąsiedzi. Co wypisze ten fragment?
int t[5] = {1, 3, 2, 4, 5};
int ile = 0;
for (int i = 0; i < 4; i++) {
    if (t[i] < t[i + 1]) {
        ile++;
    }
}
cout << ile;
Pokaż odpowiedź
3Pary sąsiadów: 1 < 3 (tak), 3 < 2 (nie), 2 < 4 (tak), 4 < 5 (tak). Trzy wzrosty. Pętla idzie do i < 4, czyli n - 1, żeby t[i + 1] nie wyszło poza tablicę.
Pary o sumie 10. Co wypisze ten fragment?
int t[5] = {3, 7, 5, 5, 7};
int ile = 0;
for (int i = 0; i < 5; i++) {
    for (int j = i + 1; j < 5; j++) {
        if (t[i] + t[j] == 10) {
            ile++;
        }
    }
}
cout << ile;
Pokaż odpowiedź
3Sumę 10 dają pary pudełek (0, 1) i (0, 4) — trójka z każdą z siódemek — oraz (2, 3) — dwie piątki. Piątka z samą sobą się nie liczy, bo j zaczyna od i + 1.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Zamiana, odwracanie, przesuwanie

Do tej pory tylko czytaliśmy tablicę. Ale pudełka można też zmieniać — i to w dowolnej kolejności, wiele razy. W tej części nauczysz się zmieniać wszystkie elementy naraz, zamieniać je miejscami, odwracać tablicę, przesuwać ją w kółko, usuwać i wstawiać elementy. Przy każdym z tych zadań kluczowe jest jedno pytanie: czy nie zamazuję wartości, której jeszcze będę potrzebować?

Zmiana każdego elementu

Najprostsza zmiana: przejdź po tablicy i każdemu pudełku przypisz nową wartość, policzoną ze starej. Zapis t[i] = t[i] * 10 najpierw odczytuje starą wartość, mnoży ją i wpisuje wynik z powrotem do tego samego pudełka — dokładnie jak x = x * 10 dla zwykłej zmiennej.

zmien_kazdy.cpp
int t[6] = {4, -3, 12, 0, -8, 5};
int n = 6;
for (int i = 0; i < n; i++) {
    if (t[i] < 0) {
        t[i] = 0;          // ujemne zamieniamy na zero
    }
}
for (int i = 0; i < n; i++) {
    t[i] *= 10;            // każde pudełko razy 10
}
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wyjście
40 0 120 0 0 50
Pomarańczowe pudełka były ujemne — najpierw zmieniły się w zero, a zero razy 10 to dalej zero.

Zamiana dwóch elementów miejscami

Z lekcji o if pamiętasz, że zamiana dwóch zmiennych wymaga trzeciej, pomocniczej — albo funkcji swap. Z pudełkami tablicy jest tak samo. Gdybyś napisał po prostu t[0] = t[4]; t[4] = t[0];, to po pierwszej linijce stara wartość t[0] przepadłaby na zawsze i oba pudełka miałyby tę samą liczbę.

zamiana.cpp
int t[5] = {7, 3, 9, 2, 5};
int n = 5;
// sposób 1: ze zmienną pomocniczą
int pom = t[0];        // odkładamy 7 na bok
t[0] = t[n - 1];       // t[0] dostaje 5
t[n - 1] = pom;        // t[4] dostaje odłożone 7
// sposób 2: swap robi to samo w jednej linijce
swap(t[1], t[2]);
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wyjście
5 9 3 2 7
Pierwszy z ostatnim (pomarańczowe) zamieniliśmy przez zmienną pomocniczą, drugi z trzecim (niebieskie) — przez swap.

swap(t[i], t[j]) zamienia zawartość dowolnych dwóch pudełek. Indeksy mogą być wyrażeniami — na przykład swap(t[0], t[gdzie]) przeniesie największy element na początek, jeśli gdzie to indeks maksimum z części 3.

Odwracanie tablicy w miejscu

W części 2 wypisywałeś tablicę od tyłu. Teraz odwrócimy ją naprawdę, w pudełkach. Pomysł: zamień pierwszy element z ostatnim, drugi z przedostatnim, trzeci z trzecim od końca… i tak aż do środka. Z quizu w części 2 znasz już numer pudełka „i-tego od końca”: n - 1 - i.

odwracanie.cpp
int t[1000];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> t[i];
}
for (int i = 0; i < n / 2; i++) {
    swap(t[i], t[n - 1 - i]);   // i-ty od początku z i-tym od końca
}
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wejście
5 1 2 3 4 5
▶ Wyjście
5 4 3 2 1
▶ Inne wejście
6 10 20 30 40 50 60
▶ Wyjście
60 50 40 30 20 10
in − 1 − izamianatablica po zamianie
start——1 2 3 4 5
04t[0] ↔ t[4]5 2 3 4 1
13t[1] ↔ t[3]5 4 3 2 1
2warunek 2 < 5 / 2, czyli 2 < 2, fałszywy — koniec

Każda zamiana ustawia na miejscu dwa elementy, więc wystarczy n / 2 zamian. Przy nieparzystym n środkowy element (tu 3) zostaje tam, gdzie był — i dobrze, bo w odwróconej tablicy też jest w środku.

Do połowy, nie do końca Gdyby pętla szła aż do i < n, druga połowa obrotów zamieniłaby wszystkie pary z powrotem: t[4] z t[0], t[3] z t[1]… i tablica wróciłaby do początkowej kolejności. Program działałby bez błędu, tylko nic by nie zmienił.

Ten sam pomysł działa dla fragmentu tablicy. Weź dwa indeksy: l na lewym końcu fragmentu i r na prawym. Zamieniaj t[l] z t[r] i przesuwaj je do siebie, aż się spotkają:

odwroc_fragment.cpp
int t[8] = {1, 2, 3, 4, 5, 6, 7, 8};
int l = 2, r = 5;              // odwracamy pudełka od 2 do 5
while (l < r) {
    swap(t[l], t[r]);
    l++;                       // lewy idzie w prawo
    r--;                       // prawy idzie w lewo
}
for (int i = 0; i < 8; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wyjście
1 2 6 5 4 3 7 8
Odwrócił się tylko fragment od pudełka 2 do 5 (pomarańczowy). Reszta tablicy jest nietknięta.

Warunek l &lt; r zatrzymuje pętlę w środku fragmentu: gdy indeksy się spotkają albo miną, wszystko jest już zamienione.

Przesuwanie o jedno miejsce w kółko

Wyobraź sobie kolejkę do kasy, w której pierwsza osoba przechodzi na koniec, a wszyscy pozostali robią krok do przodu. W tablicy: każde pudełko bierze wartość od sąsiada z prawej, a pierwszy element ląduje na końcu. Pierwszy element trzeba zapamiętać przed pętlą — pętla go zamaże.

w_lewo.cpp
int t[5] = {1, 2, 3, 4, 5};
int n = 5;
int pierwszy = t[0];             // zapamiętaj, zanim zamażesz
for (int i = 0; i < n - 1; i++) {
    t[i] = t[i + 1];             // wartość od sąsiada z prawej
}
t[n - 1] = pierwszy;             // pierwszy ląduje na końcu
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wyjście
2 3 4 5 1
w_prawo.cpp
int t[5] = {1, 2, 3, 4, 5};
int n = 5;
int ostatni = t[n - 1];
for (int i = n - 1; i > 0; i--) {   // OD KOŃCA!
    t[i] = t[i - 1];                // wartość od sąsiada z lewej
}
t[0] = ostatni;
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wyjście
5 1 2 3 4

Przesuwanie w prawo idzie od końca. Dlaczego? Zobacz, co się stanie, gdy pójdziemy od początku: pudełko 1 dostaje wartość z pudełka 0, potem pudełko 2 dostaje wartość z pudełka 1 — ale to jest już skopiowana jedynka! Ta sama liczba rozlewa się po całej tablicy:

w_prawo_zle.cpp
int t[5] = {1, 2, 3, 4, 5};
int n = 5;
int ostatni = t[n - 1];
for (int i = 1; i < n; i++) {   // ŹLE: od początku
    t[i] = t[i - 1];
}
t[0] = ostatni;
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wyjście
5 1 1 1 1
iinstrukcjatablica po
start—1 2 3 4 5
1t[1] = t[0]1 1 3 4 5
2t[2] = t[1]1 1 1 4 5
3t[3] = t[2]1 1 1 1 5
4t[4] = t[3]1 1 1 1 1

Zasada na przyszłość: przesuwasz w prawo — idź od prawej; przesuwasz w lewo — idź od lewej. Wtedy każde pudełko oddaje swoją wartość, zanim zostanie zamazane.

Przesunięcie o k miejsc — modulo wraca

A gdyby przesunąć tablicę w kółko o k miejsc w prawo? Można k razy powtórzyć przesunięcie o jeden, ale przy k = miliard trwałoby to wieki. Lepiej policzyć od razu, gdzie wyląduje każdy element. Z lekcji o modulo znasz zawijanie w kółko: element z pudełka i trafia do pudełka (i + k) % n. A pełne obroty niczego nie zmieniają, więc liczy się tylko k % n.

obrot_o_k.cpp
int t[1000], w[1000];
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
    cin >> t[i];
}
k = k % n;                      // pełne obroty niczego nie zmieniają
for (int i = 0; i < n; i++) {
    w[(i + k) % n] = t[i];      // element z pudełka i ląduje k dalej
}
for (int i = 0; i < n; i++) {
    cout << w[i] << " ";
}
cout << "\n";
▶ Wejście
5 2 1 2 3 4 5
▶ Wyjście
4 5 1 2 3
▶ Inne wejście
5 12 1 2 3 4 5
▶ Wyjście
4 5 1 2 3

Dla k = 2: element z pudełka 0 trafia do pudełka 2, z pudełka 3 do pudełka 0 (bo 5 % 5 = 0), z pudełka 4 do pudełka 1. Przesunięcie o 12 to dwa pełne obroty i jeszcze 2 — wynik taki sam.

Tym razem wyniki wpisujemy do drugiej tablicy w. Gdybyśmy pisali od razu do t, zamazywalibyśmy elementy, których jeszcze nie przenieśliśmy. Druga tablica to najprostszy sposób, żeby nie martwić się kolejnością.

Usuwanie i wstawianie

Tablica nie umie „wyjąć” pudełka ze środka — wszystkie pudełka zawsze istnieją. Usunięcie elementu to więc dwie rzeczy: przesunięcie wszystkiego, co stoi za nim, o jedno miejsce w lewo, i zmniejszenie n — liczby pudełek, których używamy. Wstawianie działa odwrotnie: robimy miejsce, przesuwając elementy w prawo (od końca!), wpisujemy nową wartość i zwiększamy n. Dlatego przy wstawianiu tablica musi mieć zapas pudełek.

usun.cpp
int t[10] = {5, 6, 7, 8, 9};
int n = 5;
int p = 1;                       // usuwamy pudełko 1, czyli 6
for (int i = p; i < n - 1; i++) {
    t[i] = t[i + 1];             // reszta w lewo
}
n--;                             // używamy o jedno pudełko mniej
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wyjście
5 7 8 9
wstaw.cpp
int t[10] = {5, 6, 8, 9};
int n = 4;
int p = 2, x = 7;                // 7 ma trafić do pudełka 2
for (int i = n; i > p; i--) {
    t[i] = t[i - 1];             // od końca: reszta w prawo
}
t[p] = x;
n++;                             // używamy o jedno pudełko więcej
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wyjście
5 6 7 8 9

Po usunięciu w pudełku t[4] wciąż leży stara dziewiątka — ale skoro n = 4, nigdy już tam nie zajrzymy. Liczy się tylko pierwszych n pudełek.

Usuwanie wielu elementów naraz

Co, jeśli trzeba usunąć wszystkie zera? Można usuwać je po jednym, za każdym razem przesuwając resztę — ale przy dużej tablicy to dużo pracy. Jest sprytniejszy sposób z dwoma indeksami. Indeks i czyta tablicę po kolei, a k mówi, ile elementów już zostawiliśmy — czyli gdzie jest pierwsze wolne miejsce. Element, który zostaje, przepisujemy na miejsce k.

bez_zer.cpp
int t[8] = {0, 3, 0, 0, 5, 1, 0, 2};
int n = 8;
int k = 0;                       // ile elementów zostawiliśmy
for (int i = 0; i < n; i++) {
    if (t[i] != 0) {
        t[k] = t[i];             // zostaje: na pierwsze wolne miejsce
        k++;
    }
}
n = k;
for (int i = 0; i < n; i++) {
    cout << t[i] << " ";
}
cout << "\n";
▶ Wyjście
3 5 1 2
it[i]zostaje?k popoczątek tablicy
00nie0—
13tak13
20nie13
30nie13
45tak23 5
51tak33 5 1
60nie33 5 1
72tak43 5 1 2

k nigdy nie wyprzedza i, więc nie zamazujemy niczego, czego jeszcze nie przeczytaliśmy. Jedno przejście i gotowe — kolejność pozostałych elementów się nie zmienia.

Kopiowanie i porównywanie tablic

Dwie rzeczy, które działają dla zwykłych zmiennych, z tablicami nie działają. Tablicy nie skopiujesz znakiem = — program się nie skompiluje. A porównanie a == b co prawda się kompiluje, ale nie sprawdza zawartości pudełek (dla dwóch różnych tablic zawsze wychodzi fałsz). Jedno i drugie robisz pętlą, pudełko po pudełku.

kopia_blad.cpp
int a[3] = {1, 2, 3};
int b[3];
b = a;        // BŁĄD KOMPILACJI: tablicy nie da się przypisać
kopia.cpp
int a[3] = {1, 2, 3};
int b[3];
for (int i = 0; i < 3; i++) {
    b[i] = a[i];                 // kopiujemy pudełko po pudełku
}
b[0] = 100;                      // zmiana kopii nie rusza oryginału
cout << a[0] << " " << b[0] << "\n";
bool takie_same = true;
for (int i = 0; i < 3; i++) {
    if (a[i] != b[i]) {
        takie_same = false;
    }
}
cout << takie_same << "\n";
▶ Wyjście
1 100 0
Tablica to nie jedna zmienna Wszystko, co robisz z całą tablicą — kopiowanie, porównywanie, wypisywanie — robisz pętlą po pudełkach. Nawet cout << t; nie wypisze elementów, tylko dziwną liczbę szesnastkową (adres tablicy w pamięci). Kopia zrobiona pętlą jest osobną tablicą: zmiana b[0] nie zmieniła a[0].
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int t[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
    t[i] = t[i] * 2 - 1;
}
for (int i = 0; i < 5; i++) {
    cout << t[i] << " ";
}
Pokaż odpowiedź
1 3 5 7 9Każde pudełko zmienia się według wzoru 2 · x − 1: 1, 3, 5, 7, 9 — wyszły kolejne liczby nieparzyste.
Zamiana bez pomocnika. Co wypisze ten fragment?
int t[2] = {4, 9};
t[0] = t[1];
t[1] = t[0];
cout << t[0] << " " << t[1];
Pokaż odpowiedź
9 9Pierwsza linijka wpisuje 9 do t[0] i czwórka przepada na zawsze. Druga przepisuje tę samą dziewiątkę z powrotem. Do zamiany potrzebna jest zmienna pomocnicza albo swap.
Odwracanie aż do końca. Co wypisze ten fragment?
int t[4] = {1, 2, 3, 4};
for (int i = 0; i < 4; i++) {
    swap(t[i], t[3 - i]);
}
for (int i = 0; i < 4; i++) {
    cout << t[i] << " ";
}
Pokaż odpowiedź
1 2 3 4Pierwsze dwa obroty odwracają tablicę (4 3 2 1), a dwa kolejne zamieniają te same pary z powrotem. Pętla musi kończyć się w połowie: i < n / 2.
Przesuwanie w lewo, ale od końca. Co wypisze ten fragment?
int t[5] = {1, 2, 3, 4, 5};
for (int i = 3; i >= 0; i--) {
    t[i] = t[i + 1];
}
for (int i = 0; i < 5; i++) {
    cout << t[i] << " ";
}
Pokaż odpowiedź
5 5 5 5 5Najpierw t[3] dostaje 5, potem t[2] dostaje wartość z t[3] — czyli już piątkę — i tak dalej. Przy przesuwaniu w lewo trzeba iść od lewej.
Obrót z modulo. Co wypisze ten fragment?
int t[5] = {1, 2, 3, 4, 5}, w[5];
for (int i = 0; i < 5; i++) {
    w[(i + 3) % 5] = t[i];
}
for (int i = 0; i < 5; i++) {
    cout << w[i];
}
Pokaż odpowiedź
34512Jedynka (pudełko 0) trafia do w[3], dwójka do w[4], trójka do w[(2 + 3) % 5] = w[0], czwórka do w[1], piątka do w[2]. To przesunięcie o 3 w prawo.
Usuwanie pierwszego elementu. Co wypisze ten fragment?
int t[5] = {5, 6, 7, 8, 9};
int n = 5;
for (int i = 0; i < n - 1; i++) {
    t[i] = t[i + 1];
}
n--;
cout << n << " " << t[0] << t[n - 1];
Pokaż odpowiedź
4 69Wszystko przesunęło się w lewo: 6 7 8 9, a n zmalało do 4. t[0] to 6, a t[n - 1] = t[3] to 9.
Zostaw tylko dodatnie. Co wypisze ten fragment?
int t[6] = {4, -1, 2, -7, -3, 8};
int k = 0;
for (int i = 0; i < 6; i++) {
    if (t[i] > 0) {
        t[k] = t[i];
        k++;
    }
}
cout << k << ":";
for (int i = 0; i < k; i++) {
    cout << " " << t[i];
}
Pokaż odpowiedź
3: 4 2 8Zostają 4, 2 i 8 — w tej samej kolejności, w jakiej były. k to liczba zostawionych elementów.
Kopia to osobna tablica. Co wypisze ten fragment?
int a[3] = {1, 2, 3}, b[3];
for (int i = 0; i < 3; i++) {
    b[i] = a[i] * a[i];
}
a[2] = 0;
cout << a[2] + b[2];
Pokaż odpowiedź
9b dostało kwadraty: 1, 4, 9. Zmiana a[2] na 0 nie rusza już b, więc 0 + 9 = 9.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Tablice równoległe, ściągi i nowe tablice

Jedna tablica to lista liczb. Ale w zadaniach dane często mają kilka cech: uczeń ma imię i punkty, produkt — nazwę i cenę, zawodnik — wynik z pierwszej i z drugiej rundy. W tej części nauczysz się trzymać takie dane w kilku tablicach naraz, budować nowe tablice z wybranych elementów, używać tablic jako ściąg do przeliczania i łączyć dwie uporządkowane listy w jedną.

Tablice równoległe: ten sam indeks, ta sama osoba

Wyobraź sobie tabelkę w zeszycie: w pierwszej kolumnie imiona, w drugiej punkty, a każdy wiersz to jedna osoba. W programie każda kolumna to osobna tablica: imie[i] i punkty[i]. Łączy je ten sam indeks — pudełko numer 2 w obu tablicach opisuje tę samą osobę. Takie tablice nazywamy równoległymi.

ranking.cpp
string imie[100];
int punkty[100];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cin >> imie[i] >> punkty[i];   // w wierszu: imię i punkty
}
int naj = 0;                        // INDEKS najlepszego
for (int i = 1; i < n; i++) {
    if (punkty[i] > punkty[naj]) {
        naj = i;
    }
}
cout << "Wygrywa " << imie[naj] << " (" << punkty[naj] << " pkt)\n";
▶ Wejście
4 Ola 17 Jan 23 Ewa 19 Igor 23
▶ Wyjście
Wygrywa Jan (23 pkt)
iimie[i]punkty[i]
0Ola17
1Jan23
2Ewa19
3Igor23

Szukamy maksimum w tablicy punkty, ale zapamiętujemy jego indeks, a nie wartość. Dzięki temu z tablicy imie odczytamy imię z tego samego wiersza: imie[naj].

Igor ma tyle samo punktów co Jan, ale znak &gt; nie podmienia indeksu przy remisie — wygrywa ten, kto był pierwszy na liście.

Dane nie zawsze przychodzą wierszami. Czasem najpierw dostajesz wyniki wszystkich zawodników z pierwszej rundy, a dopiero potem z drugiej. Bez tablic nie da się ich połączyć — gdy czytasz drugą rundę, pierwsza musi już leżeć w pudełkach.

dwie_rundy.cpp
int r1[100], r2[100];
int n;
cin >> n;
for (int i = 0; i < n; i++) { cin >> r1[i]; }   // cała 1. runda
for (int i = 0; i < n; i++) { cin >> r2[i]; }   // cała 2. runda
for (int i = 0; i < n; i++) {
    cout << r1[i] + r2[i] << " ";   // zawodnik i: obie rundy razem
}
cout << "\n";
int lepiej = 0;
for (int i = 0; i < n; i++) {
    if (r2[i] > r1[i]) {
        lepiej++;
    }
}
cout << "poprawilo sie: " << lepiej << "\n";
▶ Wejście
4 10 7 9 5 8 9 9 10
▶ Wyjście
18 16 18 15 poprawilo sie: 2
Zawodnik i to pudełko i w obu tablicach. Poprawili się zawodnicy 1 i 3 (zielone): z 7 na 9 i z 5 na 10.

Nowa tablica z wybranych elementów

W części 4 zostawiałeś w tablicy tylko wybrane elementy, przepisując je na początek. Często wygodniej jest wkładać je do nowej tablicy — oryginał zostaje wtedy nietknięty. Schemat jest ten sam: licznik mówi, ile elementów już włożyłeś, czyli gdzie jest pierwsze wolne pudełko. Można też rozdzielać elementy do kilku tablic naraz:

podzial.cpp
int t[8] = {5, 8, 2, 7, 4, 1, 6, 3};
int n = 8;
int parz[8], niep[8];
int ileP = 0, ileN = 0;          // ile już włożyliśmy do każdej
for (int i = 0; i < n; i++) {
    if (t[i] % 2 == 0) {
        parz[ileP] = t[i];       // na pierwsze wolne miejsce
        ileP++;
    } else {
        niep[ileN] = t[i];
        ileN++;
    }
}
for (int i = 0; i < ileP; i++) { cout << parz[i] << " "; }
cout << "| ";
for (int i = 0; i < ileN; i++) { cout << niep[i] << " "; }
cout << "\n";
▶ Wyjście
8 2 4 6 | 5 7 1 3
Obie nowe tablice zachowują kolejność z oryginału. Każda ma swój licznik: ileP i ileN.

Nowe tablice mają rozmiar 8, bo w najgorszym razie wszystkie liczby mogą być parzyste (albo wszystkie nieparzyste). Zapas zawsze licz na najgorszy przypadek.

Tablica-ściąga indeksowana literą

W części 1 numer dnia wskazywał pudełko z nazwą dnia. Pudełko może też wskazywać litera. Z lekcji o typach pamiętasz, że znaki to liczby (kody ASCII), a małe litery mają kolejne kody. Dlatego 'a' - 'a' to 0, 'b' - 'a' to 1, …, 'z' - 'a' to 25. Zapis c - 'a' zamienia literę na numer pudełka od 0 do 25. Zobacz to na grze Scrabble, w której każda litera ma swoją wartość punktową:

scrabble.cpp
//             a  b  c  d  e  f  g  h  i  j  k  l  m
int pkt[26] = {1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3,
//             n  o  p  q   r  s  t  u  v  w  x  y  z
               1, 1, 3, 10, 1, 1, 1, 1, 4, 4, 8, 4, 10};
string s;
cin >> s;
int suma = 0;
for (int i = 0; i < s.length(); i++) {
    suma += pkt[s[i] - 'a'];    // litera -> numer pudełka
}
cout << suma << "\n";
▶ Wejście
quiz
▶ Wyjście
22
▶ Inne wejście
kot
▶ Wyjście
7
literas[i] − 'a'pkt[…]suma
q161010
u20111
i8112
z251022

Zamiast 26 if-ów — jedna tablica i jedno odejmowanie. Ten sam trik zobaczysz w części 6 przy liczeniu liter.

Uwaga: pkt[s[i] - 'a'] działa tylko dla małych liter. Wielka litera albo cyfra dałaby indeks spoza 0–25. Jeśli w danych mogą być inne znaki, najpierw je sprawdź.

Dwie ściągi naraz: liczby rzymskie

Ściągi świetnie łączą się z tablicami równoległymi. Zamiana liczby na rzymską wymaga par „wartość — symbol”: 1000 to M, 900 to CM, 500 to D i tak dalej. Włóżmy wartości do jednej tablicy, symbole do drugiej — od największej do najmniejszej. Potem dla każdej pary: dopóki wartość mieści się w liczbie, wypisz symbol i odejmij wartość.

rzymskie.cpp
int wartosc[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string symbol[13] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL",
                     "X", "IX", "V", "IV", "I"};
int n;
cin >> n;
for (int i = 0; i < 13; i++) {
    while (n >= wartosc[i]) {   // dopóki się mieści
        cout << symbol[i];
        n -= wartosc[i];
    }
}
cout << "\n";
▶ Wejście
1994
▶ Wyjście
MCMXCIV
▶ Inne wejście
2026
▶ Wyjście
MMXXVI
n przednajwiększa mieszcząca sięwypiszn po
19941000M994
994900CM94
9490XC4
44IV0

Dzięki parom 900 (CM), 400 (CD), 90 (XC) i tak dalej nie trzeba pisać żadnych wyjątków dla „odejmowania” w zapisie rzymskim — wszystko załatwia kolejność w ściądze.

Scalanie dwóch uporządkowanych list

Na koniec klasyka, która wraca w wielu algorytmach. Masz dwie listy liczb, każda uporządkowana od najmniejszej do największej, i chcesz z nich zrobić jedną uporządkowaną listę. Wyobraź sobie dwie kolejki dzieci ustawionych od najniższego: za każdym razem z dwóch dzieci stojących na początku kolejek do nowej kolejki wchodzi niższe. Każda tablica ma swój indeks — „kto stoi pierwszy”: i w tablicy a, j w tablicy b, a k mówi, ile osób stoi już w nowej kolejce c.

scalanie.cpp
int a[5] = {1, 4, 6, 9, 12};
int b[4] = {2, 3, 10, 15};
int n = 5, m = 4;
int c[9];
int i = 0, j = 0, k = 0;
while (i < n && j < m) {        // obie listy jeszcze niepuste
    if (a[i] <= b[j]) {
        c[k] = a[i];            // mniejszy z a
        i++;
    } else {
        c[k] = b[j];            // mniejszy z b
        j++;
    }
    k++;
}
while (i < n) { c[k] = a[i]; i++; k++; }   // reszta z a
while (j < m) { c[k] = b[j]; j++; k++; }   // reszta z b
for (int x = 0; x < k; x++) {
    cout << c[x] << " ";
}
cout << "\n";
▶ Wyjście
1 2 3 4 6 9 10 12 15
a[i]b[j]bierzemy
121 (z a)
422 (z b)
433 (z b)
4104 (z a)
6106 (z a)
9109 (z a)
121010 (z b)
121512 (z a)
—15a się skończyła: reszta z b

Gdy jedna lista się skończy, pierwsza pętla while staje. Wtedy dwie ostatnie przepisują resztę drugiej listy — tylko jedna z nich coś zrobi, bo jedna lista jest już pusta.

Każda tablica ma swój indeks Gdy pracujesz na kilku tablicach naraz, każda potrzebuje własnego „gdzie jestem”. W scalaniu i pokazuje pozycję w a, j w b, a k w c. Pomylenie ich — na przykład a[j] zamiast a[i] — to częsty błąd, którego kompilator nie wykryje.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Tablice równoległe. Co wypisze ten fragment?
string imie[3] = {"Ola", "Jan", "Ewa"};
int pkt[3] = {5, 9, 7};
int naj = 0;
for (int i = 1; i < 3; i++) {
    if (pkt[i] > pkt[naj]) {
        naj = i;
    }
}
cout << imie[naj] << pkt[naj];
Pokaż odpowiedź
Jan9Największa liczba punktów, 9, leży w pudełku 1. Z tablicy imie bierzemy to samo pudełko — Jan.
Dwie tablice, ten sam indeks. Co wypisze ten fragment?
int a[4] = {3, 1, 4, 1}, b[4] = {2, 7, 1, 8};
int ile = 0;
for (int i = 0; i < 4; i++) {
    if (a[i] > b[i]) {
        ile++;
    }
}
cout << ile;
Pokaż odpowiedź
2Porównujemy pary z tym samym indeksem: 3 > 2 (tak), 1 > 7 (nie), 4 > 1 (tak), 1 > 8 (nie).
Nowa tablica. Co wypisze ten fragment?
int t[6] = {7, 2, 9, 4, 6, 1};
int b[6];
int k = 0;
for (int i = 0; i < 6; i++) {
    if (t[i] > 5) {
        b[k] = t[i];
        k++;
    }
}
cout << k << " " << b[k - 1];
Pokaż odpowiedź
3 6Do b trafiają 7, 9 i 6, więc k = 3. Ostatni włożony element leży w pudełku k - 1 = 2 — to 6.
Kopia od tyłu. Co wypisze ten fragment?
int a[4] = {1, 2, 3, 4}, b[4];
for (int i = 0; i < 4; i++) {
    b[i] = a[3 - i];
}
cout << b[0] << b[3];
Pokaż odpowiedź
41b[0] dostaje a[3] = 4, a b[3] dostaje a[0] = 1. Tablica b to odwrócona a.
Ściąga z nominałami. Ile monet wyda ten program na 13 zł?
int w[3] = {5, 2, 1};
int n = 13;
int ile = 0;
for (int i = 0; i < 3; i++) {
    while (n >= w[i]) {
        n -= w[i];
        ile++;
    }
}
cout << ile;
Pokaż odpowiedź
4Tak samo jak przy liczbach rzymskich: dwie piątki (zostaje 3), jedna dwójka (zostaje 1) i jedna jedynka. Razem 4 monety.
Pudełko wskazane literą. Co wypisze ten fragment?
int pkt[26] = {};
pkt['k' - 'a'] = 5;
pkt['o' - 'a'] = 1;
string s = "kok";
int suma = 0;
for (char c : s) {
    suma += pkt[c - 'a'];
}
cout << suma;
Pokaż odpowiedź
11Pudełko 'k' - 'a' (czyli 10) ma 5 punktów, a pudełko 'o' - 'a' (czyli 14) — 1 punkt. „kok” to 5 + 1 + 5 = 11.
Scalanie. Co wypisze ten fragment?
int a[2] = {1, 5}, b[3] = {2, 3, 8};
int i = 0, j = 0;
while (i < 2 && j < 3) {
    if (a[i] <= b[j]) {
        cout << a[i] << " ";
        i++;
    } else {
        cout << b[j] << " ";
        j++;
    }
}
while (i < 2) { cout << a[i] << " "; i++; }
while (j < 3) { cout << b[j] << " "; j++; }
Pokaż odpowiedź
1 2 3 5 8Po wypisaniu 1, 2, 3 i 5 lista a się kończy, a ostatnia pętla dopisuje resztę z b, czyli 8. Wynik jest uporządkowany.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

5.1 Powyżej średniej klasyłatwe✓ zaliczone Imiona i punkty w dwóch tablicach. Wypisz uczniów, którzy przekroczyli średnią klasy. tablice równoległedwa przejściaBRAK Rozwiąż 5.2 Najpierw parzystełatwe✓ zaliczone Rozłóż liczby do dwóch nowych tablic i wypisz najpierw parzyste, potem nieparzyste. nowa tablicalicznik = pierwsze wolneparzystość Rozwiąż 5.3 Sprawdzian z kluczemłatwe✓ zaliczone Porównaj odpowiedzi każdego ucznia z kluczem, policz punkty i wskaż najlepszego. char klucz[100]porównanie pozycja po pozycjinajlepszy Rozwiąż 5.4 Najlepsze słowo w Scrabblełatwe✓ zaliczone Wartości liter są w tablicy-ściądze indeksowanej literą. Które słowo jest warte najwięcej? int pkt[26]c - 'a'maksimum Rozwiąż 5.5 Z rzymskich na arabskieśrednie✓ zaliczone Zamień liczby rzymskie na zwykłe — z tablicą wartości indeksowaną literą. ściąga indeksowana literąnastępna cyfrastring Rozwiąż 5.6 Szyfr podstawieniowyśrednie✓ zaliczone Klucz to 26 liter. Szyfruj ściągą, a odszyfrowuj ściągą odwrotną. klucz[c - 'a']ściąga odwrotnachar Rozwiąż 5.7 Scalanie dwóch listśrednie✓ zaliczone Połącz dwie uporządkowane listy w jedną uporządkowaną — bez sortowania, trzema indeksami. scalanieindeksy i, jreszta listy Rozwiąż 5.8 Wspólne elementyśrednie✓ zaliczone Dwie listy rosnące — wypisz liczby, które są na obu. Jedno przejście dwoma indeksami. dwa indeksylisty uporządkowaneBRAK Rozwiąż
Wszystkie ćwiczenia z tej części w sprawdzarce →

Ile razy wystąpiło?

Nauczyciel sprawdził klasówki i chce wiedzieć, ile było szóstek, ile piątek, a ile jedynek. Z tym, co znasz, potrzebowałbyś sześciu liczników i sześciu if-ów (albo switch). A gdyby zamiast ocen były punkty od 0 do 100? Sto jeden liczników i sto jeden if-ów?

Tablica rozwiązuje to w jednej linijce. Robimy tablicę liczników: osobne pudełko-licznik dla każdej możliwej wartości. A najlepsze jest to, że sama wartość wskazuje numer swojego licznika. Ocena 5 zwiększa pudełko numer 5, ocena 3 — pudełko numer 3.

Wartość to numer pudełka

oceny.cpp
int ile[7] = {};          // liczniki ile[1] … ile[6]; ile[0] nieużywane
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int ocena;
    cin >> ocena;
    ile[ocena]++;         // ocena wskazuje swój licznik
}
for (int o = 6; o >= 1; o--) {
    cout << o << ": " << ile[o] << "\n";
}
▶ Wejście
8 5 3 6 5 2 5 3 4
▶ Wyjście
6: 1 5: 3 4: 1 3: 2 2: 1 1: 0
ocenaile[1]ile[2]ile[3]ile[4]ile[5]ile[6]
start000000
5000010
3001010
6001011
5001021
2011021
5011031
3012031
4012131
Tablica liczników po wczytaniu wszystkich ocen. Numer pudełka to ocena, a wartość w pudełku — ile razy ta ocena wystąpiła. Pudełko 0 nie jest używane.

Trzy rzeczy, na które warto zwrócić uwagę:

Rozmiar 7, a nie 6. Oceny to liczby od 1 do 6, więc potrzebujemy pudełka numer 6 — a ono istnieje dopiero w tablicy rozmiaru 7 (indeksy 0–6). Pudełko 0 po prostu leży nieużywane. To prostsze niż przesuwanie wszystkiego o jeden zapisem ile[ocena - 1].

Klamry = {} są obowiązkowe. Liczniki muszą startować od zera. Bez klamer w pudełkach byłyby śmieci i ++ dodawałoby jedynkę do przypadkowej liczby.

Samych ocen w ogóle nie zapamiętujemy — każdą wczytujemy do zwykłej zmiennej i od razu zwiększamy jej licznik. Tablica trzyma tylko liczniki.

Histogram z gwiazdek

Liczniki łatwo zamienić na wykres. Z lekcji o typach pamiętasz zapis string(n, znak), który robi napis z n jednakowych znaków. Rzucamy kostką i rysujemy, ile razy wypadło każde oczko:

kostka.cpp
int ile[7] = {};
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    ile[x]++;
}
for (int oczko = 1; oczko <= 6; oczko++) {
    cout << oczko << " | " << string(ile[oczko], '*') << "\n";
}
▶ Wejście
12 3 6 1 3 3 5 6 2 3 6 1 4
▶ Wyjście
1 | ** 2 | * 3 | **** 4 | * 5 | * 6 | ***

Ten sam schemat zadziała dla każdej wartości z małego zakresu: dni tygodnia urodzin, godzin, w których przychodzą klienci, numerów, na które głosują wyborcy. Zawsze: tablica liczników z zerami, jedna pętla zliczająca, jedna pętla wypisująca.

Liczenie liter

W części 5 litera wskazywała pudełko przez c - 'a'. Tak samo policzysz litery w tekście: 26 liczników, po jednym na każdą literę od a do z. Żeby przy wypisywaniu zamienić numer pudełka z powrotem na literę, dodajemy go do 'a' i rzutujemy na char — znasz to z lekcji o typach.

litery.cpp
int ile[26] = {};
string s;
cin >> s;
for (int i = 0; i < s.length(); i++) {
    ile[s[i] - 'a']++;             // 'a' -> 0, 'b' -> 1, ...
}
for (int k = 0; k < 26; k++) {
    if (ile[k] > 0) {
        cout << (char)('a' + k) << ": " << ile[k] << "\n";   // 0 -> 'a', 1 -> 'b', ...
    }
}
▶ Wejście
abrakadabra
▶ Wyjście
a: 5 b: 2 d: 1 k: 1 r: 2

Litery wychodzą w kolejności alfabetycznej, bo pętla wypisująca idzie po pudełkach od 0 do 25 — kolejność w słowie nie ma znaczenia.

Cyfry w napisie policzysz tak samo: 10 liczników i ile[c - '0']++.

Z liczników łatwo też sprawdzić, czy dwa słowa są anagramami (mają te same litery w innej kolejności, jak „kot” i „tok”): policz litery obu słów do dwóch tablic i porównaj je pudełko po pudełku.

Najczęstsza wartość

Gdy liczniki są gotowe, najczęstsza wartość to po prostu indeks największego licznika — szukasz go dokładnie tak jak maksimum z indeksem w części 3. Ze znakiem &gt; przy remisie wygrywa mniejsza wartość, bo przeglądamy pudełka od najmniejszego numeru.

najczestsza.cpp
int ile[101] = {};               // wartości od 0 do 100
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    ile[x]++;
}
int naj = 0;                     // wartość z największym licznikiem
for (int v = 1; v <= 100; v++) {
    if (ile[v] > ile[naj]) {
        naj = v;
    }
}
cout << naj << " (" << ile[naj] << " razy)\n";
▶ Wejście
10 7 3 7 100 3 0 7 3 50 2
▶ Wyjście
3 (3 razy)

Trójka i siódemka wystąpiły po trzy razy. Pętla dochodzi najpierw do pudełka 3 i to ono zostaje — przy v = 7 warunek 3 &gt; 3 jest fałszywy.

Porównaj to z podwójną pętlą z części 3: tam dla każdej liczby trzeba by liczyć, ile razy występuje, czyli około n · n obrotów. Tu jest jedna pętla po danych i jedna po licznikach.

Czy już było? Tablica bool

Czasem nie potrzebujesz wiedzieć, ile razy coś wystąpiło, tylko czy w ogóle. Wtedy wystarczy tablica bool: bylo[x] to „czy wartość x już się pojawiła”. Na start wszystko jest false. Tak policzysz różne wartości i znajdziesz pierwszą powtórkę:

powtorki.cpp
bool bylo[1001] = {};            // wszystko na false
int n;
cin >> n;
int rozne = 0;
int powtorka = -1;               // -1: jeszcze nie było powtórki
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (bylo[x]) {
        if (powtorka == -1) {
            powtorka = x;        // zapamiętaj tylko pierwszą
        }
    } else {
        bylo[x] = true;          // nowa wartość — zaznacz ją
        rozne++;
    }
}
cout << "roznych: " << rozne << "\n";
cout << "pierwsza powtorka: " << powtorka << "\n";
▶ Wejście
8 4 9 4 1 9 9 2 4
▶ Wyjście
roznych: 4 pierwsza powtorka: 4
Pudełka bylo[0] … bylo[9] po wczytaniu danych: zaznaczone (1) są wartości 1, 2, 4 i 9. Wszystkie pozostałe pudełka aż do 1000 zostały na 0.

Pierwsza powtórka pojawia się już na trzeciej pozycji: czwórka była na pierwszej. Kolejne powtórki (dziewiątki, czwórka na końcu) już nie zmieniają wyniku.

Z tej samej tablicy odczytasz też, czego brakuje: przejdź po pudełkach od 1 do n i wypisz te, które zostały false.

Wypisz w kolejności rosnącej

Liczniki pozwalają też ustawić liczby w kolejności od najmniejszej do największej. Pomysł: przejdź po wszystkich możliwych wartościach od najmniejszej i każdą wypisz tyle razy, ile wynosi jej licznik. To sortowanie przez zliczanie. Działa, gdy wartości są niedużymi liczbami całkowitymi. Inne sposoby sortowania poznasz w lekcji o sortowaniu.

rosnaco.cpp
int ile[101] = {};
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    ile[x]++;
}
for (int v = 0; v <= 100; v++) {
    for (int k = 0; k < ile[v]; k++) {   // v tyle razy, ile wystąpiło
        cout << v << " ";
    }
}
cout << "\n";
▶ Wejście
8 42 7 42 0 100 7 7 13
▶ Wyjście
0 7 7 7 13 42 42 100

Wewnętrzna pętla obraca się ile[v] razy — dla wartości, których nie było, zero razy, więc nic nie wypisuje.

Ile to pracy? Jedna pętla po n liczbach i jedna po 101 możliwych wartościach (plus wypisanie n liczb). Nawet dla miliona liczb to chwila.

Liczby ujemne — przesunięcie

Numer pudełka nie może być ujemny. Co, jeśli zliczamy temperatury od −50 do 50 stopni? Przesuwamy wszystko o 50: temperatura x trafia do pudełka x + 50. Wtedy −50 ląduje w pudełku 0, zero w pudełku 50, a 50 stopni w pudełku 100. Przy wypisywaniu przesuwamy z powrotem: pudełko k to temperatura k - 50.

temperatury.cpp
int ile[101] = {};               // temperatury od -50 do 50
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    ile[x + 50]++;               // -50 -> 0, 0 -> 50, 50 -> 100
}
int naj = 0;
for (int k = 1; k <= 100; k++) {
    if (ile[k] > ile[naj]) {
        naj = k;
    }
}
cout << naj - 50 << "\n";        // numer pudełka -> temperatura
▶ Wejście
7 -3 2 -3 -12 2 -3 5
▶ Wyjście
-3
Kiedy tablica liczników? Gdy wartości to liczby całkowite z niedużego zakresu — oceny, oczka, litery, cyfry, temperatury, liczby do kilku milionów. Rozmiar tablicy to liczba możliwych wartości (plus przesunięcie, jeśli są ujemne). Dla wartości do miliarda tablica liczników byłaby za duża — na takie dane poznasz w następnych lekcjach sortowanie i mapy.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int ile[6] = {};
int t[5] = {2, 3, 2, 2, 5};
for (int i = 0; i < 5; i++) {
    ile[t[i]]++;
}
cout << ile[2] << ile[4];
Pokaż odpowiedź
30Dwójka wystąpiła trzy razy, więc ile[2] = 3. Czwórki nie było wcale — ile[4] zostało zerem.
Liczniki liter. Co wypisze ten fragment?
int ile[26] = {};
string s = "ananas";
for (char c : s) {
    ile[c - 'a']++;
}
cout << ile['a' - 'a'] << ile['n' - 'a'];
Pokaż odpowiedź
32W „ananas” są trzy litery a i dwie litery n. 'a' - 'a' to pudełko 0, a 'n' - 'a' — pudełko 13.
Ile różnych? Co wypisze ten fragment?
bool bylo[10] = {};
int t[6] = {3, 1, 3, 3, 7, 1};
int r = 0;
for (int i = 0; i < 6; i++) {
    if (!bylo[t[i]]) {
        bylo[t[i]] = true;
        r++;
    }
}
cout << r;
Pokaż odpowiedź
3Licznik rośnie tylko przy pierwszym spotkaniu wartości: 3, 1 i 7. Powtórki zastają już true.
Sortowanie przez zliczanie. Co wypisze ten fragment?
int ile[5] = {};
int t[6] = {3, 1, 4, 1, 3, 0};
for (int i = 0; i < 6; i++) {
    ile[t[i]]++;
}
for (int v = 0; v < 5; v++) {
    for (int k = 0; k < ile[v]; k++) {
        cout << v << " ";
    }
}
Pokaż odpowiedź
0 1 1 3 3 4Liczniki to: ile[0] = 1, ile[1] = 2, ile[2] = 0, ile[3] = 2, ile[4] = 1. Każdą wartość wypisujemy tyle razy, ile wynosi jej licznik — wychodzi kolejność rosnąca.
Przesunięcie. Co wypisze ten fragment?
int ile[11] = {};
int t[4] = {-5, 0, 5, -5};
for (int i = 0; i < 4; i++) {
    ile[t[i] + 5]++;
}
cout << ile[0] << ile[5] << ile[10];
Pokaż odpowiedź
211−5 trafia do pudełka 0 (dwa razy), 0 do pudełka 5, a 5 do pudełka 10.
Remis. Co wypisze ten fragment?
int ile[5] = {};
int t[5] = {4, 1, 4, 1, 2};
for (int i = 0; i < 5; i++) {
    ile[t[i]]++;
}
int naj = 0;
for (int v = 1; v < 5; v++) {
    if (ile[v] > ile[naj]) {
        naj = v;
    }
}
cout << naj;
Pokaż odpowiedź
1Jedynka i czwórka wystąpiły po dwa razy. Pętla najpierw dochodzi do jedynki, a przy czwórce warunek 2 > 2 jest fałszywy — zostaje mniejsza wartość.
Liczyć czy zaznaczać? Co wypisze ten fragment?
int ile[5] = {};
int t[4] = {2, 2, 2, 4};
for (int i = 0; i < 4; i++) {
    ile[t[i]] = 1;
}
cout << ile[2] + ile[4];
Pokaż odpowiedź
2Tu nie ma ++, tylko = 1 — pudełko jest zaznaczane, a nie liczone. Trzy dwójki dają to samo co jedna. To działa jak tablica bool: wynik 2 to liczba różnych wartości.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Wiersze i kolumny

Tablica, którą znasz, to jeden rząd pudełek. Ale wiele danych ma kształt tabelki: plan lekcji (dni i godziny), oceny w dzienniku (uczniowie i przedmioty), plansza do gry, mapa. Do tego służy tablica dwuwymiarowa: pudełka ułożone w wiersze i kolumny, a każde pudełko ma dwa numery — wiersza i kolumny.

Tabelka pudełek

Tablicę dwuwymiarową tworzysz dwiema parami nawiasów kwadratowych: int t[3][4]; to 3 wiersze po 4 kolumny, czyli 12 pudełek. Do pojedynczego pudełka dobierasz się zapisem t[w][k]: najpierw numer wiersza, potem numer kolumny. Oba numery liczymy od zera.

int t[3][4] — 3 wiersze (numery z lewej) i 4 kolumny (numery u góry). Niebieskie pudełko to t[1][2]: wiersz 1, kolumna 2, wartość 7.
plansza.cpp
int t[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};
cout << t[0][0] << " " << t[1][2] << " " << t[2][3] << "\n";
t[1][2] = 0;
for (int w = 0; w < 3; w++) {          // dla każdego wiersza
    for (int k = 0; k < 4; k++) {      // dla każdej kolumny w tym wierszu
        cout << t[w][k] << " ";
    }
    cout << "\n";                      // koniec wiersza
}
▶ Wyjście
1 7 12 1 2 3 4 5 6 0 8 9 10 11 12
Najpierw wiersz, potem kolumna t[w][k] czytaj jak bilet do kina: rząd, potem miejsce. Wartości startowe podajesz w klamrach wiersz po wierszu — każdy wiersz we własnych klamrach. Tak jak w zwykłej tablicy, int t[3][4] = {}; wypełnia wszystko zerami.

Do przejścia po całej tabelce potrzebne są dwie pętle, jedna w drugiej — dokładnie jak przy prostokątach z gwiazdek w lekcjach o pętlach. Zewnętrzna wybiera wiersz, wewnętrzna przechodzi po kolumnach tego wiersza.

cout &lt;&lt; "\n" stoi poza wewnętrzną pętlą, ale w środku zewnętrznej — dzięki temu wykonuje się raz na wiersz.

Wczytywanie tabelki

W zadaniach tabelka przychodzi zwykle tak: w pierwszym wierszu dwie liczby n i m (liczba wierszy i kolumn), a potem n wierszy po m liczb. Tablicę robimy z zapasem w obu kierunkach i wczytujemy dwiema pętlami — wiersz po wierszu, w każdym wierszu kolumna po kolumnie, czyli w takiej kolejności, w jakiej liczby stoją na wejściu.

wczytanie.cpp
int t[100][100];
int n, m;
cin >> n >> m;                         // n wierszy, m kolumn
for (int w = 0; w < n; w++) {
    for (int k = 0; k < m; k++) {
        cin >> t[w][k];
    }
}
cout << "lewy gorny: " << t[0][0] << "\n";
cout << "prawy dolny: " << t[n - 1][m - 1] << "\n";
cout << "srodek drugiego wiersza: " << t[1][m / 2] << "\n";
▶ Wejście
2 3 1 2 3 4 5 6
▶ Wyjście
lewy gorny: 1 prawy dolny: 6 srodek drugiego wiersza: 5

Prawy dolny róg to ostatni wiersz i ostatnia kolumna: t[n - 1][m - 1] — ta sama zasada co w zwykłej tablicy, tylko w dwóch kierunkach naraz.

Uwaga na rozmiar: int t[100][100] to 10 000 pudełek — spokojnie zmieści się w main. Ale int t[1000][1000] to już milion liczb. Taka tablica musi stać poza main — wyjaśnimy to w części 8.

Sumy wierszy i sumy kolumn

Suma wiersza to suma po kolumnach jednego wiersza: zewnętrzna pętla po wierszach, wewnętrzna po kolumnach. Przy sumach kolumn jest odwrotnie — zamieniamy pętle miejscami: zewnętrzna wybiera kolumnę, wewnętrzna schodzi po wierszach w dół. Zmienna na sumę jest zerowana na początku każdego obrotu zewnętrznej pętli — inaczej sumy kolejnych wierszy by się sklejały.

sumy.cpp
int t[3][4] = {
    {3, 1, 4, 1},
    {5, 9, 2, 6},
    {5, 3, 5, 8}
};
int n = 3, m = 4;
for (int w = 0; w < n; w++) {          // sumy wierszy
    int s = 0;
    for (int k = 0; k < m; k++) {
        s += t[w][k];
    }
    cout << "wiersz " << w << ": " << s << "\n";
}
for (int k = 0; k < m; k++) {          // sumy kolumn: pętle zamienione
    int s = 0;
    for (int w = 0; w < n; w++) {
        s += t[w][k];
    }
    cout << "kolumna " << k << ": " << s << "\n";
}
▶ Wyjście
wiersz 0: 9 wiersz 1: 22 wiersz 2: 21 kolumna 0: 13 kolumna 1: 13 kolumna 2: 11 kolumna 3: 15
Wiersz 1 (niebieski): 5 + 9 + 2 + 6 = 22. Zmienia się numer kolumny, wiersz stoi w miejscu.
Kolumna 2 (niebieska): 4 + 2 + 5 = 11. Zmienia się numer wiersza, kolumna stoi w miejscu.

Ta sama zamiana pętli pozwala wypisać tabelkę „obróconą na bok”: kolumny stają się wierszami. Taką operację nazywamy transpozycją.

transpozycja.cpp
int t[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};
for (int k = 0; k < 3; k++) {          // każda kolumna...
    for (int w = 0; w < 2; w++) {      // ...wypisana jako wiersz
        cout << t[w][k] << " ";
    }
    cout << "\n";
}
▶ Wyjście
1 4 2 5 3 6

Tabelka 2 × 3 zmieniła się w 3 × 2. Pierwsza kolumna (1, 4) jest teraz pierwszym wierszem. Zewnętrzna pętla decyduje, co jest „wierszem” wyniku — tu kolumna oryginału.

Przekątne

W tabelce kwadratowej (n wierszy i n kolumn) są dwie przekątne. Na głównej, od lewego górnego rogu do prawego dolnego, numer wiersza jest równy numerowi kolumny: t[i][i]. Na drugiej, od prawego górnego do lewego dolnego, kolumna idzie od prawej: t[i][n - 1 - i]. Do przejścia po przekątnej wystarczy jedna pętla.

przekatne.cpp
int t[4][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
    {13, 14, 15, 16}
};
int n = 4;
int glowna = 0, druga = 0;
for (int i = 0; i < n; i++) {
    glowna += t[i][i];              // wiersz = kolumna
    druga += t[i][n - 1 - i];       // kolumna od prawej
}
cout << glowna << " " << druga << "\n";
▶ Wyjście
34 34
Główna przekątna (zielona): 1 + 6 + 11 + 16 = 34. Druga przekątna (pomarańczowa): 4 + 7 + 10 + 13 = 34.

Plansza ze znaków

Plansze w zadaniach to często znaki: # to ściana, . to wolne pole, S to start. Najwygodniej wczytać każdy wiersz planszy jako napis — do tablicy napisów string p[100]. Wtedy p[w] to cały wiersz, a p[w][k] to jeden znak w tym wierszu, czyli kratka planszy. Tablica napisów działa więc jak tablica dwuwymiarowa znaków.

mapa.cpp
string p[100];
int n, m;
cin >> n >> m;
for (int w = 0; w < n; w++) {
    cin >> p[w];                 // cały wiersz planszy naraz
}
int sciany = 0;
for (int w = 0; w < n; w++) {
    for (int k = 0; k < m; k++) {
        if (p[w][k] == '#') {
            sciany++;
        }
        if (p[w][k] == 'S') {
            cout << "start: wiersz " << w + 1 << ", kolumna " << k + 1 << "\n";
        }
    }
}
cout << "scian: " << sciany << "\n";
▶ Wejście
3 5 #..#. .S..# ##...
▶ Wyjście
start: wiersz 2, kolumna 2 scian: 5
Ściany (pomarańczowe) i start (niebieski) w p[1][1]. Wypisujemy numery od 1, więc to wiersz 2, kolumna 2.

cin &gt;&gt; p[w] czyta jedno „słowo”, więc działa, gdy w wierszu planszy nie ma spacji — a w zadaniach z planszami zwykle ich nie ma. Można też zrobić tablicę znaków char p[100][100] i wczytywać ją kratka po kratce przez cin &gt;&gt; p[w][k] — cin sam przeskoczy entery.

Sąsiedzi kratki

Mnóstwo zadań z planszami pyta o sąsiadów kratki. Kratka (w, k) ma czterech sąsiadów „przez bok”: górnego (w - 1, k), dolnego (w + 1, k), lewego (w, k - 1) i prawego (w, k + 1). Doliczając sąsiadów „po skosie”, ma ich ośmiu. Kratki na brzegu planszy mają sąsiadów mniej — i tu czai się błąd: p[w - 1][k] dla w = 0 sięga poza tablicę. Zanim zajrzysz do sąsiada, sprawdź, czy on w ogóle istnieje.

Wygodny sposób na wszystkich ośmiu sąsiadów: dwie małe pętle po przesunięciach dw i dk od −1 do 1. Tak działa klasyczna gra Saper — dla każdego pola liczymy, ile min jest dookoła:

saper.cpp
string p[100];
int n, m;
cin >> n >> m;
for (int w = 0; w < n; w++) {
    cin >> p[w];
}
for (int w = 0; w < n; w++) {
    for (int k = 0; k < m; k++) {
        if (p[w][k] == '*') {
            cout << '*';                       // mina zostaje miną
            continue;
        }
        int miny = 0;
        for (int dw = -1; dw <= 1; dw++) {     // wiersz wyżej, ten, niżej
            for (int dk = -1; dk <= 1; dk++) { // kolumna z lewej, ta, z prawej
                int nw = w + dw, nk = k + dk;
                if (nw >= 0 && nw < n && nk >= 0 && nk < m && p[nw][nk] == '*') {
                    miny++;
                }
            }
        }
        cout << miny;
    }
    cout << "\n";
}
▶ Wejście
3 4 *... ..*. ....
▶ Wyjście
*211 12*1 0111

Najważniejsza jest długa linijka z if. Najpierw cztery warunki sprawdzają, czy sąsiad (nw, nk) leży na planszy, a dopiero na końcu zaglądamy do p[nw][nk]. Kolejność ma znaczenie: z lekcji o if pamiętasz, że &amp;&amp; przerywa sprawdzanie przy pierwszym fałszu, więc do kratki spoza planszy program nigdy nie zajrzy.

Przesunięcie dw = 0, dk = 0 to sama kratka. Nie trzeba go pomijać: liczymy tylko pola, które nie są minami, więc sama kratka i tak nie doda miny.

Kierunki w tablicach Czterech sąsiadów przez bok wygodnie zapisać w dwóch tablicach: int dw[4] = {-1, 1, 0, 0}; i int dk[4] = {0, 0, -1, 1};. Kierunek numer d to przesunięcie (dw[d], dk[d]): góra, dół, lewo, prawo. Wtedy wystarczy jedna pętla for (int d = 0; d < 4; d++).
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int t[2][3] = {{1, 2, 3}, {4, 5, 6}};
cout << t[1][0] + t[0][2];
Pokaż odpowiedź
7t[1][0] to wiersz 1, kolumna 0 — czyli 4. t[0][2] to wiersz 0, kolumna 2 — czyli 3. Razem 7.
Pętle zamienione miejscami. Co wypisze ten fragment?
int t[2][3] = {{1, 2, 3}, {4, 5, 6}};
for (int k = 0; k < 3; k++) {
    for (int w = 0; w < 2; w++) {
        cout << t[w][k] << " ";
    }
}
Pokaż odpowiedź
1 4 2 5 3 6Zewnętrzna pętla idzie po kolumnach, więc najpierw wypisujemy całą kolumnę 0 (1 i 4), potem kolumnę 1 (2 i 5), potem kolumnę 2 (3 i 6).
Przekątna. Co wypisze ten fragment?
int t[3][3] = {{2, 0, 1}, {4, 3, 0}, {1, 5, 7}};
int s = 0;
for (int i = 0; i < 3; i++) {
    s += t[i][i];
}
cout << s;
Pokaż odpowiedź
12Główna przekątna to t[0][0], t[1][1] i t[2][2]: 2 + 3 + 7 = 12.
Wypełnianie wzorem. Co wypisze ten fragment?
int t[4][5];
for (int w = 0; w < 4; w++) {
    for (int k = 0; k < 5; k++) {
        t[w][k] = w * 10 + k;
    }
}
cout << t[3][2] << " " << t[2][4];
Pokaż odpowiedź
32 24Każde pudełko dostaje liczbę, której cyfra dziesiątek to numer wiersza, a cyfra jedności — numer kolumny: 3 · 10 + 2 = 32 i 2 · 10 + 4 = 24.
Zapomniane zerowanie. Co wypisze ten fragment?
int t[2][2] = {{1, 2}, {3, 4}};
int s = 0;
for (int w = 0; w < 2; w++) {
    for (int k = 0; k < 2; k++) {
        s += t[w][k];
    }
    cout << s << " ";
}
Pokaż odpowiedź
3 10Pierwszy wiersz daje 3. Ale s nie jest zerowane przed drugim wierszem, więc dalej rośnie: 3 + 3 + 4 = 10. Żeby dostać sumy wierszy 3 i 7, int s = 0; musi stać wewnątrz zewnętrznej pętli.
Plansza ze znaków. Co wypisze ten fragment?
string p[2] = {"#.#", ".##"};
int ile = 0;
for (int k = 0; k < 3; k++) {
    if (p[0][k] == '#' && p[1][k] == '#') {
        ile++;
    }
}
cout << ile;
Pokaż odpowiedź
1Sprawdzamy kolumny: w kolumnie 0 są # i ., w kolumnie 1 — . i #, w kolumnie 2 — dwa #. Tylko jedna kolumna ma ściany w obu wierszach.
Kierunki w tablicach. Co wypisze ten fragment?
string p[3] = {".#.", "#..", ".##"};
int dw[4] = {-1, 1, 0, 0};
int dk[4] = {0, 0, -1, 1};
int w = 1, k = 1, ile = 0;
for (int d = 0; d < 4; d++) {
    if (p[w + dw[d]][k + dk[d]] == '#') {
        ile++;
    }
}
cout << ile;
Pokaż odpowiedź
3Sąsiedzi środka planszy: górny p[0][1] = #, dolny p[2][1] = #, lewy p[1][0] = #, prawy p[1][2] = .. Środek ma wszystkich czterech sąsiadów na planszy, więc tu nie trzeba sprawdzać brzegów.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Duże tablice, sumy prefiksowe i sito

W zadaniach olimpijskich n często sięga 100 000 albo miliona, a pytań bywa tyle samo. Do takich danych potrzebujesz trzech rzeczy: wiedzieć, gdzie trzymać naprawdę duże tablice, umieć szybko odpowiadać na pytania o sumy fragmentów tablicy (sumy prefiksowe) i znaleźć wszystkie liczby pierwsze do miliona w ułamku sekundy (sito Eratostenesa).

Duże tablice deklaruj poza main

Każde pudełko zajmuje pamięć: int — 4 bajty, long long i double — 8 bajtów, bool i char — 1 bajt. Tablica miliona liczb int to więc 4 MB. Zmienne tworzone wewnątrz main trafiają do małego obszaru pamięci zwanego stosem, który ma zwykle tylko kilka megabajtów. Kilkumegabajtowa tablica w main potrafi wysypać program od razu przy starcie — bez żadnego komunikatu, a w sprawdzarce jako błąd wykonania.

Rozwiązanie: duże tablice deklaruj przed main, na samej górze programu. Takie tablice nazywamy globalnymi. Mieszczą się w nich dziesiątki milionów pudełek (do limitu pamięci z treści zadania, zwykle 256 MB), a do tego mają miłą cechę: na start są wyzerowane, bez żadnych klamer.

globalna.cpp
#include <iostream>
using namespace std;

const int MAX = 1000005;
int t[MAX];                    // globalna: poza main, same zera na start

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    long long suma = 0;
    for (int i = 0; i < n; i++) {
        suma += t[i];
    }
    cout << suma << " " << t[n] << "\n";   // t[n] nie wczytaliśmy: 0
    return 0;
}
▶ Wejście
3 5 6 7
▶ Wyjście
18 0
tablicapamięćgdzie
int t[1000]4 KBmoże być w main
int t[100000]400 KBlepiej globalnie
int t[1000000]4 MBtylko globalnie
long long t[1000000]8 MBtylko globalnie
int t[1000][1000]4 MBtylko globalnie
bool t[10000000]10 MBtylko globalnie
int t[100000000]400 MBza dużo przy 256 MB
Szablon na olimpiadę Na górze stała z rozmiarem (z małym zapasem, np. const int MAX = 1000005;) i duże tablice globalne, a w main wczytywanie i obliczenia. Rozmiar licz z ograniczeń w treści: „n ≤ 10⁶” — to milion pudełek plus kilka zapasowych. Pamięć szacuj mnożąc: liczba pudełek × bajty na pudełko.

Numeracja od 1

W zadaniach olimpijskich elementy są zwykle numerowane od 1: „pierwszy dzień”, „k-ty zawodnik”, „suma od a-tego do b-tego”. Często wygodnie jest wtedy trzymać je w pudełkach t[1] … t[n], a pudełko t[0] zostawić puste (globalna tablica i tak ma tam zero). Kosztuje to jedno pudełko, a oszczędza ciągłego odejmowania jedynki — i, jak zaraz zobaczysz, upraszcza wzory. Pętla wygląda wtedy tak: for (int i = 1; i &lt;= n; i++).

Sumy prefiksowe

Zadanie: masz n liczb i q pytań, każde w postaci „ile wynosi suma liczb od a-tej do b-tej?”. Najprościej dla każdego pytania przejść pętlą od a do b. Ale jedno pytanie to do n obrotów, więc wszystkie razem to n · q. Dla n = q = 200 000 wychodzi 40 miliardów obrotów — przy około 100 milionach obrotów na sekundę (pamiętasz z lekcji o pętli for?) program liczyłby kilka minut. Za wolno.

Sztuczka: przygotuj wcześniej sumy wszystkich początków tablicy. Niech p[i] to suma pierwszych i liczb: p[i] = t[1] + t[2] + … + t[i], a p[0] = 0 (suma zera liczb). Taki początek tablicy fachowo nazywa się prefiksem. Każdą sumę prefiksową liczymy z poprzedniej jednym dodawaniem: p[i] = p[i - 1] + t[i] — tak jak w quizie z części 2.

Liczby t[1] … t[7] (pudełko 0 nieużywane). Pytamy o sumę od 3. do 5. liczby: 4 + 1 + 5 = 10.
Sumy prefiksowe: p[5] = 3 + 1 + 4 + 1 + 5 = 14 (zielone), p[2] = 3 + 1 = 4 (pomarańczowe). Odpowiedź to p[5] − p[2] = 14 − 4 = 10.

Dlaczego to działa? p[b] to suma liczb od pierwszej do b-tej. p[a - 1] to suma od pierwszej do (a − 1)-szej. Gdy odejmiesz jedną od drugiej, początek się skróci i zostanie dokładnie suma od a-tej do b-tej:

Suma od a-tej do b-tej liczby t[a] + t[a + 1] + … + t[b] = p[b] - p[a - 1] — jedno odejmowanie zamiast pętli. Dzięki numeracji od 1 pytanie o sumę od pierwszej liczby (a = 1) daje p[b] - p[0], czyli p[b] - 0, bez żadnego wyjątku.
prefiksy.cpp
#include <iostream>
using namespace std;

const int MAX = 200005;
int t[MAX];
long long p[MAX];                  // p[i] = t[1] + ... + t[i]

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {   // numerujemy od 1
        cin >> t[i];
    }
    p[0] = 0;                        // suma zera liczb
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] + t[i];      // poprzednia suma + nowa liczba
    }
    for (int j = 0; j < q; j++) {
        int a, b;
        cin >> a >> b;
        cout << p[b] - p[a - 1] << "\n";
    }
    return 0;
}
▶ Wejście
7 3 3 1 4 1 5 9 2 3 5 1 7 6 6
▶ Wyjście
10 25 9
it[i]p[i − 1] + t[i]p[i]
0——0
130 + 33
213 + 14
344 + 48
418 + 19
559 + 514
6914 + 923
7223 + 225

Pytania: od 3 do 5 — p[5] - p[2] = 14 − 4 = 10; od 1 do 7 — p[7] - p[0] = 25; od 6 do 6 — p[6] - p[5] = 23 − 14 = 9, czyli sama liczba t[6].

Ile to pracy? n dodawań na przygotowanie i po jednym odejmowaniu na pytanie: n + q zamiast n · q. Dla 200 000 liczb i 200 000 pytań to 400 tysięcy działań zamiast 40 miliardów. Tablica p jest w long long, bo suma 200 000 liczb po miliard nie zmieści się w int.

Najlepszy odcinek długości k

Sumy prefiksowe od razu dają sumę każdego odcinka. Na przykład: „w których k kolejnych dniach spadło najwięcej deszczu?”. Odcinek k dni kończący się w dniu i to dni od i - k + 1 do i, więc jego suma to p[i] - p[i - k]. Wystarczy przejrzeć wszystkie możliwe końce i i zapamiętać najlepszy — schematem maksimum z części 3.

okno.cpp
#include <iostream>
using namespace std;

const int MAX = 100005;
long long p[MAX];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        p[i] = p[i - 1] + x;          // samych liczb nie trzeba trzymać
    }
    long long naj = p[k];             // pierwszy odcinek: dni 1 … k
    int start = 1;
    for (int i = k + 1; i <= n; i++) {
        if (p[i] - p[i - k] > naj) {  // odcinek: dni i-k+1 … i
            naj = p[i] - p[i - k];
            start = i - k + 1;
        }
    }
    cout << naj << " od dnia " << start << "\n";
    return 0;
}
▶ Wejście
10 3 2 0 5 1 1 7 3 0 4 4
▶ Wyjście
11 od dnia 5

Sumy kolejnych trójek dni: 7, 6, 7, 9, 11, 10, 7, 8. Najwięcej, 11 (1 + 7 + 3), spadło w dniach od 5. do 7.

Zauważ, że samych liczb nie zapisaliśmy w żadnej tablicy — każdą od razu dodajemy do sumy prefiksowej. Tablica p wystarczy, bo każdą liczbę da się z niej odzyskać: t[i] = p[i] - p[i - 1].

Sito Eratostenesa

Ostatnia sztuczka ma ponad 2000 lat. Jak znaleźć wszystkie liczby pierwsze do n? Można każdą liczbę sprawdzać osobno pętlą do pierwiastka, jak w lekcji o pętli for — ale dla miliona liczb to setki milionów obrotów. Grecki uczony Eratostenes wymyślił coś sprytniejszego: wypisz wszystkie liczby od 2 do n. Weź najmniejszą niewykreśloną — to liczba pierwsza. Wykreśl wszystkie jej wielokrotności. Powtarzaj. Liczby, które przetrwają, to dokładnie liczby pierwsze.

W programie „wykreślenie” to tablica bool: zlozona[x] = true znaczy „x jest wykreślona, bo jest wielokrotnością mniejszej liczby”. Numer pudełka to sama liczba.

Pudełka zlozona[2] … zlozona[30] po przesianiu. Zielone zostały na 0 — to liczby pierwsze: 2, 3, 5, 7, 11, 13, 17, 19, 23 i 29.
sito.cpp
#include <iostream>
using namespace std;

const int MAX = 1000001;
bool zlozona[MAX];                  // globalna: wszystko false

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (!zlozona[i]) {                       // i przetrwało: pierwsza
            for (int j = 2 * i; j <= n; j += i) {
                zlozona[j] = true;               // wykreśl 2i, 3i, 4i, ...
            }
        }
    }
    int ile = 0;
    for (int x = 2; x <= n; x++) {
        if (!zlozona[x]) {
            ile++;
        }
    }
    cout << ile << "\n";
    return 0;
}
▶ Wejście
30
▶ Wyjście
10
▶ Inne wejście
1000000
▶ Wyjście
78498
izlozona[i]?co robimy (dla n = 30)
2niepierwsza — wykreśl 4, 6, 8, …, 30
3niepierwsza — wykreśl 6, 9, 12, …, 30
4takpomiń (wykreślona przez 2)
5niepierwsza — wykreśl 10, 15, 20, 25, 30
6takpomiń
7niepierwsza — wykreśl 14, 21, 28
………

Dla miliona sito wykonuje tylko kilka milionów obrotów — ułamek sekundy. Wewnętrzna pętla dla liczby i obraca się około n / i razy, a dla liczb złożonych w ogóle nie rusza.

Gotowa tablica odpowiada na pytanie „czy x jest pierwsza?” jednym odczytem: !zlozona[x] (dla x ≥ 2). Przygotuj raz, odpowiadaj natychmiast — tak jak przy Fibonaccim w części 2 i przy sumach prefiksowych.

Przyspieszenie dla ciekawych Wykreślanie można zaczynać od j = i * i zamiast od 2 * i: mniejsze wielokrotności i (2i, 3i, …) zostały już wykreślone przez mniejsze liczby pierwsze. Wtedy zewnętrzna pętla może kończyć się na i * i <= n. Wynik jest ten sam, a program trochę szybszy.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.

Tablica globalna. Co wypisze ten program?
int t[5];

int main() {
    t[1] = 7;
    cout << t[0] + t[1] + t[4];
    return 0;
}
Pokaż odpowiedź
7Tablica stoi poza main, więc na start ma same zera. Zmieniliśmy tylko t[1]: 0 + 7 + 0 = 7.
Sumy prefiksowe. Co wypisze ten fragment?
int t[6] = {0, 3, 1, 4, 1, 5};
int p[6];
p[0] = 0;
for (int i = 1; i < 6; i++) {
    p[i] = p[i - 1] + t[i];
}
cout << p[4] - p[1];
Pokaż odpowiedź
6Sumy prefiksowe to 0, 3, 4, 8, 9, 14. p[4] - p[1] = 9 − 3 = 6, czyli t[2] + t[3] + t[4] = 1 + 4 + 1.
Pomyłka o jeden. Ktoś napisał p[b] − p[a] zamiast p[b] − p[a − 1]. Co wypisze program dla a = 2, b = 3?
int t[5] = {0, 5, 5, 5, 5};
int p[5];
p[0] = 0;
for (int i = 1; i < 5; i++) {
    p[i] = p[i - 1] + t[i];
}
int a = 2, b = 3;
cout << p[b] - p[a];
Pokaż odpowiedź
5Prawdziwa suma t[2] + t[3] to 10, a błędny wzór daje 15 − 10 = 5 — gubi pierwszą liczbę przedziału. p[a] zawiera już t[a], więc trzeba odjąć p[a - 1].
Najlepszy odcinek. Co wypisze ten fragment?
int p[6] = {0, 2, 9, 10, 18, 19};
int k = 2;
int naj = p[k];
for (int i = k + 1; i < 6; i++) {
    if (p[i] - p[i - k] > naj) {
        naj = p[i] - p[i - k];
    }
}
cout << naj;
Pokaż odpowiedź
9To sumy prefiksowe liczb 2, 7, 1, 8, 1. Sumy par sąsiadów: 2 + 7 = 9, 7 + 1 = 8, 1 + 8 = 9, 8 + 1 = 9. Największa to 9 — pierwsza para, a kolejne równe jej nie podmieniają wyniku.
Małe sito. Co wypisze ten fragment?
bool z[20] = {};
for (int i = 2; i < 20; i++) {
    if (!z[i]) {
        for (int j = 2 * i; j < 20; j += i) {
            z[j] = true;
        }
    }
}
for (int x = 10; x < 20; x++) {
    if (!z[x]) {
        cout << x << " ";
    }
}
Pokaż odpowiedź
11 13 17 19Po przesianiu niewykreślone zostają liczby pierwsze. Między 10 a 19 to 11, 13, 17 i 19.
Ile razy obróci się wewnętrzna pętla sita dla i = 7 i n = 30?
int n = 30, ile = 0;
for (int j = 2 * 7; j <= n; j += 7) {
    ile++;
}
cout << ile;
Pokaż odpowiedź
3Wykreślamy 14, 21 i 28 — następna wielokrotność, 35, jest już większa od 30. Dla liczby i takich obrotów jest około n / i, dlatego sito jest szybkie.
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

Baza zadań: tablice w praktyce

Znasz już wszystko, co potrzebne: tworzenie tablic i indeksy od zera, wczytywanie i wypisywanie pętlą, sumę, maksimum i szukanie, zamiany, odwracanie i przesuwanie, tablice równoległe i ściągi, tablice liczników, tablice dwuwymiarowe i plansze, a do tego duże tablice globalne, sumy prefiksowe i sito. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym pomysłem, potem zadania średnie — plansze, statki, sudoku, kwadraty magiczne, lider ciągu — a na końcu trudne, z grą w życie, spiralą, ogromnymi liczbami zapisanymi cyfra po cyfrze i wielkim finałem.

Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak modulo, napisy czy setw. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony. A tu masz najważniejsze schematy z lekcji w jednym miejscu:

Ściąga: gotowe schematy z tablicami

Tworzenie

const int MAX = 1005;
int t[MAX];          // z zapasem
int z[5] = {};       // same zera
string d[3] = {"a", "b", "c"};

Indeksy od 0 do rozmiar - 1. Element numer k to t[k - 1].

Wczytaj i wypisz

for (int i = 0; i < n; i++)
    cin >> t[i];
for (int i = n - 1; i >= 0; i--)
    cout << t[i] << " ";

Separator bez końcówki: if (i > 0) cout << ", "; przed elementem.

Maksimum i jego miejsce

int gdzie = 0;
for (int i = 1; i < n; i++)
    if (t[i] > t[gdzie]) gdzie = i;

Start od t[0], nie od zera. > — pierwsze wystąpienie, >= — ostatnie.

Szukanie

int gdzie = -1;
for (int i = 0; i < n; i++)
    if (t[i] == x) { gdzie = i; break; }

-1 znaczy „nie ma”. Bez break — ostatnie wystąpienie.

Sąsiedzi i pary

for (int i = 0; i < n - 1; i++)
    ... t[i] ... t[i + 1] ...
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)

Przy t[i + 1] warunek i < n - 1. Pary: około n² / 2 obrotów.

Zmiany w miejscu

for (int i = 0; i < n / 2; i++)
    swap(t[i], t[n - 1 - i]);
w[(i + k) % n] = t[i];   // obrót o k

W prawo przesuwaj od końca, w lewo od początku. Usuwanie: przesuń w lewo i n--.

Tablica liczników

int ile[101] = {};
ile[x]++;           // 0 ≤ x ≤ 100
ile[c - 'a']++;     // litery
ile[x + 50]++;      // od -50

Najczęstsza wartość = indeks największego licznika. bool bylo[] — „czy już było”.

Tablica dwuwymiarowa

int t[100][100];   // t[wiersz][kolumna]
string p[100];     // plansza: p[w][k]
if (nw >= 0 && nw < n &&
    nk >= 0 && nk < m && ...)

Najpierw sprawdź, czy sąsiad jest na planszy, potem do niego zajrzyj.

Sumy prefiksowe i sito

p[i] = p[i - 1] + t[i];  // od 1
suma = p[b] - p[a - 1];
if (!zlozona[i])
    for (j = 2 * i; j <= n; j += i)
        zlozona[j] = true;

Duże tablice — globalnie, przed main. Sumy w long long.

Jak rozwiązywać zadania z tablicami 1) Zapytaj: czy muszę pamiętać wszystkie dane? Jeśli trzeba do nich wrócić — porównać ze średnią, wypisać od tyłu, połączyć z danymi wczytanymi później — potrzebujesz tablicy. 2) Ile pudełek? Weź największe n z ograniczeń i dodaj zapas; przy setkach tysięcy elementów deklaruj tablicę globalnie. 3) Zdecyduj raz: numeracja od 0 czy od 1 — i trzymaj się jej w całym programie. 4) Przy każdym t[i + 1], t[i - 1] i sąsiedzie na planszy sprawdź brzegi. 5) Wartości z małego zakresu? Pomyśl o tablicy liczników. Dużo pytań o sumy fragmentów? Sumy prefiksowe. 6) Przetestuj skrajności: n = 1, wszystkie liczby równe, największe możliwe wartości.
łatwe

Rozgrzewka · zadania 1–10

Jeden pomysł naraz: zamiana sąsiadów, palindromy, podlewanie ogrodu, sto drzwi, waga szalkowa, wybory, wieże, kino, lista zakupów i pionek na planszy.

1 Zamień sąsiadówłatwe✓ zaliczone Zamień miejscami pierwszą liczbę z drugą, trzecią z czwartą i tak dalej. swapi += 2nieparzyste n Rozwiąż 2 Ciąg-palindromłatwe✓ zaliczone Czy ciąg czyta się tak samo od początku i od końca? Kilka ciągów w jednym teście. t[i] i t[n - 1 - i]flaga boolwiele zestawów Rozwiąż 3 Podlewanie ogrodułatwe✓ zaliczone Zraszacze podlewają grządki od a do b. Ile grządek jest mokrych i które zostały suche? bool mokra[]zaznaczanie przedziałuBRAK Rozwiąż 4 Sto drzwiłatwe✓ zaliczone Osoba numer i przełącza co i-te drzwi. Które drzwi zostaną otwarte? bool otwarte[]co i-ty elementprzełączanie Rozwiąż 5 Waga szalkowałatwe✓ zaliczone Znajdź odważnik, dla którego suma mas po lewej równa się sumie mas po prawej. suma całościsuma lewej stronylong long Rozwiąż 6 Wybory samorządułatwe✓ zaliczone Policz głosy na k kandydatów. Kto wygrał — a może potrzebna jest dogrywka? tablica licznikówmaksimumremis Rozwiąż 7 Wieże na szachownicyłatwe✓ zaliczone Ile par wież atakuje się na szachownicy? Liczniki dla wierszy i kolumn. plansza 8 × 8liczniki wierszy i kolumnc − 1 par Rozwiąż 8 Rezerwacje w kiniełatwe✓ zaliczone Sala kinowa to tablica dwuwymiarowa. Przyjmuj rezerwacje miejsc i odrzucaj zajęte. bool zajete[][]rząd i miejscelicznik wolnych Rozwiąż 9 Lista zakupówłatwe✓ zaliczone Cennik w tablicach równoległych: nazwy i ceny. Policz koszt listy zakupów, szukając każdej nazwy. tablice równoległeszukanie napisugrosze Rozwiąż 10 Pionek na planszyłatwe✓ zaliczone Pionek chodzi po planszy według liter G, D, L, P i nie wchodzi na ściany ani poza planszę. plansza ze znakówkierunkisprawdzanie brzegu Rozwiąż
średnie

Średnie · zadania 11–21

Kilka sztuczek naraz: medaliści, statki, kwadrat magiczny, sudoku, lider ciągu, cieplejszy dzień, liczby bliźniacze, mediana, wywiadówka, wykres i szyfr kolumnowy.

11 Medaliściśrednie✓ zaliczone Z n zawodników wybierz trzech z najlepszymi wynikami — trzy razy szukaj maksimum wśród niewybranych. tablice równoległebool wybrany[]trzy maksima Rozwiąż 12 Statkiśrednie✓ zaliczone Ile statków stoi na planszy? Licz tylko „dzioby” — górne lewe pola statków. plansza ze znakówsąsiad z góry i z lewejlicznik Rozwiąż 13 Kwadrat magicznyśrednie✓ zaliczone Sprawdź sumy wierszy, kolumn i przekątnych — i czy liczby od 1 do n² są użyte po razie. sumy wierszy i kolumnprzekątnebool uzyta[] Rozwiąż 14 Sprawdź sudokuśrednie✓ zaliczone Czy wypełnione sudoku jest poprawne? Wiersze, kolumny i kwadraty 3 × 3 — każdy z cyframi od 1 do 9. tablica 9 × 9bool bylo[10]kwadraty 3 × 3 Rozwiąż 15 Lider ciąguśrednie✓ zaliczone Czy któraś wartość zajmuje ponad połowę ciągu? Liczby są duże, więc tablica liczników odpada. liczenie wystąpieńwięcej niż połowaBRAK Rozwiąż 16 Kiedy będzie cieplej?średnie✓ zaliczone Dla każdego dnia policz, ile dni trzeba czekać na wyższą temperaturę. pętla w pętliszukanie w prawobreak Rozwiąż 17 Liczby bliźniacześrednie✓ zaliczone Pary liczb pierwszych różniących się o 2: ile ich jest do n i która para jest największa? sitop i p + 2tablica globalna Rozwiąż 18 Mediana z licznikówśrednie✓ zaliczone Znajdź środkową wartość po uporządkowaniu — bez sortowania, idąc po licznikach. tablica licznikówsuma licznikówśrodkowy element Rozwiąż 19 Wywiadówkaśrednie✓ zaliczone Tabelka ocen uczniów: najlepszy uczeń, najtrudniejszy przedmiot i lista zagrożonych. tablica 2Dsumy wierszy i kolumntablice równoległe Rozwiąż 20 Wykres słupkowyśrednie✓ zaliczone Narysuj pionowy wykres słupkowy rzutów kostką — wiersz po wierszu, od góry. tablica licznikówwiersze od górypętla w pętli Rozwiąż 21 Szyfr kolumnowyśrednie✓ zaliczone Zapisz tekst wierszami w tabelce o szerokości k, a odczytaj go kolumnami. wiersze i kolumnyi / k oraz i % kco k-ta litera Rozwiąż
trudne

Trudne · zadania 22–29

Spirala, gra w życie, skarbonki z tablicą różnic, sumy prostokątów, dodawanie i silnia olbrzymów, rekordzista dzielników — a na końcu wielki finał: tabela turnieju.

22 Spiralatrudne✓ zaliczone Wypełnij tabelkę liczbami od 1 do n · m po spirali, zgodnie z ruchem wskazówek zegara. tablica 2Dkierunki w tablicachskręt przy przeszkodzie Rozwiąż 23 Gra w życietrudne✓ zaliczone Symuluj k pokoleń gry w życie Conwaya — z drugą tablicą na nowe pokolenie. ośmiu sąsiadówdwie tablicesymulacja Rozwiąż 24 Skarbonkitrudne✓ zaliczone Wiele operacji „dodaj x do skarbonek od a do b” — tablica różnic i jedna suma prefiksowa na końcu. tablica różnicd[a] += x, d[b + 1] -= xsumy prefiksowe Rozwiąż 25 Sumy prostokątówtrudne✓ zaliczone Sumy prefiksowe w dwóch wymiarach: suma dowolnego prostokąta z czterech odczytów. sumy prefiksowe 2Ddodaj i odejmij kawałkilong long Rozwiąż 26 Dodawanie olbrzymówtrudne✓ zaliczone Dodaj dwie liczby mające do 1000 cyfr — cyfra po cyfrze, z przeniesieniem, jak w słupku. cyfry w tablicyprzeniesienieod cyfry jedności Rozwiąż 27 Silnia ze wszystkimi cyframitrudne✓ zaliczone Policz n! dla n do 500 dokładnie — liczba w tablicy cyfr mnożona przez kolejne liczby. cyfry w tablicymnożenie pisemneprzeniesienie Rozwiąż 28 Rekordzista dzielnikówtrudne✓ zaliczone Która liczba do n ma najwięcej dzielników? Policz dzielniki wszystkich liczb naraz, jak w sicie. sito dzielnikówd[j]++ dla wielokrotnościtablica globalna Rozwiąż 29 Wielki finał: tabela turniejutrudne✓ zaliczone Tabela „każdy z każdym”: policz punkty i ułóż ranking — wybierając najlepszego wśród niewybranych. tablica 2D znakówtablice równoległebool wybrany[]kilka kryteriów Rozwiąż

Częste błędy i dobre praktyki

0️⃣
Indeksy od zera
Tablica int t[5] ma pudełka od t[0] do t[4]. Pudełka t[5] nie ma. Element numer k (liczony od 1) leży w t[k - 1].
🚧
Poza tablicą — bez ostrzeżenia
C++ nie sprawdza indeksów. t[-1] czy t[n] da przypadkową liczbę, zepsuje inną zmienną albo wysypie program — często dopiero w sprawdzarce.
🔁
i < n, nie i <= n
Pętla po tablicy to for (int i = 0; i < n; i++). Gdy w środku jest t[i + 1], warunek brzmi i < n - 1; przy t[i - 1] zacznij od i = 1.
🗑️
Śmieci w nowej tablicy
Tablica utworzona w main nie jest wyzerowana. Liczniki i sumy zaczynaj od int t[N] = {}; — albo zrób tablicę globalną, która startuje z zerami.
📦
Rozmiar z zapasem
Rozmiar tablicy bierz z ograniczeń zadania, z kilkoma pudełkami zapasu: const int MAX = 1005;. Nie pisz int t[n] po wczytaniu n.
🏔️
Maksimum od t[0]
Szukając największego (albo najmniejszego) elementu, zacznij od t[0], a nie od 0. Przy samych liczbach ujemnych start od zera da wynik, którego nie ma w danych.
📋
Całość — tylko pętlą
Tablicy nie skopiujesz znakiem =, a == b nie porównuje zawartości, a cout << t wypisze adres. Kopiuj, porównuj i wypisuj pudełko po pudełku.
↔️
Przesuwaj z właściwej strony
Przesuwasz w prawo — idź od końca, w lewo — od początku. Inaczej jedna wartość rozleje się po całej tablicy. Przy obrocie o k najprościej pisać do drugiej tablicy.
🔢
Licznik: wartość to indeks
ile[x]++ wymaga tablicy o rozmiarze co najmniej największa wartość + 1. Dla wartości ujemnych przesuń indeks: ile[x + 50].
🌍
Duże tablice poza main
Tablice od około 100 000 elementów deklaruj przed main. W środku funkcji milion liczb potrafi wysypać program przy starcie.
➕
p[b] - p[a - 1]
Suma od a-tego do b-tego elementu z sum prefiksowych — z a - 1, nie z a. Numeruj od 1, ustaw p[0] = 0 i trzymaj sumy w long long.
🧭
Najpierw brzeg, potem kratka
Na planszy warunek nw >= 0 && nw < n && nk >= 0 && nk < m musi stać przed p[nw][nk]. Pamiętaj też: t[w][k] — najpierw wiersz, potem kolumna.

Co dalej?

Tablice to fundament wszystkiego, co przed Tobą: prawie każde zadanie olimpijskie zaczyna się od wczytania danych do tablicy. Następna lekcja to napisy — a napis to w gruncie rzeczy tablica znaków, więc wiele z tego, co tu poznałeś, od razu się przyda. Potem przyjdą pary, vector — tablica, która sama rośnie — i sortowanie. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.