Podstawy programowania – Laboratorium 4

Czego powinieneś nauczyć się na tych zajęciach?

• nazywać stan potrzebny do wykonania iteracji,
• przewidywać wartości zmiennych krok po kroku,
• dobierać while albo for do problemu,
• stosować skrócone przypisania oraz rozróżniać ++i i i++,
• stosować licznik, akumulator i bieżące ekstremum,
• rozpoznawać warunek zakończenia oraz ryzyko pętli nieskończonej,
• wykorzystywać zagnieżdżone pętle i szacować liczbę powtórzeń.

Pytanie prowadzące: „Jaki stan muszę pamiętać i jak zmienia się on po jednej iteracji?”. To pytanie jest ważniejsze niż pamięciowe odtwarzanie składni pętli.

---

Każda pętla ma początek, warunek i zmianę

Aby pętla miała sens, przed jej uruchomieniem musi istnieć stan początkowy. Przed kolejną iteracją sprawdzany jest warunek. W ciele pętli wykonujemy pracę oraz zmieniamy stan tak, aby zbliżać się do zakończenia.

1. Ustal stan początkowy.
2. Sprawdź warunek kontynuacji.
3. Wykonaj pracę dla jednej iteracji.
4. Zmień stan i wróć do warunku.

1. Wykonaj ślad pętli

Przed uruchomieniem przygotuj tabelę z kolumnami: numer iteracji, value przed dodaniem i sum po dodaniu. Następnie przewidź końcowy wynik programu.

Program do analizy

#include <stdio.h>

int main(void) {
    int value = 3;
    int sum = 0;

    while (value > 0) {
        sum = sum + value;
        value = value - 1;
    }

    printf("%d %d\n", value, sum);
    return 0;
}

Iteracja	value przed	sum po
1	3	3
2	2	5
3	1	6

Po trzeciej iteracji value przyjmuje 0, więc warunek staje się fałszywy. Program wypisuje 0 6.

---

Pętla while: powtarzaj, dopóki warunek jest prawdziwy

Pętla while najpierw sprawdza warunek. Jeżeli od początku jest on fałszywy, ciało nie wykona się ani razu. Tę konstrukcję wybieramy szczególnie wtedy, gdy liczba iteracji wynika z danych i nie jest z góry znana.

Pętla nieskończona najczęściej powstaje dlatego, że ciało nie zmienia żadnej wartości wpływającej na warunek albo zmienia ją w niewłaściwym kierunku. Zawsze wskaż, dlaczego pętla zbliża się do końca.

---

Zmiana stanu: +=, ++ i --

Licznik często zmieniamy o jeden. Najbardziej jawny zapis i = i + 1 dobrze pokazuje znaczenie operacji: odczytaj dotychczasową wartość i, dodaj jeden i przypisz wynik z powrotem do i. W C tę samą zmianę można zapisać krócej.

Jeżeli każdy z tych zapisów stanowi osobną instrukcję, końcowy efekt jest taki sam: wartość i rośnie o jeden. Operator += jest przykładem przypisania złożonego. Analogicznie możemy zapisać sum += value, number -= 2, product *= factor albo number /= 10.

Zapis	Znaczenie
++i	zwiększ i i jako wartość wyrażenia wykorzystaj nową wartość
i++	jako wartość wyrażenia wykorzystaj starą wartość i, a następnie zwiększ i
--i	zmniejsz i i jako wartość wyrażenia wykorzystaj nową wartość
i--	jako wartość wyrażenia wykorzystaj starą wartość i, a następnie zmniejsz i

Prefiks i postfiks w praktyce

Różnicę między zapisem prefiksowym i postfiksowym widać dopiero wtedy, gdy korzystamy z wartości całego wyrażenia. Przed każdym z dwóch doświadczeń przywracamy i = 5.

#include <stdio.h>

int main(void) {
    int i = 5;

    int post_value = i++;
    printf("i++: wynik = %d, i = %d\n", post_value, i);

    i = 5;
    int pre_value = ++i;
    printf("++i: wynik = %d, i = %d\n", pre_value, i);

    return 0;
}

