C++ · Podstawy · Lekcja 05

Pętla for w C++

Pętlę while już znasz. Teraz poznasz jej najczęściej używaną siostrę: pętlę for, w której start, warunek i zmiana licznika stoją razem w jednej linijce. Nauczysz się dobierać zakresy i liczyć obroty, wczytywać dane, chodzić po napisach znak po znaku, rysować wzory pętlą w pętli, sprawdzać wszystkie możliwości i oceniać, czy program zdąży policzyć wynik. Po każdej części czekają ćwiczenia ze sprawdzarką.

61 ćwiczeń w trakcie lekcji29 zadań w bazie na koniec90 ze sprawdzarką C++
Filmy z OKI

Wolisz obejrzeć?

Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Ten odcinek omawia dokładnie ten temat.

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

Co już umiesz i czego się nauczysz

Ta lekcja 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.

CZĘŚĆ 01–02

Jak działa for

Budowa i kolejność wykonywania, zakresy, kroki i liczenie obrotów, zasięg licznika.

CZĘŚĆ 03–05

for w zadaniach

Wczytywanie danych, break i continue, kiedy for, a kiedy while, napisy i for (char c : s).

CZĘŚĆ 06–07

Pętla w pętli

Rysunki z wierszy i kolumn, pary liczb i sprawdzanie wszystkich możliwości.

CZĘŚĆ 08

Czy zdąży?

Ile obrotów wykona komputer w sekundę, liczenie obrotów wzorem i pętle do pierwiastka.

Przypomnienie: złota zasada sprawdzarki Sprawdzarka porównuje Twoje wyjście z oczekiwanym znak po znaku, więc wypisujesz dokładnie to, o co prosi zadanie — bez „Podaj liczbę:” i bez dodatkowych słów. Spacje na końcu wiersza są ignorowane, więc cout << 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:

while.cpp
int i = 1;              // start
while (i <= 5) {        // warunek
    cout << i << " ";
    i++;                // zmiana
}
▶ Wyjście
1 2 3 4 5
for.cpp
// start; warunek; zmiana — wszystko w jednym miejscu
for (int i = 1; i <= 5; i++) {
    cout << i << " ";
}
▶ Wyjście
1 2 3 4 5

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

for (int i = 1; i <= 5; i++) { … }
start — raz, na początkuwarunek — przed każdym obrotemzmiana — po każdym obrocie
1️⃣

start

Wykonuje się jeden raz, zanim pętla w ogóle ruszy. Zwykle tworzy licznik: int i = 1.

2️⃣

warunek

Sprawdzany przed każdym obrotem — dokładnie jak w while. Prawdziwy: wykonaj ciało. Fałszywy: koniec pętli.

3️⃣

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.

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

int main() {
    for (int i = 1; i <= 3; i++) {
        cout << "Obrot nr " << i << "\n";
    }
    cout << "Koniec\n";
    return 0;
}
▶ Wyjście
Obrot nr 1 Obrot nr 2 Obrot nr 3 Koniec
start: int i = 1 i <= 3 ? TAK ciało: cout << … zmiana: i++ wróć do warunku NIE za pętlą: "Koniec"
Schemat jest taki sam jak dla while. Różnica jest tylko w zapisie: w for zmiana stoi w nawiasie, ale wykonuje się dopiero po ciele.

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:

Krokco się wykonujewartość iefekt
1int i = 1 (start)1tworzy licznik — tylko raz
2i <= 31true → ciało
3ciało1wypisuje „Obrot nr 1”
4i++ (zmiana)2i rośnie
5i <= 32true → ciało
6ciało2wypisuje „Obrot nr 2”
7i++3i rośnie
8i <= 33true → ciało
9ciało3wypisuje „Obrot nr 3”
10i++4i rośnie
11i <= 34false → koniec pętli
12instrukcja za pętlą—wypisuje „Koniec”
Zapamiętaj kolejność start → warunek → ciało → zmiana → warunek → ciało → zmiana → … → warunek fałszywy → koniec. Start wykonuje się raz. Warunek — o jeden raz więcej niż ciało (ostatnie sprawdzenie kończy pętlę). Zmiana — tyle samo razy co ciało.

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.

co_trzy_while.cpp
int n;
cin >> n;
int i = 2;
while (i <= n) {
    cout << i << " ";
    i += 3;
}
co_trzy_for.cpp
int n;
cin >> n;
for (int i = 2; i <= n; i += 3) {
    cout << i << " ";
}
▶ Wejście
15
▶ Wyjście
2 5 8 11 14

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++).

od_1_do_n.cpp
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
    cout << i << " ";
}
cout << "\n";
▶ Wejście
7
▶ Wyjście
1 2 3 4 5 6 7
n_razy.cpp
int n;
cin >> n;
for (int i = 0; i < n; i++) {
    cout << "Hej! ";
}
cout << "\n";
▶ Wejście
3
▶ Wyjście
Hej! Hej! Hej!

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

