Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Ten odcinek omawia dokładnie ten temat.
Co już umiesz i czego się nauczysz
Ta lekcja zakłada, że przerobiłeś lekcje Typy zmiennych, Input / Output, If / Else i — przede wszystkim — While loop. Z lekcji o while pamiętasz, że każda pętla ma trzy elementy: start (zmienna z wartością początkową przed pętlą), warunek (kiedy pętla ma się jeszcze kręcić) i zmianę (coś w ciele, co przybliża warunek do fałszu). Znasz też liczniki, sumy, rekordy, break, continue i pętlę w pętli.
Pętla for nie umie niczego, czego nie umiałby while. Ale zbiera te trzy elementy w jednym miejscu, na samej górze pętli. Dzięki temu jednym spojrzeniem widać, skąd licznik startuje, dokąd dojdzie i jak szybko — a to sprawia, że pętle z licznikiem pisze się szybciej i myli rzadziej. W programach olimpijskich for pojawia się kilka razy częściej niż while.
Uczymy się tak samo jak poprzednio: przepisuj przykłady do swojego edytora i uruchamiaj je, przy pytaniach „Co wypisze program?” najpierw śledź program w głowie albo na kartce, a dopiero potem sprawdzaj odpowiedź, i po każdej części rób ćwiczenia w sprawdzarce. Nie przerabiaj wszystkiego za jednym razem — rób przerwy po kolejnych częściach.
Jak działa for
Budowa i kolejność wykonywania, zakresy, kroki i liczenie obrotów, zasięg licznika.
for w zadaniach
Wczytywanie danych, break i continue, kiedy for, a kiedy while, napisy i for (char c : s).
Pętla w pętli
Rysunki z wierszy i kolumn, pary liczb i sprawdzanie wszystkich możliwości.
Czy zdąży?
Ile obrotów wykona komputer w sekundę, liczenie obrotów wzorem i pętle do pierwiastka.
cout << i << " " w pętli niczego nie psuje. Uważaj natomiast na spacje i znaki w środku wiersza oraz na wielkość liter.
Mapa lekcji
for — while w jednej linijce
Przypomnij sobie najprostszą pętlę z lekcji o while: wypisanie liczb od 1 do 5. Trzy elementy pętli są tam porozrzucane po trzech różnych miejscach: start nad pętlą, warunek w nawiasie, a zmiana — na samym dole ciała. W krótkim programie to nie problem, ale gdy ciało pętli ma dwadzieścia linijek, zmiana ginie gdzieś na dole i łatwo o niej zapomnieć.
Pętla for (po angielsku „dla”, czytaj: „for”) robi dokładnie to samo, tylko wszystkie trzy elementy zapisuje w jednym nawiasie, oddzielone średnikami. Porównaj:
int i = 1; // start
while (i <= 5) { // warunek
cout << i << " ";
i++; // zmiana
}
// start; warunek; zmiana — wszystko w jednym miejscu
for (int i = 1; i <= 5; i++) {
cout << i << " ";
}
Oba programy wypisują to samo i działają tak samo. Wersja z for jest krótsza, ale ważniejsze jest co innego: z samej pierwszej linijki od razu wiesz, że licznik i zacznie od 1, skończy na 5 i będzie rósł o 1. Nie trzeba szukać zmiany na dole ciała.
Budowa pętli for
start
Wykonuje się jeden raz, zanim pętla w ogóle ruszy. Zwykle tworzy licznik: int i = 1.
warunek
Sprawdzany przed każdym obrotem — dokładnie jak w while. Prawdziwy: wykonaj ciało. Fałszywy: koniec pętli.
zmiana
Wykonuje się po każdym obrocie, po ostatniej instrukcji ciała, a przed kolejnym sprawdzeniem warunku. Najczęściej i++.
dwa średniki w nawiasie
Oddzielają trzy części. Po zmianie średnika nie ma, a za nawiasem — tak jak przy while — nie stawiasz średnika.
#include <iostream>
using namespace std;
int main() {
for (int i = 1; i <= 3; i++) {
cout << "Obrot nr " << i << "\n";
}
cout << "Koniec\n";
return 0;
}
Kolejność wykonywania — obrót po obrocie
To najważniejsza rzecz w całej lekcji, więc przyjrzyj się jej dokładnie. Choć zmiana i++ stoi w nawiasie przed ciałem, wykonuje się po nim. Prześledźmy obroty.cpp krok po kroku:
| Krok | co się wykonuje | wartość i | efekt |
|---|---|---|---|
| 1 | int i = 1 (start) | 1 | tworzy licznik — tylko raz |
| 2 | i <= 3 | 1 | true → ciało |
| 3 | ciało | 1 | wypisuje „Obrot nr 1” |
| 4 | i++ (zmiana) | 2 | i rośnie |
| 5 | i <= 3 | 2 | true → ciało |
| 6 | ciało | 2 | wypisuje „Obrot nr 2” |
| 7 | i++ | 3 | i rośnie |
| 8 | i <= 3 | 3 | true → ciało |
| 9 | ciało | 3 | wypisuje „Obrot nr 3” |
| 10 | i++ | 4 | i rośnie |
| 11 | i <= 3 | 4 | false → koniec pętli |
| 12 | instrukcja za pętlą | — | wypisuje „Koniec” |
Przepisywanie while na for
Każdą pętlę while z licznikiem przepiszesz na for w trzech ruchach: start znad pętli przenosisz na początek nawiasu, warunek zostaje w środku, a zmianę z dołu ciała przenosisz na koniec nawiasu. Ciało pętli robi się o jedną linijkę krótsze.
int n;
cin >> n;
int i = 2;
while (i <= n) {
cout << i << " ";
i += 3;
}
int n;
cin >> n;
for (int i = 2; i <= n; i += 3) {
cout << i << " ";
}
Zmiana nie musi być i++ — może to być dowolna instrukcja zmieniająca licznik: i += 3, i--, i *= 2. Wrócimy do tego w następnej części.
Od 1 do n i „powtórz n razy”
Dwa schematy z lekcji o while zapisują się w for szczególnie zgrabnie. Pierwszy — przejście po liczbach od 1 do n. Drugi — powtórzenie czegoś dokładnie n razy, gdzie licznik tylko liczy obroty. Ten drugi ma w C++ swoją „kanoniczną” postać, którą zobaczysz w tysiącach programów: for (int i = 0; i < n; i++).
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cout << i << " ";
}
cout << "\n";
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cout << "Hej! ";
}
cout << "\n";
Dlaczego start od 0 i warunek <? Licznik przyjmuje wartości 0, 1, …, n − 1 — dokładnie n różnych liczb. Za chwilę, przy napisach, zobaczysz, że numeracja od zera jest w C++ naturalna (pierwszy znak napisu to s[0]), więc ten zapis bardzo się przydaje. Ale for (int i = 1; i <= n; i++) też daje n obrotów — wybierasz ten, który w danym zadaniu jest wygodniejszy.
Odliczanie i licznik w obliczeniach
int n;
cin >> n;
for (int i = n; i >= 1; i--) {
cout << i << "... ";
}
cout << "Start!\n";
for (int i = 1; i <= 5; i++) {
cout << i << " " << i * i << " " << 2 * i + 1 << "\n";
}
Odliczanie: licznik startuje od n, warunek i >= 1 pozwala dojść do jedynki, a zmiana i-- zmniejsza licznik. Tabela: licznik to zwykła zmienna typu int, więc możesz go mnożyć, dodawać i podstawiać do wzorów — w każdym obrocie dostajesz inną wartość.
Suma w pętli for — także z ułamkami
Akumulatory z lekcji o while działają w for bez żadnych zmian: zmienna przed pętlą, dokładanie w ciele, wypisanie po pętli. Policzmy sumę 1 + 1/2 + 1/3 + … + 1/n. Tu czai się pułapka z lekcji o typach:
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
double suma = 0;
for (int i = 1; i <= 4; i++) {
suma += 1 / i; // dzielenie całkowite!
}
cout << fixed << setprecision(4) << suma << "\n";
return 0;
}
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
double suma = 0;
for (int i = 1; i <= 4; i++) {
suma += 1.0 / i; // dzielenie z ułamkiem
}
cout << fixed << setprecision(4) << suma << "\n";
return 0;
}
W lewej wersji 1 / i to dzielenie dwóch liczb całkowitych: dla i = 1 daje 1, a dla i ≥ 2 — zero. Suma wynosi więc 1. Wystarczy jedna kropka: 1.0 / i to już dzielenie z ułamkiem i wychodzi poprawne 1 + 0,5 + 0,3333 + 0,25 = 2,0833.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
for (int i = 1; i <= 4; i++) {
cout << i;
}
Pokaż odpowiedź
for (int i = 0; i < 6; i++) {
cout << "*";
}
Pokaż odpowiedź
for (int i = 10; i > 0; i -= 3) {
cout << i << " ";
}
Pokaż odpowiedź
for (int i = 1; i <= 3; i++) {
cout << i;
cout << "-";
}
Pokaż odpowiedź
int s = 0;
for (int i = 2; i <= 8; i += 2) {
s += i;
}
cout << s;
Pokaż odpowiedź
for (int i = 5; i <= 3; i++) {
cout << "X";
}
cout << "koniec";
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ę.
Skąd, dokąd i co ile
Nagłówek pętli for to w praktyce opis zakresu: skąd licznik startuje, do jakiej wartości dojdzie i o ile zmienia się w każdym kroku. Kto umie szybko czytać i pisać takie nagłówki, ten pisze pętle bez błędów. Oto najczęstsze z nich — z wartościami licznika i liczbą obrotów:
| nagłówek | wartości licznika | obrotów |
|---|---|---|
for (int i = 0; i < n; i++) | 0, 1, …, n − 1 | n |
for (int i = 1; i <= n; i++) | 1, 2, …, n | n |
for (int i = n; i >= 1; i--) | n, n − 1, …, 1 | n |
for (int i = n - 1; i >= 0; i--) | n − 1, …, 1, 0 | n |
for (int i = a; i <= b; i++) | a, a + 1, …, b | b − a + 1 |
for (int i = a; i <= b; i += k) | a, a + k, a + 2k, … | (b − a) / k + 1 |
for (int p = 1; p <= n; p *= 2) | 1, 2, 4, 8, … | ok. log₂ n + 1 |
Wzory w ostatniej kolumnie przydają się częściej, niż myślisz: pozwalają sprawdzić program bez uruchamiania go, a w części 8 — policzyć, czy zdąży się wykonać. Zatrzymajmy się przy nich na chwilę.
Ile liczb jest od a do b?
Ile liczb całkowitych jest od 3 do 7? Odejmowanie daje 7 − 3 = 4, ale liczb jest pięć: 3, 4, 5, 6, 7. Odejmowanie liczy „odstępy” między liczbami, a liczb jest zawsze o jedną więcej niż odstępów — tak samo jak słupków w płocie jest o jeden więcej niż przęseł. Dlatego od a do b jest b − a + 1 liczb.
Ze skokiem co k jest podobnie: od a do b mieści się (b − a) / k pełnych skoków (dzielenie całkowite!), a liczb jest o jedną więcej. Sprawdźmy na przykładzie: od 1 do 20 co 4.
int a = 1, b = 20, k = 4;
int ile = 0;
for (int i = a; i <= b; i += k) {
cout << i << " ";
ile++;
}
cout << "\nobrotow: " << ile;
cout << ", ze wzoru: " << (b - a) / k + 1 << "\n";
(20 − 1) / 4 = 19 / 4 = 4 (dzielenie całkowite) — tyle jest pełnych skoków. Plus pierwszy obrót dla i = 1: razem 5. Następna wartość, 21, nie spełnia warunku i <= 20.
Wzór działa tylko wtedy, gdy a ≤ b. Gdy a > b, warunek jest fałszywy od razu i pętla wykona się zero razy — taki zakres nazywamy pustym.
W dół, co k, razy 2
Zmiana w nawiasie może być dowolną instrukcją, która zmienia licznik. Ważne tylko, żeby start, warunek i zmiana do siebie pasowały: gdy licznik maleje, warunek musi mieć postać „dopóki jest większy niż…”, a gdy rośnie — „dopóki jest mniejszy niż…”.
int a, b;
cin >> a >> b;
for (int i = b; i >= a; i--) {
cout << i << " ";
}
cout << "\n";
for (long long p = 1; p <= 1000000000000LL; p *= 10) {
cout << p << " ";
}
cout << "\n";
int a, b, k;
cin >> a >> b >> k;
for (int i = a; i <= b; i += k) {
cout << i << " ";
}
cout << "\n";
Licznik nie musi być typu int. W pętli z potęgami dziesiątki dochodzimy do biliona, więc licznik jest long long. Liczba 1000000000000LL ma na końcu literki LL — to informacja dla kompilatora, że ta stała ma typ long long. Przy samych cyfrach kompilator i tak by się domyślił, ale z LL od razu widać, że liczba jest duża.
Licznik żyje tylko w pętli
Zmienna utworzona w nawiasie for — int i = 1 — istnieje tylko w tej pętli. Za klamrą zamykającą pętlę już jej nie ma. To wygodne (licznik nie zaśmieca reszty programu, a w następnej pętli możesz znowu napisać int i), ale bywa zaskakujące:
for (int i = 1; i <= 5; i++) {
cout << i << " ";
}
cout << i; // błąd: i już nie istnieje
int i; // licznik przed pętlą
for (i = 1; i * i <= 50; i++) {
// nic nie robimy — tylko szukamy
}
cout << "pierwszy kwadrat ponad 50: " << i * i << "\n";
Komunikat kompilatora brzmi: 'i' was not declared in this scope — „i nie zostało zadeklarowane w tym zasięgu”. Jeśli wartość licznika jest potrzebna po pętli, utwórz zmienną przed pętlą, a w nawiasie tylko nadaj jej wartość startową (i = 1, bez int). Tak jak w prawym przykładzie, gdzie po pętli i wynosi 8 — pierwsza liczba, której kwadrat przekroczył 50.
Dwa liczniki w jednym nawiasie
W części startowej i w części zmiany możesz zmieścić więcej niż jedną instrukcję — oddzielasz je przecinkami. Przydaje się, gdy dwa liczniki idą razem, na przykład jeden w górę, a drugi w dół:
for (int i = 1, j = 10; i < j; i++, j -= 2) {
cout << i << " " << j << "\n";
}
Kolejne pary (i, j): (1, 10), (2, 8), (3, 6), (4, 4). Przy ostatniej warunek 4 < 4 jest fałszywy. Uwaga: przecinki stoją tylko w starcie i w zmianie. Warunek jest jeden — jeśli chcesz sprawdzać dwie rzeczy, łączysz je przez && albo ||.
Nie zmieniaj licznika w ciele
Kompilator pozwala zmieniać licznik również w ciele pętli — ale wtedy nagłówek przestaje mówić prawdę. Ktoś (także Ty za tydzień) czyta for (int i = 0; i < 10; i++) i spodziewa się dziesięciu obrotów, a tu nagle w ciele stoi i += 2. Jeśli krok ma być inny niż 1, wpisz go w nawias. Zobacz, jak łatwo się pomylić:
for (int i = 0; i < 10; i++) {
cout << i << " ";
i += 2; // ukryta druga zmiana
}
cout << "\n";
for (int i = 0; i < 10; i += 3) {
cout << i << " ";
}
cout << "\n";
Lewa pętla zwiększa licznik dwa razy w obrocie: o 2 w ciele i o 1 w nagłówku — razem o 3. Wynik jest taki sam jak po prawej, ale żeby to zobaczyć, trzeba było przeczytać całe ciało. Zasada: cała „logika licznika” w nawiasie.
Skacz od razu tam, gdzie trzeba
Ostatni przykład tej części łączy wszystko. Chcemy wypisać wielokrotności liczby k z przedziału od a do b. Pierwszy pomysł: przejść po wszystkich liczbach i sprawdzać if (i % k == 0). Działa — ale gdy przedział ma miliard liczb, a wielokrotności jest kilka, pętla wykonuje miliard niepotrzebnych obrotów. Lepiej od razu znaleźć pierwszą wielokrotność i skakać co k:
long long a, b, k;
cin >> a >> b >> k;
long long start = (a + k - 1) / k * k; // pierwsza wielokrotność >= a
for (long long x = start; x <= b; x += k) {
cout << x << " ";
}
cout << "\n";
Skąd wzór (a + k - 1) / k * k? Dzielenie całkowite a / k zaokrągla w dół, a dodanie k - 1 przed dzieleniem zamienia to w zaokrąglenie w górę (ten sam trik co przy autobusach w lekcji o if). Wynik mnożymy z powrotem przez k i mamy najmniejszą wielokrotność k, która nie jest mniejsza od a.
Dla a = 10 i k = 7: (10 + 6) / 7 = 2, a 2 · 7 = 14. Druga pętla wykonuje tylko 4 obroty, choć przedział ma 3 miliardy liczb.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
int ile = 0;
for (int i = 5; i <= 25; i += 5) {
ile++;
}
cout << ile;
Pokaż odpowiedź
for (int i = 1; i < 100; i *= 3) {
cout << i << " ";
}
Pokaż odpowiedź
for (int i = 8, j = 0; j < i; i--, j++) {
cout << i - j << " ";
}
Pokaż odpowiedź
int ile = 0;
for (int i = -3; i <= 3; i++) {
ile++;
}
cout << ile;
Pokaż odpowiedź
int i;
for (i = 0; i < 20; i += 6) {
}
cout << i;
Pokaż odpowiedź
for (int i = 0; i < 6; i++) {
cout << i;
i++;
}
Pokaż odpowiedź
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ę.
Wczytywanie n danych pętlą for
Najczęstszy początek zadania olimpijskiego brzmi: „W pierwszym wierszu jest liczba n, a w kolejnych n liczb”. Z lekcji o while umiesz już takie dane wczytać. Z for robi się to krócej i czytelniej, bo od razu widać, że pętla wykona się dokładnie n razy:
int n;
cin >> n;
long long suma = 0;
int i = 0;
while (i < n) {
int x;
cin >> x;
suma += x;
i++;
}
cout << suma << "\n";
int n;
cin >> n;
long long suma = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
suma += x;
}
cout << suma << "\n";
Licznik i służy tu tylko do odliczenia n obrotów — w ciele go nie używamy. Wszystko, czego nauczyłeś się o akumulatorach, działa bez zmian: suma, licznik warunkowy, iloczyn, średnia. Zmienia się tylko „opakowanie” pętli.
Licznik jako numer pozycji
Gdy zadanie pyta „na której pozycji…”, wygodnie jest liczyć od 1 do n — wtedy licznik i jest od razu numerem wczytywanej liczby. Znajdźmy największą liczbę i miejsce, w którym wystąpiła po raz pierwszy, oraz najmniejszą i miejsce, w którym wystąpiła po raz ostatni:
int n;
cin >> n;
int maks = 0, gdzieMaks = 0;
int mini = 0, gdzieMini = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i == 1 || x > maks) { // pierwsze wystąpienie
maks = x;
gdzieMaks = i;
}
if (i == 1 || x <= mini) { // ostatnie wystąpienie
mini = x;
gdzieMini = i;
}
}
cout << "max " << maks << " na miejscu " << gdzieMaks << "\n";
cout << "min " << mini << " na miejscu " << gdzieMini << "\n";
Dwie sztuczki naraz. Pierwsza: warunek i == 1 || … sprawia, że przy pierwszej liczbie rekord ustawia się zawsze — nie trzeba wczytywać jej osobno przed pętlą. Druga: o tym, czy zapamiętamy pierwsze, czy ostatnie wystąpienie, decyduje jeden znak. Przy > równa wartość nie zmienia rekordu (zostaje pierwsze), a przy <= — zmienia (zostaje ostatnie).
Kilka danych w jednym obrocie
W jednym obrocie możesz wczytać tyle wartości, ile ma jeden „wiersz” danych — na przykład cenę i ilość z paragonu albo imię i ocenę ucznia. Zmienna typu string wczytuje się tak samo jak liczba:
int n;
cin >> n;
long long razem = 0;
for (int i = 0; i < n; i++) {
long long cena, ilosc;
cin >> cena >> ilosc;
cout << cena * ilosc << "\n";
razem += cena * ilosc;
}
cout << "razem: " << razem << "\n";
int n;
cin >> n;
string kto;
int najlepsza = 0;
for (int i = 0; i < n; i++) {
string imie;
int ocena;
cin >> imie >> ocena;
if (ocena > najlepsza) {
najlepsza = ocena;
kto = imie; // imię „jedzie” razem z rekordem
}
}
cout << kto << " (" << najlepsza << ")\n";
W prawym przykładzie razem z najlepszą oceną zapamiętujemy imię jej właściciela. To bardzo częsty schemat: rekord i „metka” rekordu zmieniają się zawsze razem, w tym samym if. Ola ma też piątkę, ale 5 > 5 to fałsz, więc zostaje Kuba — ten, który był wcześniej.
Poprzednia liczba w pętli for
Gdy porównujesz sąsiednie liczby, pierwszą wczytujesz przed pętlą, a pętla przechodzi po pozostałych n − 1 liczbach. W for zapisujesz to jako licznik od 1 do n − 1, czyli for (int i = 1; i < n; i++):
int n, poprz;
cin >> n >> poprz;
int zmiany = 0;
for (int i = 1; i < n; i++) {
int x;
cin >> x;
if ((poprz > 0 && x < 0) || (poprz < 0 && x > 0)) {
zmiany++;
}
poprz = x;
}
cout << zmiany << "\n";
Pary sąsiadów: (3, −1) zmiana, (−1, −4) nie, (−4, 2) zmiana, (2, 5) nie, (5, −6) zmiana — razem 3.
Może kusić skrót poprz * x < 0 (iloczyn liczb o różnych znakach jest ujemny). Działa dla małych liczb, ale gdy dane sięgają miliarda, iloczyn nie mieści się w int i wynik jest przypadkowy. Porównania z zerem są bezpieczne zawsze.
Rekord na bieżąco: najniższy stan konta
Rekord nie musi dotyczyć wczytanych liczb — może dotyczyć czegoś, co liczysz po drodze. Na koncie jest 0 zł, potem kolejno wpłaty (dodatnie) i wypłaty (ujemne). Jaki był najniższy stan konta? Po każdej operacji aktualizujesz saldo i od razu porównujesz je z rekordem:
int n;
cin >> n;
long long saldo = 0, najnizej = 0; // 0 to stan początkowy
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
saldo += x;
if (saldo < najnizej) {
najnizej = saldo;
}
}
cout << saldo << " " << najnizej << "\n";
| operacja | saldo | najniżej |
|---|---|---|
| start | 0 | 0 |
| +100 | 100 | 0 |
| −250 | −150 | −150 |
| +50 | −100 | −150 |
| +300 | 200 | −150 |
| −20 | 180 | −150 |
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
int n;
cin >> n;
int ile = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 5) ile++;
}
cout << ile;
4 3 7 2 8Pokaż odpowiedź
int n, maks = 0, gdzie = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x >= maks) {
maks = x;
gdzie = i;
}
}
cout << gdzie;
5 2 6 6 1 6Pokaż odpowiedź
int n, s = 0;
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
s += a * b;
}
cout << s;
3 5 4 2 10 1 1Pokaż odpowiedź
int n, poprz;
cin >> n >> poprz;
int ile = 0;
for (int i = 1; i < n; i++) {
int x;
cin >> x;
if (x > poprz) ile++;
poprz = x;
}
cout << ile;
5 1 3 2 5 4Pokaż odpowiedź
int n;
cin >> n;
int s = 0, m = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s += x;
if (s < m) m = s;
}
cout << m;
4 10 -30 15 -20Pokaż odpowiedź
int n, best = 0;
string kto;
cin >> n;
for (int i = 0; i < n; i++) {
string imie;
int p;
cin >> imie >> p;
if (p > best) {
best = p;
kto = imie;
}
}
cout << kto;
3 Ola 3 Ala 6 Ela 6Pokaż odpowiedź
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ę.
Kiedy for, kiedy while — i co z break i continue
Skoro for i while potrafią to samo, to po co dwie pętle? Chodzi o czytelność. Każdą z nich da się zastąpić drugą, ale zwykle jedna pasuje do zadania wyraźnie lepiej. Prosta reguła, której trzymają się prawie wszyscy programiści:
| Sytuacja | Pętla | Przykład |
|---|---|---|
| wiadomo z góry, ile obrotów albo po jakim zakresie chodzi licznik | for | n liczb na wejściu, od a do b, każdy znak napisu, wiersze rysunku |
| pętla kręci się „aż coś się stanie”, a liczby obrotów nie da się przewidzieć | while | dane do zera, while (cin >> x), cyfry liczby, Collatz, algorytm Euklidesa |
| ciało musi wykonać się co najmniej raz | do … while | rzut kostką, liczenie cyfr zera |
Dla porządku: for z pustym startem i pustą zmianą — for (; warunek; ) — to dokładnie while (warunek). A cyfry liczby da się rozebrać pętlą for: for (long long k = n; k > 0; k /= 10). To poprawne i czasem wygodne, ale gdy nie ma „licznika”, tylko zmieniająca się wartość, while jest zwykle czytelniejszy. Nie ma tu sztywnych zakazów — chodzi o to, żeby kod dało się łatwo przeczytać.
break w pętli for — szukanie
break działa w for tak samo jak w while: kończy pętlę natychmiast, bez wykonywania zmiany i bez sprawdzania warunku. Typowe zastosowanie to szukanie pierwszego elementu, który spełnia warunek:
int a, b, k;
cin >> a >> b >> k;
int wynik = 0; // 0 = nie znaleziono
for (int x = a; x <= b; x++) {
if (x % k == 0) {
wynik = x;
break;
}
}
if (wynik == 0) {
cout << "BRAK\n";
} else {
cout << wynik << "\n";
}
Dla pierwszego wejścia pętla sprawdza 20 i 21 — przy 21 znajduje wielokrotność siódemki i kończy pracę. Pozostałych 19 liczb nie sprawdza wcale.
Zamiast break można też dopisać do warunku pętli „i jeszcze nie znalazłem”: for (int x = a; x <= b && wynik == 0; x++). Oba sposoby są dobre — wybierz ten, który lepiej czytasz.
continue w pętli for — bez pułapki
Pamiętasz pułapkę z lekcji o while? continue przeskakiwało resztę ciała razem z i++ na jego końcu i program się zawieszał. W pętli for tego problemu nie ma: continue przeskakuje resztę ciała, ale zmiana z nawiasu i tak się wykona, zanim pętla wróci do warunku. To jeden z powodów, dla których for jest bezpieczniejszy.
for (int i = 1; i <= 12; i++) {
if (i % 3 == 0) {
continue; // i++ wykona się mimo to
}
cout << i << " ";
}
cout << "\n";
int n;
cin >> n;
long long suma = 0;
int pominiete = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x <= 0) {
pominiete++;
continue;
}
suma += x;
}
cout << suma << " " << pominiete << "\n";
for bez warunku: for (;;)
Każdą z trzech części nagłówka można pominąć — średniki muszą jednak zostać. Gdy pominiesz warunek, pętla uznaje go za zawsze prawdziwy: for (;;) to to samo co while (true). Taka pętla ma sens tylko z break w środku. Przydaje się, gdy licznik jest potrzebny, ale nie wiadomo, dokąd dojdzie:
long long s;
cin >> s;
long long suma = 0;
for (long long i = 1; ; i++) { // bez warunku!
suma += i;
if (suma > s) {
cout << i << " " << suma << "\n";
break;
}
}
long long n;
cin >> n;
for (long long x = n + 1; ; x++) {
bool pierwsza = true;
for (long long d = 2; d * d <= x; d++) {
if (x % d == 0) {
pierwsza = false;
break; // kończy tylko pętlę po d
}
}
if (pierwsza) {
cout << x << "\n";
break; // kończy pętlę po x
}
}
W prawym programie są dwa break-i i każdy kończy tylko swoją pętlę: pierwszy przerywa szukanie dzielnika (wiadomo już, że x nie jest pierwsza), drugi — szukanie kolejnych kandydatów (znaleźliśmy odpowiedź). Liczba 1 000 000 007 jest pierwsza i bardzo często pojawia się w zadaniach olimpijskich — jeszcze ją spotkasz.
for (;;) i for (int i = 1; ; i++) zakończą się tylko przez break. Zanim wyślesz program, upewnij się, że break na pewno się kiedyś wykona — że szukana rzecz na pewno istnieje. Liczba pierwsza większa od n zawsze się znajdzie, a suma 1 + 2 + … zawsze w końcu przekroczy s, więc tutaj jesteśmy bezpieczni.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
for (int i = 1; i <= 10; i++) {
if (i * i > 20) {
break;
}
cout << i << " ";
}
Pokaż odpowiedź
for (int i = 1; i <= 6; i++) {
if (i % 2 == 1) continue;
cout << i;
}
Pokaż odpowiedź
int ile = 0;
for (int i = 0; ; i += 7) {
ile++;
if (i > 30) break;
}
cout << ile;
Pokaż odpowiedź
int znalezione = 0;
int i;
for (i = 10; i <= 50 && znalezione == 0; i++) {
if (i % 13 == 0) znalezione = i;
}
cout << znalezione << " " << i;
Pokaż odpowiedź
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (j == 2) break;
cout << i << j << " ";
}
}
Pokaż odpowiedź
int n = 1000, k = 0;
for (; n > 1; ) {
n /= 10;
k++;
}
cout << k;
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ę.
Napis znak po znaku
Napis to ciąg znaków ponumerowanych od zera: w słowie kot znak s[0] to k, s[1] to o, a s[2] to t. Długość napisu podaje s.length() (albo — to samo — s.size()). Przejście po wszystkich znakach to więc pętla po indeksach od 0 do s.length() - 1, czyli dokładnie ten „kanoniczny” for, który już znasz:
string s;
cin >> s;
for (int i = 0; i < s.length(); i++) {
cout << i << ": " << s[i] << "\n";
}
Warunek i < s.length(), a nie <= — bo ostatni indeks to długość minus jeden. Napis s[3] w słowie kot nie istnieje; odczyt spoza napisu to błąd, którego kompilator nie wyłapie, a program zachowa się nieprzewidywalnie.
Kompilator może przy i < s.length() wypisać ostrzeżenie o porównaniu liczby ze znakiem i bez znaku (signedness). Długość jest typu bez liczb ujemnych — dopóki i nie jest ujemne, nic złego się nie dzieje.
Separator między elementami
Częste zadanie: wypisz elementy oddzielone jakimś znakiem — przecinkiem, myślnikiem — ale bez tego znaku na początku i na końcu. Spacji na końcu sprawdzarka nie widzi, ale myślnik już tak. Sztuczka: wypisuj separator przed każdym elementem oprócz pierwszego.
string s;
cin >> s;
for (int i = 0; i < s.length(); i++) {
if (i > 0) {
cout << "-";
}
cout << s[i];
}
cout << "\n";
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
if (i > 1) {
cout << ", ";
}
cout << i * i;
}
cout << "\n";
Pętla „dla każdego znaku”: for (char c : s)
Gdy numer pozycji nie jest Ci potrzebny, a chcesz tylko obejrzeć każdy znak po kolei, C++ ma krótszy zapis: for (char c : s). Czytaj go: „dla każdego znaku c w napisie s”. W każdym obrocie zmienna c dostaje kolejny znak — bez liczników, bez s[i] i bez ryzyka wyjścia poza napis.
string s;
getline(cin, s); // cały wiersz, ze spacjami
int ile = 0;
for (char c : s) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'y') {
ile++;
}
}
cout << ile << "\n";
string s;
cin >> s;
int suma = 0;
for (char c : s) {
if (c >= '0' && c <= '9') {
suma += c - '0'; // znak cyfry → liczba
}
}
cout << suma << "\n";
Przypomnienie z lekcji o typach: znak '7' to nie liczba 7, tylko kod znaku. Ponieważ kody cyfr stoją w tabeli ASCII po kolei, c - '0' zamienia znak cyfry na jej wartość. Tak samo litery: c - 'a' to numer litery w alfabecie (od 0), a c - 'a' + 'A' zamienia małą literę na wielką.
Zmienianie znaków napisu
Do pozycji napisu można też zapisywać: s[i] = 'X'; podmienia i-ty znak. Gdy chcesz zmieniać znaki w pętli „dla każdego”, musisz dopisać &: for (char &c : s). Bez & zmienna c jest tylko kopią znaku i zmiany przepadają. Z & pracujesz na oryginale.
string s;
getline(cin, s);
for (int i = 0; i < s.length(); i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
s[i] = s[i] - 'a' + 'A';
}
}
cout << s << "\n";
string s;
getline(cin, s);
for (char &c : s) { // & — pracuj na oryginale
if (c >= 'a' && c <= 'z') {
c = c - 'a' + 'A';
}
}
cout << s << "\n";
Spróbuj u siebie usunąć & z prawej wersji — program wypisze napis bez zmian. To jedna z tych pułapek, których kompilator nie zgłosi, bo kod jest poprawny, tylko robi coś innego, niż chciałeś.
Budowanie nowego napisu
Zamiast zmieniać napis, często łatwiej zbudować nowy: zaczynasz od pustego "" i dokładasz znaki na koniec przez +=. Tak usuniesz spacje albo zapiszesz słowo wspak:
string s;
getline(cin, s);
string wynik = "";
for (char c : s) {
if (c != ' ') {
wynik += c;
}
}
cout << wynik << "\n";
string s;
cin >> s;
string w = "";
for (int i = s.length() - 1; i >= 0; i--) {
w += s[i];
}
cout << w << "\n";
W pętli wstecz licznik musi być typu int: po zerze schodzi do −1 i warunek i >= 0 kończy pętlę. Gdyby licznik był typu bez znaku (takiego jak długość napisu), zamiast −1 dostałby ogromną liczbę i pętla nigdy by się nie skończyła.
Dwa końce naraz: palindrom
Słowo jest palindromem, gdy czytane od tyłu jest takie samo (kajak, anna). Nie trzeba go odwracać: wystarczy porównać pierwszy znak z ostatnim, drugi z przedostatnim i tak dalej. Znak numer i od początku ma parę numer n - 1 - i od końca, a sprawdzić trzeba tylko pierwszą połowę:
string s;
cin >> s;
int n = s.length();
bool ok = true;
for (int i = 0; i < n / 2; i++) {
if (s[i] != s[n - 1 - i]) {
ok = false;
break;
}
}
cout << (ok ? "TAK" : "NIE") << "\n";
| i | s[i] | s[n − 1 − i] | równe? |
|---|---|---|---|
| 0 | k | k | tak |
| 1 | a | a | tak |
| 2 | 2 < 5 / 2 = 2 fałsz — środek nie ma pary | ||
Zapis ok ? "TAK" : "NIE" to operator ?: z lekcji o if — wybiera jeden z dwóch napisów.
Dwa napisy i krok co dwa
string s, t;
cin >> s >> t; // ta sama długość
int ile = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] != t[i]) {
ile++;
}
}
cout << ile << "\n";
string s;
cin >> s;
for (int i = 0; i + 1 < s.length(); i += 2) {
char t = s[i];
s[i] = s[i + 1];
s[i + 1] = t;
}
cout << s << "\n";
Lewy program: jeden licznik obsługuje oba napisy naraz — porównuje znaki na tych samych pozycjach. Prawy: pętla idzie co dwa i zamienia sąsiadów miejscami przez trzecią zmienną. Warunek i + 1 < s.length() pilnuje, żeby para miała drugi znak — przy nieparzystej długości ostatnia litera zostaje na miejscu.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
string s = "abcdef";
for (int i = 1; i < s.length(); i += 2) {
cout << s[i];
}
Pokaż odpowiedź
string s = "Ala ma kota";
int ile = 0;
for (char c : s) {
ile++;
}
cout << ile;
Pokaż odpowiedź
string s = "kot";
for (char c : s) {
c = 'x';
}
cout << s;
Pokaż odpowiedź
string s = "a1b2c3";
int x = 0;
for (char c : s) {
if (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
}
}
cout << x;
Pokaż odpowiedź
string s = "kajak", w = "";
for (int i = 0; i < s.length(); i++) {
if (s[i] != 'a') w += s[i];
}
cout << w;
Pokaż odpowiedź
string s = "abcdcba";
int n = s.length(), ile = 0;
for (int i = 0; i < n / 2; i++) {
ile++;
}
cout << ile;
Pokaż odpowiedź
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ę.
for w for: wiersze i kolumny
Pętlę w pętli poznałeś już przy while: zewnętrzna liczy wiersze, wewnętrzna — elementy w wierszu, i w każdym obrocie zewnętrznej wewnętrzna wykonuje wszystkie swoje obroty. Z for zagnieżdżanie jest jeszcze prostsze, bo znika najczęstszy błąd: licznik wewnętrznej pętli tworzy się w jej nawiasie, więc przy każdym wejściu do niej sam startuje od nowa.
int a = 3, b = 6;
for (int w = 1; w <= a; w++) { // wiersze
for (int k = 1; k <= b; k++) { // kolumny
cout << "*";
}
cout << "\n";
}
Porównaj z wersją z while: nie trzeba pamiętać o int k = 0; przed wewnętrzną pętlą ani o k++ na jej końcu. Wszystko jest w nagłówku, a nagłówek wykonuje się od początku przy każdym obrocie zewnętrznej pętli.
Nazwy liczników są dowolne, ale warto, żeby coś mówiły: w i k (wiersz, kolumna) albo klasyczne i i j. Ważne tylko, żeby były różne — za chwilę zobaczysz, co się dzieje, gdy nie są.
Trójkąty: wewnętrzna pętla zależy od zewnętrznej
Najciekawsze kształty powstają, gdy liczba obrotów wewnętrznej pętli zależy od numeru wiersza. Wystarczy zmienić start albo warunek wewnętrznej pętli, żeby dostać trójkąt w inną stronę. Przy rysunkach zawsze zrób najpierw tabelkę: numer wiersza → ile znaków jakiego rodzaju.
w znaków w wierszu w
for (int w = 1; w <= n; w++) {
for (int k = 1; k <= w; k++)
cout << "*";
cout << "\n";
}
Wiersz 1 — jedna gwiazdka, wiersz n — n gwiazdek.
n − w + 1 znaków
for (int w = 1; w <= n; w++) {
for (int k = w; k <= n; k++)
cout << "*";
cout << "\n";
}
Wewnętrzna startuje od w — im dalszy wiersz, tym krócej.
kropki, potem gwiazdki
for (int w = 1; w <= n; w++) {
for (int k = 1; k <= n - w; k++)
cout << ".";
for (int k = 1; k <= w; k++)
cout << "*";
cout << "\n";
}
Dwie wewnętrzne pętle po kolei — trójkąt dosunięty do prawej.
int n = 4;
for (int w = 1; w <= n; w++) {
for (int k = 1; k <= n - w; k++) {
cout << ".";
}
for (int k = 1; k <= w; k++) {
cout << "*";
}
cout << "\n";
}
int n = 5;
for (int w = 1; w <= n; w++) {
for (char c = 'A'; c < 'A' + w; c++) {
cout << c;
}
cout << "\n";
}
W prawym przykładzie licznikiem wewnętrznej pętli jest znak. To działa, bo znaki są w środku liczbami (kodami ASCII): c++ przechodzi do następnej litery, a 'A' + w to litera stojąca w pozycji o w dalej niż A.
Pary liczb: j od i + 1
Pętla w pętli to też sposób na przejrzenie wszystkich par. Jeśli para (1, 3) i para (3, 1) to dla Ciebie to samo, a pary (2, 2) nie chcesz, wewnętrzna pętla startuje od i + 1. Każda para pojawia się wtedy dokładnie raz:
int n = 4, ile = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
cout << "(" << i << "," << j << ") ";
ile++;
}
}
cout << "\npar: " << ile << "\n";
Dla i = 1 wewnętrzna pętla robi 3 obroty, dla i = 2 — dwa, dla i = 3 — jeden, a dla i = 4 — zero. Razem 3 + 2 + 1 = 6. Ogólnie par jest n · (n − 1) / 2 — przyda się w części 8.
Gdyby wewnętrzna pętla startowała od j = i, doszłyby pary (1,1), (2,2), …; a od j = 1 — każda para pojawiłaby się dwa razy, raz jako (1,3), raz jako (3,1).
Tabelka z nagłówkami
Pętle zagnieżdżone i setw z lekcji Input / Output to razem przepis na równe tabelki. Przed tabelką wypisujemy wiersz nagłówka (też pętlą), a w każdym wierszu tabelki — najpierw jego opis, potem pętlę z wartościami:
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int n = 4;
cout << "x |";
for (int k = 1; k <= n; k++) {
cout << setw(4) << k;
}
cout << "\n--+";
for (int k = 1; k <= n; k++) {
cout << "----";
}
cout << "\n";
for (int w = 1; w <= n; w++) {
cout << w << " |";
for (int k = 1; k <= n; k++) {
cout << setw(4) << w * k;
}
cout << "\n";
}
return 0;
}
setw(4) działa tylko na najbliższą wypisywaną rzecz, więc stoi w pętli przed każdą liczbą. Kreskę pod nagłówkiem też rysuje pętla — po 4 myślniki na każdą kolumnę, bo tyle zajmuje każde pole.
Uwaga na ten sam licznik w obu pętlach
int ile = 0;
for (int i = 0; i < 3; i++) {
for (int i = 0; i < 4; i++) { // drugie i!
ile++;
}
}
cout << ile << "\n";
Ten program działa (wychodzi 3 · 4 = 12), ale tylko przez przypadek: wewnętrzne int i to nowa zmienna, która przesłania zewnętrzne i. W środku nie masz już dostępu do numeru wiersza. Wystarczy, że w ciele zechcesz użyć obu liczników — i program zrobi coś zupełnie innego, niż myślisz.
Jeszcze gorzej, gdy wewnętrzna pętla nie tworzy nowej zmiennej, tylko zmienia zewnętrzną (for (i = 0; …)) — wtedy zewnętrzna pętla może się nigdy nie skończyć. Zasada: każda pętla ma swój licznik o innej nazwie.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 4; j++) {
cout << "*";
}
}
Pokaż odpowiedź
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= i; j++) {
cout << j;
}
cout << " ";
}
Pokaż odpowiedź
for (int i = 1; i <= 3; i++) {
for (int j = i; j <= 3; j++) {
cout << j;
}
cout << " ";
}
Pokaż odpowiedź
int ile = 0;
for (int i = 1; i <= 5; i++) {
for (int j = i + 1; j <= 5; j++) {
ile++;
}
}
cout << ile;
Pokaż odpowiedź
for (char c = 'a'; c <= 'e'; c += 2) {
cout << c;
}
Pokaż odpowiedź
int s = 0;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (i == j) s += i * j;
}
}
cout << s;
Pokaż odpowiedź
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ę.
Sprawdź wszystkie możliwości
Wiele zagadek, które na lekcji matematyki rozwiązuje się sprytnym rachunkiem, komputer rozwiązuje… siłą. Skoro potrafi sprawdzić miliony przypadków w ułamku sekundy, można po prostu wypróbować każdą możliwą odpowiedź i zostawić te, które pasują. Ta metoda nazywa się przeszukiwaniem zupełnym (po angielsku brute force, „brutalna siła”) i jest pierwszym pomysłem, od którego warto zacząć prawie każde zadanie.
Przepis zawsze jest ten sam: 1) ustal, czego szukasz i jakie wartości może to mieć, 2) przejdź po wszystkich tych wartościach pętlą (albo kilkoma pętlami), 3) dla każdej sprawdź warunek z treści.
Kury i krowy
Klasyczna zagadka: na podwórku są kury i krowy, razem 10 głów i 28 nóg. Ile jest kur, a ile krów? Na matematyce ułożyłbyś układ równań. Komputer sprawdzi po prostu każdą możliwą liczbę krów — od 0 do 10:
int glowy, nogi;
cin >> glowy >> nogi;
for (int krowy = 0; krowy <= glowy; krowy++) {
int kury = glowy - krowy;
if (2 * kury + 4 * krowy == nogi) {
cout << "kury: " << kury << ", krowy: " << krowy << "\n";
}
}
| krowy | kury | nogi | = 28? |
|---|---|---|---|
| 0 | 10 | 20 | nie |
| 1 | 9 | 22 | nie |
| 2 | 8 | 24 | nie |
| 3 | 7 | 26 | nie |
| 4 | 6 | 28 | tak! |
| 5…10 | 5…0 | 30…40 | nie |
Zauważ, że nie potrzebujemy drugiej pętli po kurach: gdy znamy liczbę krów, liczba kur wynika z liczby głów. To ważna myśl na całą tę część — jeśli jakąś wartość da się wyliczyć z pozostałych, nie przeszukuj jej osobną pętlą.
Każda cyfra osobno: trzy pętle
Szukamy liczb trzycyfrowych, których suma cyfr wynosi 5. Zamiast rozbierać każdą liczbę od 100 do 999 na cyfry, możemy budować ją z cyfr: trzy pętle — po cyfrze setek, dziesiątek i jedności. Kolejność pętli daje liczby od razu rosnąco:
int s = 5, ile = 0;
for (int a = 1; a <= 9; a++) { // setki (nie 0!)
for (int b = 0; b <= 9; b++) { // dziesiątki
for (int c = 0; c <= 9; c++) { // jedności
if (a + b + c == s) {
cout << 100 * a + 10 * b + c << " ";
ile++;
}
}
}
}
cout << "\nrazem: " << ile << "\n";
Trzy pętle wykonują razem 9 · 10 · 10 = 900 sprawdzeń — po jednym na każdą liczbę trzycyfrową. Cyfra setek startuje od 1, bo liczba trzycyfrowa nie zaczyna się od zera.
I znowu — trzecia pętla nie jest konieczna. Gdy znamy a i b, cyfra c musi wynosić s − a − b; wystarczy sprawdzić, czy to jest cyfra (od 0 do 9). Tu zysk jest niewielki, ale przy większych zadaniach jedna pętla mniej to często różnica między „zdąży” a „nie zdąży”.
Druga wartość wynika z pierwszej
Długopis kosztuje 2 zł, zeszyt 3 zł. Na ile sposobów możesz wydać dokładnie 12 zł? Przeszukiwanie po liczbie długopisów i liczbie zeszytów to dwie pętle. Ale gdy wiadomo, ile długopisów kupiłeś, na zeszyty zostaje konkretna kwota — i albo dzieli się ona przez cenę zeszytu, albo nie:
int a, b, n; // cena długopisu, zeszytu, kwota
cin >> a >> b >> n;
int sposoby = 0;
for (int x = 0; a * x <= n; x++) { // x długopisów
int reszta = n - a * x;
if (reszta % b == 0) {
cout << x << " dlugopisow, " << reszta / b << " zeszytow\n";
sposoby++;
}
}
cout << "sposobow: " << sposoby << "\n";
Warunek pętli a * x <= n mówi: „dopóki starcza pieniędzy na x długopisów”. To naturalna granica przeszukiwania — dalej nie ma sensu szukać.
Ustalanie granic to druga ważna umiejętność. Zawsze zastanów się, jaka jest najmniejsza i największa sensowna wartość, której szukasz. Za wąsko — zgubisz rozwiązania. Za szeroko — program będzie liczył niepotrzebnie długo.
Bez powtórzeń: a ≤ b ≤ c
Ile jest trójkątów o bokach całkowitych i obwodzie 12? Trójkąt o bokach 3, 4, 5 to ten sam trójkąt co 5, 3, 4 — nie chcemy go liczyć sześć razy. Rozwiązanie: szukamy tylko boków ułożonych rosnąco, a ≤ b ≤ c. Pętla po b startuje od a, a trzeci bok wynika z obwodu. Z trzech odcinków da się zbudować trójkąt, gdy dwa krótsze są razem dłuższe od najdłuższego:
int p = 12, ile = 0;
for (int a = 1; a <= p; a++) {
for (int b = a; a + b + b <= p; b++) { // c >= b
int c = p - a - b;
if (a + b > c) {
cout << a << " " << b << " " << c << "\n";
ile++;
}
}
}
cout << "trojkatow: " << ile << "\n";
Warunek wewnętrznej pętli a + b + b <= p to sprytny zapis „c = p − a − b jest co najmniej b”. Dzięki niemu nigdy nie dostaniemy c mniejszego od b, więc każdy trójkąt pojawi się raz, z bokami w kolejności rosnącej.
Na przykład 1, 5, 6 odpada, bo 1 + 5 = 6 nie jest większe od 6 — z takich odcinków wyjdzie płaski „trójkąt”.
Cztery pętle: kody PIN
Pętli może być więcej niż dwie czy trzy. Ile jest czterocyfrowych kodów PIN o sumie cyfr 2, w których żadne dwie sąsiednie cyfry nie są takie same? Cztery pętle przechodzą po wszystkich 10 000 kodach od 0000 do 9999:
int s = 2, ile = 0;
for (int a = 0; a <= 9; a++)
for (int b = 0; b <= 9; b++)
for (int c = 0; c <= 9; c++)
for (int d = 0; d <= 9; d++)
if (a + b + c + d == s && a != b && b != c && c != d) {
cout << a << b << c << d << " ";
ile++;
}
cout << "\nkodow: " << ile << "\n";
Tu klamry przy pętlach pominięto, bo każda pętla zawiera dokładnie jedną instrukcję (następną pętlę). To częsty widok w programach olimpijskich, ale na początek bezpieczniej pisać klamry zawsze.
Kod wypisujemy, wypisując cztery cyfry po kolei — dzięki temu zera z przodu same się pojawiają (0101, a nie 101).
Dlaczego tylko dwa kody? Cyfry o sumie 2 to albo jedna dwójka i trzy zera, albo dwie jedynki i dwa zera. W pierwszym przypadku dwa zera zawsze stoją obok siebie. W drugim pasują tylko układy na przemian: 0101 i 1010.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
int ile = 0;
for (int a = 1; a <= 9; a++)
for (int b = 0; b <= 9; b++)
ile++;
cout << ile;
Pokaż odpowiedź
for (int x = 0; x <= 5; x++) {
int y = 5 - x;
if (x * y == 6) cout << x << y << " ";
}
Pokaż odpowiedź
int n = 10, ile = 0;
for (int a = 1; a <= n; a++)
for (int b = a; b <= n; b++)
if (a * b == 12) ile++;
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (int a = 0; a <= 9; a++)
for (int b = 0; b <= 9; b++)
if (a + b == 9) ile++;
cout << ile;
Pokaż odpowiedź
int a = 7, n = 50, ile = 0;
for (int x = 0; a * x <= n; x++) {
ile++;
}
cout << ile;
Pokaż odpowiedź
for (int a = 1; a <= 20; a++)
for (int b = a; b <= 20; b++)
if (a * a + b * b == 13 * 13)
cout << a << " " << b << "\n";
Pokaż odpowiedź
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ę.
Jak szybka jest pętla — czy program zdąży?
Każde zadanie w sprawdzarce ma limit czasu, zwykle 1 sekundę na test. Na olimpiadzie jest tak samo. Program, który liczy poprawnie, ale za wolno, dostaje zero punktów za dany test — sprawdzarka po prostu przerywa go po upływie limitu. Dlatego przed napisaniem pętli warto oszacować, ile obrotów wykona.
Reguła kciuka, której używają zawodnicy: komputer wykonuje w sekundę około 100 milionów (10⁸) prostych obrotów pętli — takich, w których jest kilka działań i porównań. Bywa szybciej, bywa wolniej, ale jako miara „czy zdąży” sprawdza się świetnie.
| liczba obrotów | czas (orientacyjnie) | czy zdąży w 1 s? |
|---|---|---|
| 10⁶ (milion) | tysięczna część sekundy | bez problemu |
| 10⁷ | setna część sekundy | tak |
| 10⁸ | około sekundy | na granicy |
| 10⁹ (miliard) | kilka – kilkanaście sekund | nie |
| 10¹² (bilion) | kilka godzin | zdecydowanie nie |
Ile obrotów wykonuje pętla?
Liczbę obrotów odczytasz wprost z nagłówków pętli — to umiesz już z części 2. Przy pętlach zagnieżdżonych mnożysz: wewnętrzne ciało wykonuje się tyle razy, ile obrotów robi zewnętrzna, razy ile robi wewnętrzna. Najczęstsze przypadki:
| pętla | obrotów | dla n = 10⁶ |
|---|---|---|
for (i = 1; i <= n; i++) | n | 10⁶ — szybko |
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) | n · n | 10¹² — godziny |
for (i = 1; i <= n; i++) for (j = i + 1; j <= n; j++) | n · (n − 1) / 2 | 5 · 10¹¹ — wciąż godziny |
for (d = 1; d * d <= n; d++) | ok. √n | 1000 — natychmiast |
for (p = 1; p <= n; p *= 2) | ok. log₂ n | 20 — natychmiast |
Liczenie par „bez powtórzeń” (j = i + 1) jest dwa razy szybsze niż wszystkich par, ale dla dużego n to nadal za mało — połowa z biliona to wciąż ogrom. Gdy dane są duże, trzeba zmienić pomysł, a nie tylko szczegóły. Program poniżej liczy obroty pętli par dla małego n i porównuje wynik ze wzorem:
long long n;
cin >> n;
long long ile = 0;
for (long long i = 1; i <= n; i++) {
for (long long j = i + 1; j <= n; j++) {
ile++;
}
}
cout << ile << " = " << n * (n - 1) / 2 << "\n";
Dla n = 1000 pętle wykonują pół miliona obrotów — moment. Dla n = 10⁹ wynik ze wzoru dostaniesz od razu, a pętle liczyłyby go latami. To pierwsza lekcja szybkości: jeśli coś da się policzyć wzorem, nie licz tego pętlą.
Zwróć uwagę na typy: n · (n − 1) dla n = 10⁹ to 10¹⁸ — mieści się w long long, ale nie w int.
Pętla do pierwiastka
Z lekcji o while znasz już test pierwszości, który szuka dzielnika tylko dopóki d * d <= n. Teraz widać, dlaczego to tak ważne: dla n rzędu biliona (10¹²) pętla do n wykonałaby bilion obrotów — kilka godzin. Pętla do pierwiastka wykonuje ich najwyżej milion — tysięczną część sekundy.
long long n;
cin >> n;
bool pierwsza = (n >= 2);
for (long long d = 2; d * d <= n; d++) {
if (n % d == 0) {
pierwsza = false;
break;
}
}
cout << (pierwsza ? "TAK" : "NIE") << "\n";
d * d do biliona — poza zakresem int. Gdyby d było typu int, mnożenie by się przepełniło, warunek dawałby bzdury i pętla mogłaby się nigdy nie skończyć. Licznik, który się mnoży, musi mieć typ, w którym zmieści się iloczyn.
Dzielniki chodzą parami
Ten sam pomysł działa przy szukaniu wszystkich dzielników. Dzielniki liczby n łączą się w pary: jeśli d dzieli n, to n / d też dzieli n. Dla n = 36 to pary (1, 36), (2, 18), (3, 12), (4, 9) i (6, 6). W każdej parze mniejszy dzielnik jest najwyżej pierwiastkiem z n. Wystarczy więc znaleźć „małe” dzielniki — „duże” dostajemy za darmo:
long long n;
cin >> n;
long long ile = 0, suma = 0;
for (long long d = 1; d * d <= n; d++) {
if (n % d == 0) {
ile++;
suma += d;
if (d != n / d) { // para, chyba że d * d == n
ile++;
suma += n / d;
}
}
}
cout << ile << " dzielnikow, suma " << suma << "\n";
Uważaj na kwadraty: dla d = 6 przy n = 36 „para” to ta sama liczba (6 · 6 = 36). Bez warunku d != n / d szóstka zostałaby policzona dwa razy.
A jak wypisać dzielniki po kolei, bez tablic? Dwie pętle: pierwsza idzie w górę do pierwiastka i wypisuje małe dzielniki, druga wraca w dół i wypisuje ich pary, n / d:
long long n;
cin >> n;
long long d = 1;
for (; d * d <= n; d++) {
if (n % d == 0) cout << d << " ";
}
for (d = d - 1; d >= 1; d--) {
if (n % d == 0 && d * d != n) cout << n / d << " ";
}
cout << "\n";
W drugim programie licznik d jest utworzony przed pierwszą pętlą — po niej potrzebujemy jego wartości, żeby wiedzieć, skąd wracać. Start pierwszej pętli jest pusty (for (; …), bo d ma już wartość 1.
Jedna pętla zamiast dwóch
Ostatni, najważniejszy trik. Ile jest par liczb a < b z przedziału od 1 do n, których suma wynosi s? Przeszukiwanie wszystkich par to n · (n − 1) / 2 obrotów — dla n = 10⁷ to 5 · 10¹³, kilka dni liczenia. Ale gdy znamy a, to b nie jest dowolne: musi być równe s − a. Druga pętla jest zbędna — wystarczy sprawdzić jedną wartość:
int n, s;
cin >> n >> s;
long long ile = 0;
for (int a = 1; a <= n; a++) {
for (int b = a + 1; b <= n; b++) {
if (a + b == s) ile++;
}
}
cout << ile << "\n";
int n, s;
cin >> n >> s;
long long ile = 0;
for (int a = 1; a <= n; a++) {
int b = s - a; // b wynika z a
if (a < b && b <= n) ile++;
}
cout << ile << "\n";
Lewy program dla n = 10 milionów nie skończyłby się przed końcem tygodnia. Prawy — w kilka setnych sekundy. Oba są poprawne, ale tylko prawy dostałby punkty. To ten sam pomysł, co w części 7: nie przeszukuj tego, co możesz wyliczyć.
Szacowanie liczby obrotów to początek dużego tematu, który nazywa się złożonością czasową. Wrócisz do niego w osobnej lekcji — na razie wystarczy, że przed wysłaniem rozwiązania zadasz sobie pytanie: „ile obrotów wykona moja pętla dla największych danych z treści?”.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
long long ile = 0;
for (int i = 0; i < 100; i++)
for (int j = 0; j < 100; j++)
for (int k = 0; k < 100; k++)
ile++;
cout << ile;
Pokaż odpowiedź
long long n = 1000000, ile = 0;
for (long long d = 1; d * d <= n; d++) {
ile++;
}
cout << ile;
Pokaż odpowiedź
int ile = 0;
for (long long p = 1; p <= 1000000000; p *= 2) {
ile++;
}
cout << ile;
Pokaż odpowiedź
int n = 100, ile = 0;
for (int d = 1; d * d <= n; d++) {
if (n % d == 0) {
if (d * d == n) ile += 1;
else ile += 2;
}
}
cout << ile;
Pokaż odpowiedź
int n = 10, s = 15, ile = 0;
for (int a = 1; a <= n; a++) {
int b = s - a;
if (a < b && b <= n) ile++;
}
cout << ile;
Pokaż odpowiedź
int n = 5, ile = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
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ń: pętla for w praktyce
Znasz już wszystko, co potrzebne: budowę pętli for, zakresy i liczbę obrotów, wczytywanie danych, break i continue, napisy i for (char c : s), pętle zagnieżdżone, przeszukiwanie wszystkich możliwości i szacowanie szybkości. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jedną pętlą, potem zadania średnie — serie, rysunki z warunkiem, liczenie liter, hetman i zegar — a na końcu trudne, z trójkami pitagorejskimi, hipotezą Goldbacha, kalendarzem i wielkim finałem.
Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak setw, setprecision, long long czy pętla while. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony.
Rozgrzewka · zadania 1–9
Jedna pętla albo prosta pętla w pętli — sumy, alfabet, wykresy, tabela temperatur i silnie.
Średnie · zadania 10–21
Serie, rysunki z warunkiem na wiersz i kolumnę, liczenie liter, kompresja napisu, hetman i zegar.
Trudne · zadania 22–29
Trójki pitagorejskie, palindromy, Goldbach, liczby zaprzyjaźnione, kalendarz — a na końcu wielki finał: wyniki konkursu.