W kroku pętli for wartość całego wyrażenia jest pomijana. Dlatego dla licznika typu int zapisy i++ i ++i mają tam ten sam efekt i nie ma między nimi praktycznej różnicy wydajności. W przykładach będziemy konsekwentnie używać popularnego zapisu i++.

Nie modyfikuj tej samej zmiennej kilka razy w jednym wyrażeniu. Zapisy takie jak int result = i++ + ++i; albo printf("%d %d", i++, i++); prowadzą w C do niezdefiniowanego zachowania. Na tym etapie stosuj ++ i -- jako samodzielne instrukcje albo w części aktualizującej pętli for.

Pętla for: gdy kontrolujemy licznik

W nagłówku for zapisujemy trzy części: inicjalizację, warunek kontynuacji i zmianę po każdej iteracji. Zapis for (int i = 0; i < limit; i++) oznacza: rozpocznij od zera, wykonuj iteracje dla wartości mniejszych od granicy i po każdej iteracji zwiększ licznik o jeden.

2. Zakres od 0 do x - 1

Wczytaj dodatnie x i wypisz liczby 0, 1, ..., x - 1. Przed uruchomieniem przewidź, ile liczb zostanie wypisanych dla x = 1 oraz x = 5.

Rozwiązanie

#include <stdio.h>

int main(void) {
    int limit;
    scanf("%d", &limit);

    for (int i = 0; i < limit; i++) {
        printf("%d ", i);
    }
    printf("\n");

    return 0;
}

Warunek i < limit tworzy przedział domknięty z lewej i otwarty z prawej strony: [0, limit). Dla dodatniego limit liczba iteracji jest równa dokładnie limit.

---

Typowe role zmiennych w pętli

Rola	Co pamięta?	Typowa inicjalizacja
licznik	ile elementów przetworzono albo który element przetwarzamy	0 lub 1
akumulator	sumę dotychczasowych wartości	0
iloczyn	iloczyn dotychczasowych wartości	1
ekstremum	największą lub najmniejszą dotychczasową wartość	pierwszy element danych
flaga	czy wykryto określoną własność	0 albo 1

3. Suma liczb od 1 do n

Wczytaj dodatnie n i oblicz sumę kolejnych liczb od 1 do n. Po zakończeniu każdej iteracji zmienna sum ma przechowywać sumę liczb od 1 do aktualnego i.

Rozwiązanie

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }

    printf("%lld\n", sum);
    return 0;
}

Zdanie opisujące znaczenie sum po każdej iteracji jest prostym niezmiennikiem pętli. Pomaga zarówno stworzyć algorytm, jak i wyjaśnić, dlaczego wynik jest poprawny.

4. Maksimum ze strumienia liczb

Wczytaj dodatnie n, a potem n liczb całkowitych. Wypisz największą. Nie zakładaj, że dane są dodatnie. Dlaczego inicjalizacja maksimum wartością 0 byłaby błędna?

Rozwiązanie

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);

    int maximum;
    scanf("%d", &maximum);

    for (int i = 1; i < n; i++) {
        int value;
        scanf("%d", &value);

        if (value > maximum) {
            maximum = value;
        }
    }

    printf("maksimum: %d\n", maximum);
    return 0;
}

Pierwszy element staje się początkowym maksimum, więc stan od początku reprezentuje prawdziwy element wejścia. Pozostała pętla zaczyna się od i = 1, bo jeden element już został wczytany.

---

Gdy nie znamy liczby danych: wartownik

Wartownik to specjalna wartość oznaczająca koniec danych. Nie należy ona do przetwarzanej sekwencji. Schemat jest prosty: wczytaj pierwszą wartość, sprawdź ją, przetwórz i wczytaj następną.

5. Suma do napotkania zera

Wczytuj liczby rzeczywiste i dodawaj je do sumy, dopóki użytkownik nie poda 0. Zero kończy wejście i nie zmienia sumy. Program musi poprawnie obsłużyć także sytuację, w której pierwszą wartością jest zero.

Rozwiązanie

#include <stdio.h>

int main(void) {
    double sum = 0.0;
    double value;
    scanf("%lf", &value);

    while (value != 0.0) {
        sum += value;
        scanf("%lf", &value);
    }

    printf("suma: %.6f\n", sum);
    return 0;
}