odliczanie.cpp
int n;
cin >> n;
for (int i = n; i >= 1; i--) {
    cout << i << "... ";
}
cout << "Start!\n";
▶ Wejście
5
▶ Wyjście
5... 4... 3... 2... 1... Start!
tabela.cpp
for (int i = 1; i <= 5; i++) {
    cout << i << " " << i * i << " " << 2 * i + 1 << "\n";
}
▶ Wyjście
1 1 3 2 4 5 3 9 7 4 16 9 5 25 11

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:

odwrotnosci_zle.cpp
#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;
}
▶ Wyjście
1.0000
odwrotnosci.cpp
#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;
}
▶ Wyjście
2.0833

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
for (int i = 1; i <= 4; i++) {
    cout << i;
}
Pokaż odpowiedź
1234Licznik przyjmuje wartości 1, 2, 3 i 4. Przy 5 warunek jest fałszywy.
Ile razy wypisze się gwiazdka?
for (int i = 0; i < 6; i++) {
    cout << "*";
}
Pokaż odpowiedź
******Sześć razy — dla i = 0, 1, 2, 3, 4, 5. Zapis i = 0; i < n daje dokładnie n obrotów.
Co wypisze ten fragment?
for (int i = 10; i > 0; i -= 3) {
    cout << i << " ";
}
Pokaż odpowiedź
10 7 4 1Po 1 licznik zmienia się na −2, a −2 > 0 to fałsz. Pętla nie trafia w zero, ale warunek > 0 zatrzymuje ją w porę.
Kiedy wykona się zmiana? Co wypisze program?
for (int i = 1; i <= 3; i++) {
    cout << i;
    cout << "-";
}
Pokaż odpowiedź
1-2-3-Całe ciało (obie instrukcje cout) wykonuje się przed i++. Zmiana stoi w nawiasie, ale działa dopiero po ciele.
Suma w pętli for. Co wypisze program?
int s = 0;
for (int i = 2; i <= 8; i += 2) {
    s += i;
}
cout << s;
Pokaż odpowiedź
20Do sumy trafiają 2, 4, 6 i 8 — razem 20.
Co wypisze ten fragment?
for (int i = 5; i <= 3; i++) {
    cout << "X";
}
cout << "koniec";
Pokaż odpowiedź
koniecWarunek 5 <= 3 jest fałszywy już przy pierwszym sprawdzeniu, więc ciało nie wykona się ani razu — tak samo jak w while.

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łówekwartości licznikaobrotów
for (int i = 0; i < n; i++)0, 1, …, n − 1n
for (int i = 1; i <= n; i++)1, 2, …, nn
for (int i = n; i >= 1; i--)n, n − 1, …, 1n
for (int i = n - 1; i >= 0; i--)n − 1, …, 1, 0n
for (int i = a; i <= b; i++)a, a + 1, …, bb − 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.

ile_obrotow.cpp
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";
▶ Wyjście
1 5 9 13 17 obrotow: 5, ze wzoru: 5

(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ż…”.

w_dol.cpp
int a, b;
cin >> a >> b;
for (int i = b; i >= a; i--) {
    cout << i << " ";
}
cout << "\n";
▶ Wejście
-2 3
▶ Wyjście
3 2 1 0 -1 -2
potegi.cpp
for (long long p = 1; p <= 1000000000000LL; p *= 10) {
    cout << p << " ";
}
cout << "\n";
▶ Wyjście
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 10000000000 100000000000 1000000000000
co_k.cpp
int a, b, k;
cin >> a >> b >> k;
for (int i = a; i <= b; i += k) {
    cout << i << " ";
}
cout << "\n";
▶ Wejście
-10 10 4
▶ Wyjście
-10 -6 -2 2 6 10

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:

zasieg_blad.cpp
for (int i = 1; i <= 5; i++) {
    cout << i << " ";
}
cout << i;    // błąd: i już nie istnieje
▶ Kompilator
error: 'i' was not declared in this scope
zasieg_dobrze.cpp
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";
▶ Wyjście
pierwszy kwadrat ponad 50: 64

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ół:

dwa_liczniki.cpp
for (int i = 1, j = 10; i < j; i++, j -= 2) {
    cout << i << " " << j << "\n";
}
▶ Wyjście
1 10 2 8 3 6

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

licznik_w_ciele.cpp
for (int i = 0; i < 10; i++) {
    cout << i << " ";
    i += 2;     // ukryta druga zmiana
}
cout << "\n";
▶ Wyjście
0 3 6 9
licznik_w_naglowku.cpp
for (int i = 0; i < 10; i += 3) {
    cout << i << " ";
}
cout << "\n";
▶ Wyjście
0 3 6 9

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:

wielokrotnosci.cpp
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";
▶ Wejście
10 40 7
▶ Wyjście
14 21 28 35
▶ Wejście
1000000000 4000000000 1000000000
▶ Wyjście
1000000000 2000000000 3000000000 4000000000

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile razy wykona się ciało tej pętli?
int ile = 0;
for (int i = 5; i <= 25; i += 5) {
    ile++;
}
cout << ile;
Pokaż odpowiedź
5Wartości 5, 10, 15, 20 i 25. Ze wzoru: (25 − 5) / 5 + 1 = 5.
Co wypisze ten fragment?
for (int i = 1; i < 100; i *= 3) {
    cout << i << " ";
}
Pokaż odpowiedź
1 3 9 27 81Po 81 licznik zmienia się na 243, a 243 < 100 to fałsz.
Co wypisze ten fragment?
for (int i = 8, j = 0; j < i; i--, j++) {
    cout << i - j << " ";
}
Pokaż odpowiedź
8 6 4 2Pary (8, 0), (7, 1), (6, 2), (5, 3) — różnica maleje o 2. Przy (4, 4) warunek 4 < 4 jest fałszywy.
Ile liczb wypisze pętla?
int ile = 0;
for (int i = -3; i <= 3; i++) {
    ile++;
}
cout << ile;
Pokaż odpowiedź
7Od −3 do 3: 3 − (−3) + 1 = 7 liczb (−3, −2, −1, 0, 1, 2, 3).
Licznik przed pętlą. Co wypisze program?
int i;
for (i = 0; i < 20; i += 6) {
}
cout << i;
Pokaż odpowiedź
24Licznik przyjmuje 0, 6, 12, 18, a potem 24 — i przy 24 pętla się kończy. Po pętli i ma wartość pierwszą, która nie spełniła warunku.
Co wypisze ten fragment?
for (int i = 0; i < 6; i++) {
    cout << i;
    i++;
}
Pokaż odpowiedź
024Licznik rośnie dwa razy w obrocie — raz w ciele, raz w nagłówku. Ciało widzi wartości 0, 2 i 4. Lepiej było napisać i += 2 w nawiasie.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

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

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:

suma_while.cpp
int n;
cin >> n;
long long suma = 0;
int i = 0;
while (i < n) {
    int x;
    cin >> x;
    suma += x;
    i++;
}
cout << suma << "\n";
suma_for.cpp
int n;
cin >> n;
long long suma = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    suma += x;
}
cout << suma << "\n";
▶ Wejście
5 4 -2 10 7 1
▶ Wyjście
20

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:

