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ć.
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.
Pierwsza tablica
Pudełka z numerami, indeksy od zera, wczytywanie, wypisywanie i wypełnianie tablicy pętlą.
Przeglądanie i zmiany
Suma, maksimum, szukanie, sąsiedzi — a potem zamiana, odwracanie, przesuwanie, usuwanie i wstawianie.
Kilka tablic i liczniki
Tablice równoległe, tablice-ściągi, nowa tablica z wybranych elementów i tablica liczników.
Plansze i olimpiada
Tablice dwuwymiarowe i plansze, duże tablice globalne, sumy prefiksowe i sito Eratostenesa.
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:
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
cout << e << " " << d << " " << c << " " << b << " " << a << "\n";
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:
int t[5]; // tablica t: pięć pudełek typu int
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ę:
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";
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.
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";
| obrót | i | instrukcja | skutek |
|---|---|---|---|
| 1. | 0 | cin >> t[0] | t[0] = 1 |
| 2. | 1 | cin >> t[1] | t[1] = 2 |
| 3. | 2 | cin >> t[2] | t[2] = 3 |
| 4. | 3 | cin >> t[3] | t[3] = 4 |
| 5. | 4 | cin >> t[4] | t[4] = 5 |
| — | 5 | warunek 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.
| który element | indeks | w tablicy powyżej |
|---|---|---|
| pierwszy | 0 | t[0] = 7 |
| drugi | 1 | t[1] = 3 |
| trzeci | 2 | t[2] = 9 |
| k-ty | k - 1 | np. czwarty: t[3] = 2 |
| ostatni w tablicy rozmiaru n | n - 1 | t[4] = 5 |
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:
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";
| po linijce | t[0] | t[1] | t[2] | t[3] | t[4] |
|---|---|---|---|---|---|
int t[5]; | ? | ? | ? | ? | ? |
t[0] = 10; | 10 | ? | ? | ? | ? |
t[1] = 20; | 10 | 20 | ? | ? | ? |
t[2] = t[0] + t[1]; | 10 | 20 | 30 | ? | ? |
t[3] = t[2] * 2; | 10 | 20 | 30 | 60 | ? |
t[4] = t[3] - 1; | 10 | 20 | 30 | 60 | 59 |
t[1]++; | 10 | 21 | 30 | 60 | 59 |
t[0] += 5; | 15 | 21 | 30 | 60 | 59 |
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ć:
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";
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.
int t[5]; // bez klamer!
for (int i = 0; i < 5; i++) {
cout << t[i] << " ";
}
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.
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]
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.
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
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.
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";
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ę.
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
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";
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.
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.
Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
int t[4] = {8, 6, 4, 2};
cout << t[1];
Pokaż odpowiedź
t[0] to 8, a t[1] — drugie pudełko — to 6.int t[5] = {3, 1};
cout << t[0] + t[1] + t[4];
Pokaż odpowiedź
t[2], t[3] i t[4] — dostały zera. 3 + 1 + 0 = 4.int t[3] = {5, 7, 9};
t[0] = t[2];
t[2] = t[0] + 1;
cout << t[0] << " " << t[1] << " " << t[2];
Pokaż odpowiedź
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.int t[5] = {4, 3, 2, 1, 0};
cout << t[t[1]];
Pokaż odpowiedź
t[1] to 3. Potem bierzemy t[3], czyli 1.int t[4] = {10, 20, 30, 40};
int i = 1;
cout << t[i + 1] << " " << t[i] + 1;
Pokaż odpowiedź
t[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.string s[3] = {"ala", "ma", "kota"};
cout << s[2] << s[0];
Pokaż odpowiedź
s[2] to trzeci napis, „kota”, a s[0] — pierwszy, „ala”. Wychodzą sklejone, bo żadnej spacji nie wypisaliśmy.int t[] = {1, 1, 2, 3, 5, 8};
cout << t[5] - t[0];
Pokaż odpowiedź
t[5] = 8. 8 − 1 = 7.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];
4Pokaż odpowiedź
dlugosc[3] = 30. A dlugosc[4] to już maj, który ma 31 dni — klasyczny błąd przesunięcia o jeden.8 ćwiczeń do tej części
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ę.
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:
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.
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";
To trzy pętle, które będziesz pisać najczęściej. Porównaj je:
| pętla | po 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 >= 0, żeby nie pominąć pudełka zero.
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.
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:
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";
}
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";
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 <=, 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.
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";
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:
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";
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ę.
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";
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:
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";
}
| i | f[i - 2] | f[i - 1] | f[i] |
|---|---|---|---|
| 2 | 0 | 1 | 1 |
| 3 | 1 | 1 | 2 |
| 4 | 1 | 2 | 3 |
| 5 | 2 | 3 | 5 |
| 6 | 3 | 5 | 8 |
| … | … | … | … |
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.
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";
W pierwszym obrocie i = 0, więc warunek i > 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.
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";
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.
Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
int t[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i += 2) {
cout << t[i];
}
Pokaż odpowiedź
t[0], t[2] i t[4] — bez spacji, bo żadnej nie wypisujemy.int t[5] = {9, 8, 7, 6, 5};
for (int i = 4; i >= 1; i--) {
cout << t[i];
}
Pokaż odpowiedź
i = 1, więc t[0] (czyli 9) nie zostało wypisane. Żeby dojść do pierwszego pudełka, warunek musi brzmieć i >= 0.int t[5];
for (int i = 0; i < 5; i++) {
t[i] = i * 3;
}
cout << t[4] + t[1];
Pokaż odpowiedź
t[4] to 12, t[1] to 3, razem 15.int t[6];
t[0] = 1;
for (int i = 1; i < 6; i++) {
t[i] = t[i - 1] * 3;
}
cout << t[5];
Pokaż odpowiedź
t[5] to 3 do piątej.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ź
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.int t[4] = {1, 2, 3, 4};
for (int i = 1; i <= 4; i++) {
cout << t[i] << " ";
}
Pokaż odpowiedź
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++).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ź
i = 0. Potem t[0] = 3, t[3] = 1, t[1] = 0. Po trzech skokach i to 0.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ź
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.8 ćwiczeń do tej części
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ę.
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ę.
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";
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ę.
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";
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] > suma / n sprawdź t[i] * n > 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:
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";
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].
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";
| i | t[i] | t[gdzie] | t[i] > t[gdzie]? | gdzie |
|---|---|---|---|---|
| start | — | 4 | — | 0 |
| 1 | 9 | 4 | tak | 1 |
| 2 | 2 | 9 | nie | 1 |
| 3 | 9 | 9 | nie | 1 |
| 4 | −1 | 9 | nie | 1 |
| 5 | 7 | 9 | nie | 1 |
| 6 | 2 | 9 | nie | 1 |
Dziewiątka stoi w dwóch miejscach: w pudełkach 1 i 3. Przy i = 3 warunek 9 > 9 jest fałszywy, więc zostaje pierwsza dziewiątka. Wypisujemy gdzie + 1, bo „pozycja” to numer liczony od 1.
Gdy zamienisz > na >=, równa wartość też podmieni indeks — dostaniesz ostatnią dziewiątkę, pozycję 4. Najmniejszy element znajdziesz tak samo, ze znakiem <.
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ą.
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";
}
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 < n - 1.
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";
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.
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.
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";
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ą.
Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
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ź
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ź
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ź
maks zostaje 0 — a zera w ogóle nie ma w tablicy! Poprawny wynik to −2. Dlatego zawsze zaczynamy od maks = t[0].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ź
>= druga dziewiątka (w pudełku 3) też podmienia indeks, więc zostaje ostatnie wystąpienie największej wartości.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ź
break kończy pętlę, więc dalszych siódemek program już nie widzi.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ź
break pętla idzie do końca, a każda kolejna siódemka nadpisuje g. Zostaje ostatnia — w pudełku 4.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ź
i < 4, czyli n - 1, żeby t[i + 1] nie wyszło poza tablicę.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ź
j zaczyna od i + 1.8 ćwiczeń do tej części
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ę.
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.
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";
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ę.
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";
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.
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";
| i | n − 1 − i | zamiana | tablica po zamianie |
|---|---|---|---|
| start | — | — | 1 2 3 4 5 |
| 0 | 4 | t[0] ↔ t[4] | 5 2 3 4 1 |
| 1 | 3 | t[1] ↔ t[3] | 5 4 3 2 1 |
| 2 | warunek 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.
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ą:
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";
Warunek l < 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.
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";
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";
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:
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";
| i | instrukcja | tablica po |
|---|---|---|
| start | — | 1 2 3 4 5 |
| 1 | t[1] = t[0] | 1 1 3 4 5 |
| 2 | t[2] = t[1] | 1 1 1 4 5 |
| 3 | t[3] = t[2] | 1 1 1 1 5 |
| 4 | t[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.
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";
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.
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";
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";
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.
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";
| i | t[i] | zostaje? | k po | początek tablicy |
|---|---|---|---|---|
| 0 | 0 | nie | 0 | — |
| 1 | 3 | tak | 1 | 3 |
| 2 | 0 | nie | 1 | 3 |
| 3 | 0 | nie | 1 | 3 |
| 4 | 5 | tak | 2 | 3 5 |
| 5 | 1 | tak | 3 | 3 5 1 |
| 6 | 0 | nie | 3 | 3 5 1 |
| 7 | 2 | tak | 4 | 3 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.
int a[3] = {1, 2, 3};
int b[3];
b = a; // BŁĄD KOMPILACJI: tablicy nie da się przypisać
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";
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].
Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
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ź
int t[2] = {4, 9};
t[0] = t[1];
t[1] = t[0];
cout << t[0] << " " << t[1];
Pokaż odpowiedź
t[0] i czwórka przepada na zawsze. Druga przepisuje tę samą dziewiątkę z powrotem. Do zamiany potrzebna jest zmienna pomocnicza albo swap.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ź
i < n / 2.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ź
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.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ź
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.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ź
t[0] to 6, a t[n - 1] = t[3] to 9.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ź
k to liczba zostawionych elementów.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ź
b dostało kwadraty: 1, 4, 9. Zmiana a[2] na 0 nie rusza już b, więc 0 + 9 = 9.8 ćwiczeń do tej części
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ę.
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.
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";
| i | imie[i] | punkty[i] |
|---|---|---|
| 0 | Ola | 17 |
| 1 | Jan | 23 |
| 2 | Ewa | 19 |
| 3 | Igor | 23 |
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 > 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.
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";
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:
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";
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ą:
// 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";
| litera | s[i] − 'a' | pkt[…] | suma |
|---|---|---|---|
| q | 16 | 10 | 10 |
| u | 20 | 1 | 11 |
| i | 8 | 1 | 12 |
| z | 25 | 10 | 22 |
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ść.
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";
| n przed | największa mieszcząca się | wypisz | n po |
|---|---|---|---|
| 1994 | 1000 | M | 994 |
| 994 | 900 | CM | 94 |
| 94 | 90 | XC | 4 |
| 4 | 4 | IV | 0 |
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.
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";
| a[i] | b[j] | bierzemy |
|---|---|---|
| 1 | 2 | 1 (z a) |
| 4 | 2 | 2 (z b) |
| 4 | 3 | 3 (z b) |
| 4 | 10 | 4 (z a) |
| 6 | 10 | 6 (z a) |
| 9 | 10 | 9 (z a) |
| 12 | 10 | 10 (z b) |
| 12 | 15 | 12 (z a) |
| — | 15 | a 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.
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.
Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
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ź
imie bierzemy to samo pudełko — Jan.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ź
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ź
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.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ź
b[0] dostaje a[3] = 4, a b[3] dostaje a[0] = 1. Tablica b to odwrócona a.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ź
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ź
'k' - 'a' (czyli 10) ma 5 punktów, a pudełko 'o' - 'a' (czyli 14) — 1 punkt. „kok” to 5 + 1 + 5 = 11.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ź
a się kończy, a ostatnia pętla dopisuje resztę z b, czyli 8. Wynik jest uporządkowany.8 ćwiczeń do tej części
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ę.
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
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";
}
| ocena | ile[1] | ile[2] | ile[3] | ile[4] | ile[5] | ile[6] |
|---|---|---|---|---|---|---|
| start | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 0 | 1 | 0 |
| 6 | 0 | 0 | 1 | 0 | 1 | 1 |
| 5 | 0 | 0 | 1 | 0 | 2 | 1 |
| 2 | 0 | 1 | 1 | 0 | 2 | 1 |
| 5 | 0 | 1 | 1 | 0 | 3 | 1 |
| 3 | 0 | 1 | 2 | 0 | 3 | 1 |
| 4 | 0 | 1 | 2 | 1 | 3 | 1 |
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:
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";
}
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.
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', ...
}
}
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 > przy remisie wygrywa mniejsza wartość, bo przeglądamy pudełka od najmniejszego numeru.
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";
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 > 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ę:
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";
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.
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";
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.
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
Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
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ź
ile[2] = 3. Czwórki nie było wcale — ile[4] zostało zerem.int ile[26] = {};
string s = "ananas";
for (char c : s) {
ile[c - 'a']++;
}
cout << ile['a' - 'a'] << ile['n' - 'a'];
Pokaż odpowiedź
'a' - 'a' to pudełko 0, a 'n' - 'a' — pudełko 13.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ź
true.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ź
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.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ź
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ź
2 > 2 jest fałszywy — zostaje mniejsza wartość.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ź
++, 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.8 ćwiczeń do tej części
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ę.
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] = {
{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
}
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 << "\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.
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";
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.
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";
}
Ta sama zamiana pętli pozwala wypisać tabelkę „obróconą na bok”: kolumny stają się wierszami. Taką operację nazywamy transpozycją.
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";
}
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.
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";
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.
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";
cin >> 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 >> 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:
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";
}
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 && 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.
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++).
Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
int t[2][3] = {{1, 2, 3}, {4, 5, 6}};
cout << t[1][0] + t[0][2];
Pokaż odpowiedź
t[1][0] to wiersz 1, kolumna 0 — czyli 4. t[0][2] to wiersz 0, kolumna 2 — czyli 3. Razem 7.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ź
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ź
t[0][0], t[1][1] i t[2][2]: 2 + 3 + 7 = 12.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ź
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ź
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.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ź
# i ., w kolumnie 1 — . i #, w kolumnie 2 — dwa #. Tylko jedna kolumna ma ściany w obu wierszach.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ź
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.8 ćwiczeń do tej części
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ę.
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.
#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;
}
| tablica | pamięć | gdzie |
|---|---|---|
int t[1000] | 4 KB | może być w main |
int t[100000] | 400 KB | lepiej globalnie |
int t[1000000] | 4 MB | tylko globalnie |
long long t[1000000] | 8 MB | tylko globalnie |
int t[1000][1000] | 4 MB | tylko globalnie |
bool t[10000000] | 10 MB | tylko globalnie |
int t[100000000] | 400 MB | za dużo przy 256 MB |
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 <= 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.
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:
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.
#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;
}
| i | t[i] | p[i − 1] + t[i] | p[i] |
|---|---|---|---|
| 0 | — | — | 0 |
| 1 | 3 | 0 + 3 | 3 |
| 2 | 1 | 3 + 1 | 4 |
| 3 | 4 | 4 + 4 | 8 |
| 4 | 1 | 8 + 1 | 9 |
| 5 | 5 | 9 + 5 | 14 |
| 6 | 9 | 14 + 9 | 23 |
| 7 | 2 | 23 + 2 | 25 |
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.
#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;
}
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.
#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;
}
| i | zlozona[i]? | co robimy (dla n = 30) |
|---|---|---|
| 2 | nie | pierwsza — wykreśl 4, 6, 8, …, 30 |
| 3 | nie | pierwsza — wykreśl 6, 9, 12, …, 30 |
| 4 | tak | pomiń (wykreślona przez 2) |
| 5 | nie | pierwsza — wykreśl 10, 15, 20, 25, 30 |
| 6 | tak | pomiń |
| 7 | nie | pierwsza — 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.
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.
Najpierw odpowiedz w myślach — rozpisz sobie pudełka tablicy na kartce i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
int t[5];
int main() {
t[1] = 7;
cout << t[0] + t[1] + t[4];
return 0;
}
Pokaż odpowiedź
main, więc na start ma same zera. Zmieniliśmy tylko t[1]: 0 + 7 + 0 = 7.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ź
p[4] - p[1] = 9 − 3 = 6, czyli t[2] + t[3] + t[4] = 1 + 4 + 1.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ź
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].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ź
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ź
int n = 30, ile = 0;
for (int j = 2 * 7; j <= n; j += 7) {
ile++;
}
cout << ile;
Pokaż odpowiedź
7 ćwiczeń do tej części
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ę.
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.
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.
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.
Ś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.
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.