W tym podstawowym zadaniu zakładamy poprawne dane wejściowe. W laboratorium 5 wrócimy do bardziej ogólnego zakończenia wejścia i wykorzystamy wartość zwracaną przez scanf.

---

Przetwarzanie cyfr liczby

Dla nieujemnej liczby całkowitej ostatnią cyfrę otrzymujemy przez number % 10, a usuwamy ją przez number / 10. Każda iteracja skraca zapis dziesiętny o jedną cyfrę. Szczególnej uwagi wymaga liczba 0, która ma jedną cyfrę, choć typowa pętla dzielenia nie wykonałaby się ani razu.

6. Liczba cyfr

Wczytaj nieujemną liczbę typu unsigned int i podaj liczbę jej cyfr dziesiętnych. Rozwiązanie rozpoczyna licznik od jednego, dzięki czemu poprawnie obsługuje zero.

Rozwiązanie

#include <stdio.h>

int main(void) {
    unsigned int number;
    scanf("%u", &number);

    int digits = 1;
    while (number >= 10) {
        number /= 10;
        digits++;
    }

    printf("liczba cyfr: %d\n", digits);
    return 0;
}

7. Test pierwszości

Wczytaj liczbę całkowitą nie większą niż milion i sprawdź, czy jest pierwsza. Liczby mniejsze od 2 nie są pierwsze. Nie trzeba sprawdzać dzielników większych niż pierwiastek z liczby.

Rozwiązanie

#include <stdio.h>

int main(void) {
    int number;
    scanf("%d", &number);

    int is_prime = number >= 2;

    for (int divisor = 2; divisor * divisor <= number; divisor++) {
        if (number % divisor == 0) {
            is_prime = 0;
        }
    }

    if (is_prime) {
        printf("liczba pierwsza\n");
    } else {
        printf("liczba nie jest pierwsza\n");
    }

    return 0;
}

Jeżeli liczba złożona ma dzielnik większy od pierwiastka, drugi czynnik jest mniejszy od pierwiastka i zostałby już sprawdzony. Warunek divisor * divisor <= number ogranicza więc liczbę prób. Na tym etapie ważniejsza od formalnej analizy jest umiejętność wyjaśnienia, dlaczego nie badamy wszystkich wartości aż do number - 1.

---

Zagnieżdżone pętle: iteracja dla każdej iteracji

Jeżeli pętla wewnętrzna znajduje się w zewnętrznej, wykonuje się od początku dla każdej wartości licznika zewnętrznego. Gdy obie wykonują po n iteracji, ciało wewnętrzne wykonuje się około n · n razy.

8. Tabliczka mnożenia n × n

Wczytaj n z przedziału 1–10 i wypisz kwadratową tabliczkę mnożenia. Licznik zewnętrzny oznacza wiersz, a wewnętrzny – kolumnę.

Rozwiązanie

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);

    for (int row = 1; row <= n; row++) {
        for (int column = 1; column <= n; column++) {
            printf("%4d", row * column);
        }
        printf("\n");
    }

    return 0;
}

Dla n = 3 wyrażenie row * column zostanie obliczone dziewięć razy. Instrukcja wypisująca koniec wiersza należy do pętli zewnętrznej, ale znajduje się już poza pętlą wewnętrzną.

---

Debugger i błąd „o jeden”

Błąd off-by-one oznacza, że pętla wykonała się o jedną iterację za dużo lub za mało. Najczęściej wynika z pomylenia < z <=, startu od niewłaściwej wartości albo błędnego momentu aktualizacji licznika.

Audyt granicy pętli

Specyfikacja mówi: „wypisz dokładnie n liczb od 0 do n - 1„. Kod poniżej kompiluje się, ale łamie specyfikację. Ustaw punkt zatrzymania na instrukcji printf, obserwuj i dla n = 3 i popraw tylko jeden znak.

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);

    for (int i = 0; i <= n; i++) {
        printf("%d ", i);
    }
    printf("\n");

    return 0;
}

Diagnoza: warunek i <= n dopuszcza także wartość n, więc ciało wykonuje się n + 1 razy. Poprawny warunek to i < n.