rekordy_pozycje.cpp
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";
▶ Wejście
7 4 9 1 9 3 1 5
▶ Wyjście
max 9 na miejscu 2 min 1 na miejscu 6

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:

paragon.cpp
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";
▶ Wejście
3 250 4 1999 1 45 10
▶ Wyjście
1000 1999 450 razem: 3449
najlepszy.cpp
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";
▶ Wejście
4 Ala 4 Kuba 5 Ola 5 Igor 3
▶ Wyjście
Kuba (5)

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++):

zmiany_znaku.cpp
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";
▶ Wejście
6 3 -1 -4 2 5 -6
▶ Wyjście
3

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:

saldo.cpp
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";
▶ Wejście
5 100 -250 50 300 -20
▶ Wyjście
180 -150
operacjasaldonajniżej
start00
+1001000
−250−150−150
+50−100−150
+300200−150
−20180−150
Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze program dla podanego wejścia?
int n;
cin >> n;
int ile = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x > 5) ile++;
}
cout << ile;
Wejście: 4 3 7 2 8
Pokaż odpowiedź
2Większe od 5 są 7 i 8.
Na której pozycji zapamięta maksimum?
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;
Wejście: 5 2 6 6 1 6
Pokaż odpowiedź
5Przy >= każda kolejna szóstka nadpisuje pozycję, więc zostaje ostatnia — piąta.
Pary liczb. Co wypisze program?
int n, s = 0;
cin >> n;
for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    s += a * b;
}
cout << s;
Wejście: 3 5 4 2 10 1 1
Pokaż odpowiedź
415 · 4 + 2 · 10 + 1 · 1 = 20 + 20 + 1 = 41.
Co policzy ten program?
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;
Wejście: 5 1 3 2 5 4
Pokaż odpowiedź
2Liczy wzrosty między sąsiadami: (1, 3) i (2, 5). Pary (3, 2) i (5, 4) to spadki.
Najniższe saldo. Co wypisze?
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;
Wejście: 4 10 -30 15 -20
Pokaż odpowiedź
-25Saldo: 10, −20, −5, −25. Najniższe jest ostatnie: −25.
Kto wygra?
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;
Wejście: 3 Ola 3 Ala 6 Ela 6
Pokaż odpowiedź
AlaAla i Ela mają po 6 punktów, ale przy ostrej nierówności rekord zmienia się tylko na większy — zostaje Ala, która była wcześniej.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

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

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:

SytuacjaPętlaPrzykład
wiadomo z góry, ile obrotów albo po jakim zakresie chodzi licznikforn 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ćwhiledane do zera, while (cin >> x), cyfry liczby, Collatz, algorytm Euklidesa
ciało musi wykonać się co najmniej razdo … whilerzut 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:

pierwsza_podzielna.cpp
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";
}
▶ Wejście
20 40 7
▶ Wyjście
21
▶ Wejście
8 9 5
▶ Wyjście
BRAK

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.

continue_for.cpp
for (int i = 1; i <= 12; i++) {
    if (i % 3 == 0) {
        continue;       // i++ wykona się mimo to
    }
    cout << i << " ";
}
cout << "\n";
▶ Wyjście
1 2 4 5 7 8 10 11
tylko_dodatnie.cpp
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";
▶ Wejście
6 4 -2 0 7 -1 3
▶ Wyjście
14 3

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:

do_progu.cpp
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;
    }
}
▶ Wejście
10
▶ Wyjście
5 15
▶ Wejście
1000000
▶ Wyjście
1414 1000405
nastepna_pierwsza.cpp
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
    }
}
▶ Wejście
100
▶ Wyjście
101
▶ Wejście
1000000000
▶ Wyjście
1000000007

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.

Uwaga na pętlę bez końca 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.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
for (int i = 1; i <= 10; i++) {
    if (i * i > 20) {
        break;
    }
    cout << i << " ";
}
Pokaż odpowiedź
1 2 3 4Dla i = 5 kwadrat 25 przekracza 20 i pętla kończy się, zanim 5 zostanie wypisane.
Co wypisze ten fragment?
for (int i = 1; i <= 6; i++) {
    if (i % 2 == 1) continue;
    cout << i;
}
Pokaż odpowiedź
246Nieparzyste są pomijane. Zmiana i++ wykonuje się po continue, więc pętla nie utknie.
Ile obrotów wykona pętla?
int ile = 0;
for (int i = 0; ; i += 7) {
    ile++;
    if (i > 30) break;
}
cout << ile;
Pokaż odpowiedź
6Wartości i: 0, 7, 14, 21, 28, 35. Przy 35 warunek i > 30 jest prawdziwy, ale ile++ stoi przed break — ten obrót też jest policzony.
Warunek z &&. Co wypisze program?
int znalezione = 0;
int i;
for (i = 10; i <= 50 && znalezione == 0; i++) {
    if (i % 13 == 0) znalezione = i;
}
cout << znalezione << " " << i;
Pokaż odpowiedź
13 14Przy i = 13 znajdujemy wielokrotność. Ale uwaga: zanim warunek zatrzyma pętlę, wykona się jeszcze zmiana i++ — stąd 14. Przy break licznik zostałby równy 13.
Co wypisze ten fragment?
for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 3; j++) {
        if (j == 2) break;
        cout << i << j << " ";
    }
}
Pokaż odpowiedź
11 21 31break przerywa tylko wewnętrzną pętlę (przy j = 2). Zewnętrzna działa dalej i dla każdego i wypisuje tylko parę z j = 1.
for z pustym startem i zmianą. Co wypisze?
int n = 1000, k = 0;
for (; n > 1; ) {
    n /= 10;
    k++;
}
cout << k;
Pokaż odpowiedź
3To w praktyce while (n > 1): 1000 → 100 → 10 → 1, trzy obroty.

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:

znaki.cpp
string s;
cin >> s;
for (int i = 0; i < s.length(); i++) {
    cout << i << ": " << s[i] << "\n";
}
▶ Wejście
kot
▶ Wyjście
0: k 1: o 2: t

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.

literuj.cpp
string s;
cin >> s;
for (int i = 0; i < s.length(); i++) {
    if (i > 0) {
        cout << "-";
    }
    cout << s[i];
}
cout << "\n";
▶ Wejście
olimpiada
▶ Wyjście
o-l-i-m-p-i-a-d-a
lista_liczb.cpp
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
    if (i > 1) {
        cout << ", ";
    }
    cout << i * i;
}
cout << "\n";
▶ Wejście
5
▶ Wyjście
1, 4, 9, 16, 25

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.

samogloski.cpp
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";
▶ Wejście
ala ma kota a kot ma ale
▶ Wyjście
10
cyfry_w_tekscie.cpp
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";
▶ Wejście
a1b22c7
▶ Wyjście
12

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.

wielkie_indeks.cpp
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";
▶ Wejście
Ala ma 2 koty!
▶ Wyjście
ALA MA 2 KOTY!
wielkie_ref.cpp
string s;
getline(cin, s);
for (char &c : s) {         // & — pracuj na oryginale
    if (c >= 'a' && c <= 'z') {
        c = c - 'a' + 'A';
    }
}
cout << s << "\n";
▶ Wejście
Ala ma 2 koty!
▶ Wyjście
ALA MA 2 KOTY!

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:

bez_spacji.cpp
string s;
getline(cin, s);
string wynik = "";
for (char c : s) {
    if (c != ' ') {
        wynik += c;
    }
}
cout << wynik << "\n";
▶ Wejście
Ala ma kota
▶ Wyjście
Alamakota
wspak.cpp
string s;
cin >> s;
string w = "";
for (int i = s.length() - 1; i >= 0; i--) {
    w += s[i];
}
cout << w << "\n";
▶ Wejście
programowanie
▶ Wyjście
einawomargorp

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

palindrom.cpp
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";
▶ Wejście
kajak
▶ Wyjście
TAK
▶ Wejście
kotek
▶ Wyjście
NIE
is[i]s[n − 1 − i]równe?
0kktak
1aatak
22 < 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

roznice.cpp
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";
▶ Wejście
kotek kotka
▶ Wyjście
2
zamiana_par.cpp
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";
▶ Wejście
abcdefg
▶ Wyjście
badcfeg

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
string s = "abcdef";
for (int i = 1; i < s.length(); i += 2) {
    cout << s[i];
}
Pokaż odpowiedź
bdfIndeksy 1, 3 i 5 — co drugi znak, zaczynając od drugiego.
Ile razy wykona się ciało pętli?
string s = "Ala ma kota";
int ile = 0;
for (char c : s) {
    ile++;
}
cout << ile;
Pokaż odpowiedź
11Pętla przechodzi po każdym znaku, także po dwóch spacjach — napis ma 11 znaków.
Bez &. Co wypisze program?
string s = "kot";
for (char c : s) {
    c = 'x';
}
cout << s;
Pokaż odpowiedź
kotc jest kopią znaku — zmiana kopii nie zmienia napisu. Z for (char &c : s) wypisałoby się xxx.
Co wypisze ten fragment?
string s = "a1b2c3";
int x = 0;
for (char c : s) {
    if (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
    }
}
cout << x;
Pokaż odpowiedź
123Cyfry 1, 2 i 3 są doklejane do liczby jak przy odwracaniu — wynik to 123.
Co wypisze ten fragment?
string s = "kajak", w = "";
for (int i = 0; i < s.length(); i++) {
    if (s[i] != 'a') w += s[i];
}
cout << w;
Pokaż odpowiedź
kjkDo nowego napisu trafiają wszystkie znaki oprócz a.
Ile par porówna pętla dla słowa długości 7?
string s = "abcdcba";
int n = s.length(), ile = 0;
for (int i = 0; i < n / 2; i++) {
    ile++;
}
cout << ile;
Pokaż odpowiedź
37 / 2 = 3 w dzieleniu całkowitym: pary (0, 6), (1, 5), (2, 4). Środkowy znak nie ma pary i nie trzeba go sprawdzać.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

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

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.

prostokat.cpp
int a = 3, b = 6;
for (int w = 1; w <= a; w++) {         // wiersze
    for (int k = 1; k <= b; k++) {     // kolumny
        cout << "*";
    }
    cout << "\n";
}
▶ Wyjście
****** ****** ******

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.

trojkaty.cpp
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";
}
▶ Wyjście
...* ..** .*** ****
trojkat_liter.cpp
int n = 5;
for (int w = 1; w <= n; w++) {
    for (char c = 'A'; c < 'A' + w; c++) {
        cout << c;
    }
    cout << "\n";
}
▶ Wyjście
A AB ABC ABCD ABCDE

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:

pary.cpp
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";
▶ Wyjście
(1,2) (1,3) (1,4) (2,3) (2,4) (3,4) par: 6

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:

tabliczka.cpp
#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;
}
▶ Wyjście
x | 1 2 3 4 --+---------------- 1 | 1 2 3 4 2 | 2 4 6 8 3 | 3 6 9 12 4 | 4 8 12 16

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

ten_sam_licznik.cpp
int ile = 0;
for (int i = 0; i < 3; i++) {
    for (int i = 0; i < 4; i++) {    // drugie i!
        ile++;
    }
}
cout << ile << "\n";
▶ Wyjście
12

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile razy wypisze się gwiazdka?
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 4; j++) {
        cout << "*";
    }
}
Pokaż odpowiedź
********************5 obrotów zewnętrznej po 4 obroty wewnętrznej — 20 gwiazdek.
Co wypisze ten fragment?
for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= i; j++) {
        cout << j;
    }
    cout << " ";
}
Pokaż odpowiedź
1 12 123W wierszu i wewnętrzna pętla wypisuje liczby od 1 do i.
Co wypisze ten fragment?
for (int i = 1; i <= 3; i++) {
    for (int j = i; j <= 3; j++) {
        cout << j;
    }
    cout << " ";
}
Pokaż odpowiedź
123 23 3Wewnętrzna pętla startuje od i, więc każdy kolejny wiersz zaczyna się o jeden dalej.
Ile par policzy program?
int ile = 0;
for (int i = 1; i <= 5; i++) {
    for (int j = i + 1; j <= 5; j++) {
        ile++;
    }
}
cout << ile;
Pokaż odpowiedź
104 + 3 + 2 + 1 + 0 = 10, czyli 5 · 4 / 2.
Co wypisze ten fragment?
for (char c = 'a'; c <= 'e'; c += 2) {
    cout << c;
}
Pokaż odpowiedź
aceLicznik będący znakiem może skakać o więcej niż 1 — tu co drugą literę.
Co wypisze ten fragment?
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ź
14Warunek i == j spełniają tylko pary (1,1), (2,2), (3,3): 1 + 4 + 9 = 14.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

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

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:

kury_krowy.cpp
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";
    }
}
▶ Wejście
10 28
▶ Wyjście
kury: 6, krowy: 4
krowykurynogi= 28?
01020nie
1922nie
2824nie
3726nie
4628tak!
5…105…030…40nie

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:

suma_cyfr_5.cpp
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";
▶ Wyjście
104 113 122 131 140 203 212 221 230 302 311 320 401 410 500 razem: 15

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:

zakupy.cpp
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";
▶ Wejście
2 3 12
▶ Wyjście
0 dlugopisow, 4 zeszytow 3 dlugopisow, 2 zeszytow 6 dlugopisow, 0 zeszytow sposobow: 3

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:

trojkaty.cpp
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";
▶ Wyjście
2 5 5 3 4 5 4 4 4 trojkatow: 3

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:

piny.cpp
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";
▶ Wyjście
0101 1010 kodow: 2

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.

Jak przeszukiwać mądrze 1) Przeszukuj tylko to, czego nie da się wyliczyć — trzecia wartość często wynika z dwóch pierwszych. 2) Ustal granice: najmniejszą i największą sensowną wartość. 3) Gdy kolejność nie ma znaczenia, wymuś ją (a ≤ b ≤ c), żeby nie liczyć tego samego kilka razy. 4) Policz, ile sprawdzeń wykona program — o tym jest następna część.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile sprawdzeń warunku wykona ten fragment?
int ile = 0;
for (int a = 1; a <= 9; a++)
    for (int b = 0; b <= 9; b++)
        ile++;
cout << ile;
Pokaż odpowiedź
909 wartości a razy 10 wartości b — tyle, ile jest liczb dwucyfrowych.
Co wypisze ten fragment?
for (int x = 0; x <= 5; x++) {
    int y = 5 - x;
    if (x * y == 6) cout << x << y << " ";
}
Pokaż odpowiedź
23 32Szukamy dwóch liczb o sumie 5 i iloczynie 6. Druga liczba wynika z pierwszej, więc wystarczy jedna pętla.
Ile par wypisze program?
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ź
2Pary a ≤ b z iloczynem 12 i obiema liczbami do 10: (2, 6) i (3, 4). Para (1, 12) odpada, bo 12 > 10.
Co wypisze ten fragment?
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ź
10Pary cyfr o sumie 9: (0, 9), (1, 8), …, (9, 0) — dziesięć par.
Ile obrotów wykona pętla?
int a = 7, n = 50, ile = 0;
for (int x = 0; a * x <= n; x++) {
    ile++;
}
cout << ile;
Pokaż odpowiedź
8x przyjmuje wartości od 0 do 7 (7 · 7 = 49 ≤ 50, a 7 · 8 = 56 > 50) — razem 8 obrotów.
Co wypisze ten fragment?
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ź
5 12Jedyna para z a ≤ b, w której a² + b² = 169, to 5 i 12 — boki trójkąta prostokątnego o przeciwprostokątnej 13.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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

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

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ówczas (orientacyjnie)czy zdąży w 1 s?
10⁶ (milion)tysięczna część sekundybez problemu
10⁷setna część sekundytak
10⁸około sekundyna granicy
10⁹ (miliard)kilka – kilkanaście sekundnie
10¹² (bilion)kilka godzinzdecydowanie 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ętlaobrotówdla n = 10⁶
for (i = 1; i <= n; i++)n10⁶ — szybko
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++)n · n10¹² — godziny
for (i = 1; i <= n; i++) for (j = i + 1; j <= n; j++)n · (n − 1) / 25 · 10¹¹ — wciąż godziny
for (d = 1; d * d <= n; d++)ok. √n1000 — natychmiast
for (p = 1; p <= n; p *= 2)ok. log₂ n20 — 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:

licz_obroty.cpp
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";
▶ Wejście
4
▶ Wyjście
6 = 6
▶ Wejście
1000
▶ Wyjście
499500 = 499500

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.

pierwsza_bilion.cpp
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";
▶ Wejście
999999999989
▶ Wyjście
TAK
▶ Wejście
999999999999
▶ Wyjście
NIE
Licznik w long long! Dla n = 10¹² licznik d dochodzi do miliona, a 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:

dzielniki_pary.cpp
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";
▶ Wejście
36
▶ Wyjście
9 dzielnikow, suma 91
▶ Wejście
1000000000000
▶ Wyjście
169 dzielnikow, suma 2499694822171

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:

dzielniki_po_kolei.cpp
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";
▶ Wejście
36
▶ Wyjście
1 2 3 4 6 9 12 18 36

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ść:

pary_wolno.cpp
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";
▶ Wejście
6 7
▶ Wyjście
3
pary_szybko.cpp
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";
▶ Wejście
6 7
▶ Wyjście
3
▶ Wejście
10000000 10000001
▶ Wyjście
5000000

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?”.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Ile razy wykona się instrukcja ile++?
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ź
1000000100 · 100 · 100 = milion. Trzy zagnieżdżone pętle po n obrotów to n³.
Ile obrotów wykona pętla dla n = 10⁶?
long long n = 1000000, ile = 0;
for (long long d = 1; d * d <= n; d++) {
    ile++;
}
cout << ile;
Pokaż odpowiedź
1000d dochodzi do 1000, bo 1000 · 1000 = 10⁶. Pętla do pierwiastka jest tysiąc razy krótsza niż pętla do n.
Ile obrotów wykona pętla?
int ile = 0;
for (long long p = 1; p <= 1000000000; p *= 2) {
    ile++;
}
cout << ile;
Pokaż odpowiedź
302²⁹ ≈ 5,4 · 10⁸ mieści się w miliardzie, a 2³⁰ ≈ 1,07 · 10⁹ już nie. Wartości p to 2⁰, 2¹, …, 2²⁹ — 30 obrotów.
Ile dzielników ma 100? Policz tak, jak robi to program.
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ź
9Małe dzielniki: 1, 2, 4, 5 (po 2 punkty — z parami 100, 50, 25, 20) i 10 (1 punkt, bo 10 · 10 = 100). Razem 4 · 2 + 1 = 9.
Ile par znajdzie szybki program dla n = 10 i s = 15?
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ź
3Pary (5, 10), (6, 9), (7, 8). Dla a od 1 do 4 liczba b przekracza 10, a od 8 w górę nie jest większa od a.
Ile razy wykona się ile++? (n = 5)
int n = 5, ile = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        ile++;
cout << ile;
Pokaż odpowiedź
151 + 2 + 3 + 4 + 5 = 15, czyli n · (n + 1) / 2.
Ćwiczenia · teraz Ty

7 ćwiczeń do tej części

0 / 7 zaliczonych

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

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

Baza zadań: 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.

Jak rozwiązywać zadania z pętlą for 1) Ustal, po czym idzie pętla: po liczbach od a do b, po n danych, po znakach napisu, po wierszach rysunku? To wyznacza nagłówek. 2) Zapisz pierwszą i ostatnią wartość licznika — i sprawdź, czy nie ma błędu o jeden. 3) Przy rysunkach zrób tabelkę: numer wiersza → ile znaków jakiego rodzaju. 4) Przy przeszukiwaniu zastanów się, które wartości trzeba przeszukać, a które da się wyliczyć. 5) Oszacuj liczbę obrotów dla największych danych: do ok. 10⁸ — zdąży. 6) Przetestuj skrajności: n = 1, puste zakresy, największe liczby.
łatwe

Rozgrzewka · zadania 1–9

Jedna pętla albo prosta pętla w pętli — sumy, alfabet, wykresy, tabela temperatur i silnie.

średnie

Średnie · zadania 10–21

Serie, rysunki z warunkiem na wiersz i kolumnę, liczenie liter, kompresja napisu, hetman i zegar.

10 Liczby Nivenaśrednie✓ zaliczone Ile liczb z przedziału dzieli się przez sumę swoich cyfr? Pętla po cyfrach w pętli po liczbach. forsuma cyfr w środkulicznik Rozwiąż 11 Najdłuższy wzrostśrednie✓ zaliczone Najdłuższy fragment ciągu, w którym każda liczba jest większa od poprzedniej. forpoprzednia liczbaseria i rekord Rozwiąż 12 Trójkąt Floydaśrednie✓ zaliczone Kolejne liczby naturalne ułożone w trójkąt: 1 / 2 3 / 4 5 6 / … for w forlicznik poza pętlami Rozwiąż 13 Rombśrednie✓ zaliczone Choinka i odwrócona choinka razem — szerokość wiersza najpierw rośnie, potem maleje. for w fordwie połówkiwzór na szerokość Rozwiąż 14 Litera Xśrednie✓ zaliczone Kwadrat n × n z # na obu przekątnych — warunek na numer wiersza i kolumny. for w forprzekątne|| Rozwiąż 15 Warstwy kwadratuśrednie✓ zaliczone Każde pole to numer warstwy: odległość od najbliższego brzegu plus 1. for w forminimum z czterechwzór na pole Rozwiąż 16 Najczęstsza literaśrednie✓ zaliczone Dla każdej litery od a do z policz, ile razy występuje — i wybierz rekordzistkę. for po literachfor po napisie w środkurekord Rozwiąż 17 Anagramyśrednie✓ zaliczone Czy dwa słowa mają dokładnie te same litery? Porównaj liczbę wystąpień każdej litery. for po literachliczenie w dwóch napisachflaga Rozwiąż 18 Kompresja napisuśrednie✓ zaliczone aaabcc → a3bc2: zamień każdą serię jednakowych liter na literę i długość serii. for po napisieseriabudowanie napisu Rozwiąż 19 Pola atakowane przez hetmanaśrednie✓ zaliczone Hetman bije w pionie, poziomie i po skosach. Ile pól szachownicy n × n atakuje? for w forwarunek na skoswartość bezwzględna Rozwiąż 20 Sumy kolejnych liczbśrednie✓ zaliczone Na ile sposobów n jest sumą co najmniej dwóch kolejnych liczb naturalnych? 15 = 4 + 5 + 6. for w forbreaksuma do progu Rozwiąż 21 Godziny o sumie cyfr sśrednie✓ zaliczone Pętla po godzinach i pętla po minutach: ile razy w ciągu doby suma cyfr zegara wynosi s? for w forcyfrysetw i setfill Rozwiąż
trudne

Trudne · zadania 22–29

Trójki pitagorejskie, palindromy, Goldbach, liczby zaprzyjaźnione, kalendarz — a na końcu wielki finał: wyniki konkursu.

22 Trójki pitagorejskietrudne✓ zaliczone Wszystkie trójkąty prostokątne o bokach całkowitych do n: a² + b² = c². trzy pętle forprzeszukiwaniekolejność wyników Rozwiąż 23 Największy palindromiczny iloczyntrudne✓ zaliczone Sprawdź wszystkie iloczyny x · y z przedziału i znajdź największy palindrom. for w forodwracanie liczbyrekord Rozwiąż 24 Palindromy w systemie dwójkowymtrudne✓ zaliczone Ile liczb z przedziału ma zapis dwójkowy czytany tak samo od tyłu? 9 = 1001₂. forodwracanie w systemie dwójkowym% 2 i / 2 Rozwiąż 25 Hipoteza Goldbachatrudne✓ zaliczone Zapisz liczbę parzystą jako sumę dwóch liczb pierwszych — z najmniejszym pierwszym składnikiem. fortest pierwszości w środkubreaklong long Rozwiąż 26 Liczby zaprzyjaźnionetrudne✓ zaliczone 220 i 284: suma dzielników jednej to druga. Znajdź wszystkie takie pary do n. forsuma dzielników do pierwiastkapara warunków Rozwiąż 27 Ciąg „patrz i mów”trudne✓ zaliczone 1, 11, 21, 1211, 111221… — każdy wyraz opisuje na głos poprzedni. for po napisieseriebudowanie napisupętla w pętli Rozwiąż 28 Kartka z kalendarzatrudne✓ zaliczone Wydrukuj miesiąc jako siatkę tygodni: puste pola na początku, setw(2) i nowy wiersz po niedzieli. forsetwpozycja w tygodniu% Rozwiąż 29 Wielki finał: wyniki konkursutrudne✓ zaliczone Imiona i punkty za k zadań: sumy, najlepsze zadanie każdego, zwycięzca, średnia i statystyki. for w forstringrekordysetprecisionwszystko naraz Rozwiąż

Częste błędy i dobre praktyki

;
Średniki w nawiasie, nie za nim
W nawiasie dokładnie dwa średniki: for (start; warunek; zmiana). Średnik za nawiasem — for (…); — tworzy pustą pętlę, a klamry wykonują się raz.
🔁
Kolejność: ciało, potem zmiana
Zmiana stoi w nawiasie przed ciałem, ale wykonuje się po nim. Start — tylko raz, warunek — przed każdym obrotem.
1️⃣
Błąd o jeden
i = 0; i < n i i = 1; i <= n to n obrotów. Od a do b jest b − a + 1 liczb. Sprawdź pierwszą i ostatnią wartość licznika.
📦
Licznik żyje w pętli
int i z nawiasu znika za pętlą. Jeśli wartość jest potrzebna później, utwórz zmienną przed pętlą: int i; for (i = 1; …).
✋
Nie zmieniaj licznika w ciele
Cała logika licznika w nagłówku. Dodatkowe i++ w ciele sprawia, że nagłówek kłamie, a pętla robi co innego, niż się wydaje.
🔀
Różne liczniki w różnych pętlach
W pętli w pętli używaj innych nazw: i i j albo w i k. Ten sam licznik w obu pętlach to przepis na chaos.
🔤
< przy napisach
Indeksy napisu to 0 … s.length() - 1, więc warunek to i < s.length(). Pętla wstecz — z licznikiem typu int.
&
for (char &c : s)
Bez & pętla „dla każdego” dostaje kopie znaków i zmiany przepadają. Z & zmieniasz oryginalny napis.
⏭️
continue w for jest bezpieczne
W for po continue zmiana z nawiasu wykona się normalnie — w odróżnieniu od while, gdzie i++ na końcu ciała zostałoby pominięte.
🧮
Nie przeszukuj tego, co da się wyliczyć
Jeśli trzecia wartość wynika z dwóch pierwszych (c = p − a − b, b = s − a), nie twórz dla niej pętli. Jedna pętla mniej to często tysiące razy szybciej.
⏱️
Policz obroty
Około 10⁸ prostych obrotów na sekundę. Pętla w pętli dla n = 10⁶ to 10¹² — nie zdąży. Dzielniki i liczby pierwsze — do pierwiastka.
📏
long long w nagłówku
Gdy licznik dochodzi do miliarda albo w warunku jest d * d dla dużych n, licznik musi być long long — inaczej przepełnienie zepsuje warunek.

Co dalej?

Następna lekcja to Modulo: reszta z dzielenia, którą znasz od pierwszej lekcji, przyjrzysz się jej dokładniej — parzystość, ostatnia cyfra i „zawijanie w kółko”, dzięki któremu liczy się dni tygodnia, godziny na zegarze i pozycje w kółeczku. Pętle przydadzą się tam na każdym kroku. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.