Więcej o pętlach i tablicach
Część programistyczna
W dzisiejszej części programistycznej wprowadzimy raczej niewiele nowych elementów języka programowania. Skoncentrujemy się raczej na tym, jak wykorzystać znane nam elementy do pisania coraz ciekawszych programów. Zwieńczeniem części programistycznej będzie napisanie programu, który szuka wystąpień zadanego słowa w tekście.
Typ logiczny bool
Zobacz tekst nagrania
Wczytujemy do tablicy ciąg \(n\) liczb całkowitych. Chcemy sprawdzić, czy ciąg ten jest rosnący, czyli czy każda kolejna liczba jest ściśle większa od poprzedniej.
Aby rozwiązać to zadanie, wprowadzimy zmienną pomocniczą, w której będziemy pamiętać, czy już rozważony fragment ciągu jest rosnący, czy nie. Zmienna ta będzie typu logicznego bool. Typ ten przyjmuje tylko dwie wartości – true i false, czyli prawdę i fałsz.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int t[n];
for (int i = 0; i < n; i++)
cin >> t[i];
bool rosnacy = true;
for (int i = 1; i < n; i++)
if (t[i - 1] >= t[i])
rosnacy = false;
if (rosnacy == true)
cout << "TAK" << endl;
else
cout << "NIE" << endl;
}
Pytanie: Czy ten program zadziała poprawnie dla ciągu jednoelementowego?
Tak naprawdę wielokrotnie już używaliśmy typu bool, tylko sami o tym nie wiedzieliśmy. Otóż każde wyrażenie logiczne w instrukcji if lub while jest albo prawdziwe, albo fałszywe, więc jest typu bool. Tym bardziej więc zmienną typu bool możemy umieścić w warunku np. instrukcji if, czyli zamiast
if (rosnacy == true)
napiszemy po prostu:
if (rosnacy)
Możemy też pójść o krok dalej i wyeliminować z pętli instrukcję if! Ggdy aktualizujemy zmienną rosnący, korzystamy tu z operacji logicznej "oraz", czyli &&. Otrzymujemy następujący, elegancki program:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int t[n];
for (int i = 0; i < n; i++)
cin >> t[i];
bool rosnacy = true;
for (int i = 1; i < n; i++)
rosnacy = rosnacy && (t[i - 1] < t[i]);
if (rosnacy)
cout << "TAK" << endl;
else
cout << "NIE" << endl;
}
Zagnieżdżanie pętli
Zobacz tekst nagrania
Wiemy, że w pętli może występować instrukcja złożona, czyli instrukcja zawierająca dowolnie wiele innych instrukcji. Nic nie stoi na przeszkodzie, aby jedną z tych instrukcji była... kolejna pętla! W takiej sytuacji mówimy, że mamy do czynienia z dwiema zagnieżdżonymi pętlami.
Żeby zobaczyć, jak to działa, napiszmy prosty program, który wypisze tabliczkę mnożenia – czyli wyniki mnożenia dowolnej pary cyfr dziesiętnych. Użyjemy tu dwóch pętli z dwiema zmiennymi sterującymi, \(i\) oraz \(j\).
#include <iostream>
using namespace std;
int main() {
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++)
cout << i * j << " ";
cout << endl;
}
}
Widzimy, że zewnętrzna pętla for ma jakby większą "ważność" od wewnętrznej, tj. rzadziej wykonuje obroty. Najpierw \(i=1\), wówczas wewnętrzna pętla przemierza kolejne \(j=1,\ldots,9\). Później \(i=2\) i znów \(j\) przemierza kolejne wartości od 1 do 9, itd. Sam program działa poprawnie, ale niestety wynik wygląda brzydko.
1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81
Możemy poprawić sposób wypisywania wyniku. Wystarczy przed każdą liczbą jednocyfrową wypisać spację:
#include <iostream>
using namespace std;
int main() {
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
int k = i * j;
if (k < 10)
cout << " ";
cout << k << " ";
}
cout << endl;
}
}
Teraz już jest ładniej. Wynik tego programu może pomóc w nauce naszym młodszym kolegom ze szkoły podstawowej.
1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81
Tablice znaków, czyli napisy
Zobacz tekst nagrania
W poprzedniej lekcji wprowadziliśmy tablice zawierające liczby całkowite. Ich elementami były liczby typu int lub long long. Teraz zobaczymy, co się stanie, gdy elementami tablicy będą elementy typu char, o których wiemy, że mogą być interpretowane zarówno jako znaki kodu ASCII, jak i jako niewielkie liczby całkowite. W takim przypadku w tablicy znajduje się pewien ciąg znaków, czyli po prostu napis. I znów okazuje się, że z tablicami znaków mieliśmy już wcześniej do czynienia, nawet o tym nie wiedząc. Otóż wszystkie komunikaty, które nasz program kiedykolwiek wypisywał (te umieszczone w cudzysłowach "..."), były takimi właśnie napisami!
char t[n];
Takie tablice znaków nie są niestety zbytnio wygodne w użyciu. Dlatego zamiast nich w tej lekcji będziemy używać czegoś bardzo podobnego, ale nieco przyjemniejszego. Będzie to typ string.
Elementy typu string to tablice znaków, których długość nie musi być ustalona. Jeśli chcemy ich używać w programie, musimy dopisać na początku programu specjalny wiersz #include <string>. Aby dowiedzieć się, jaką długość ma dany napis, używamy operacji size(). Napisy typu string możemy wczytywać i wypisywać tak samo jak liczby. Oto prosty przykład.
#include <iostream>
#include <string>
using namespace std;
int main() {
string napis = "Pierwszy program";
cout << napis.size() << endl;
cout << napis << endl;
}
Jeszcze jeden przykład: napiszemy program, który wczytuje pewną liczbę nazwisk i wypisuje te z nich, które mają dokładnie 8 liter i zaczynają się na "K". Zwróćmy uwagę na to, że gdy chodzi nam o napis typu string, umieszczamy go zawsze w cudzysłowach "...", natomiast gdy chodzi nam o pojedynczy znak typu char (np. jako pojedynczą składową zmiennej typu string), umieszczamy go w apostrofach 'x'.
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
string nazwisko;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> nazwisko;
if (nazwisko.size() == 8 && nazwisko[0] == 'K')
cout << nazwisko << endl;
}
}
Napis, podobnie jak liczba, jest wczytywany aż do napotkania pierwszej spacji lub końca wiersza. Dla danych:
5
Kowalski Nowak Kopernik Sobieski Kochanowski
wynikiem powyższego programu jest więc:
Kowalski
Kopernik
Wyszukiwanie wzorca w tekście
Problem wyszukiwania wzorca w tekście pojawia się w informatyce bardzo często. Możemy szukać wystąpienia jakiegoś słowa lub fragmentu słowa w dokumencie czy na danej stronie internetowej. Możemy też poszukiwać jakiegoś słowa czy frazy w wiadomościach e-mail lub w całej sieci Internet, za pomocą wyszukiwarki (tu jednak mamy do czynienia z bardziej złożonym problemem, gdyż poszukujemy wzorca w wielu tekstach naraz i dodatkowo dopuszczamy, że różne słowa wzorca występują w różnych miejscach tekstu). My przyjmiemy, że wzorzec i tekst są ciągami znaków i poszukujemy wszystkich fragmentów tekstu, które są takie jak wzorzec. Napiszemy teraz najprostszy program rozwiązujący to zadanie.
Zobacz tekst nagrania
Zarówno wzorzec, jak i tekst będą napisami typu string. W rozwiązaniu rozważymy każdą pozycję \(i\), w której możemy przyłożyć wzorzec do tekstu, i za pomocą drugiej, wewnętrznej pętli for sprawdzimy, czy rzeczywiście wzorzec tam pasuje. Nie możemy przeglądać wszystkich \(i\) od 0 do \(n-1\), gdyż np. dla \(i = n-1\), przy przeglądaniu kolejnych pozycji wzorca, w tekście możemy wyjść poza tablicę. Dlatego ostatnią pozycją, jaką będziemy chcieli rozważyć, jest \(i=n-m\). Wtedy dla kolejnych pozycji wzorca sprawdzimy pozycje tekstu od \(n-m\) do \(n-1\).
Do sprawdzenia, czy na danej pozycji mamy wystąpienie, użyjemy zmiennej logicznej typu bool. Mamy już komplet narzędzi do napisania tego programu:
#include <iostream>
#include <cstring>
using namespace std;
int main() {
string wzorzec, tekst;
cin >> wzorzec >> tekst;
int m = wzorzec.size(), n = tekst.size();
for (int i = 0; i <= n - m; i++) {
bool pasuje = true;
for (int j = 0; j < m; j++)
if (wzorzec[j] != tekst[i + j])
pasuje = false;
if (pasuje)
cout << i << endl;
}
}
Na koniec kilka pytań do uczestników kursu:
- Jak myślisz, jak zadziałałby program, gdybyśmy w zewnętrznej pętli for rozważali \(i\) od 0 do \(n-1\)? Sprawdź to!
- Jak napisać wewnętrzną pętlę bez użycia instrukcji warunkowej
if? - Jak zmienić powyższy program, by wypisywał tylko TAK lub NIE w zależności od tego, czy w tekście jest choć jedno wystąpienie wzorca?
- Jak zmienić powyższy program, by dodatkowo zliczał wszystkie wystąpienia wzorca w tekście?
Komentarz: Sortowanie
Dzisiaj poznamy bardzo prosty algorytm sortowania znany pod nazwą Sortowania przez wybór. Naszym celem będzie uporządkowanie niemalejąco tablicy \(a[0..n-1]\) zawierającej \(n\) liczb całkowitych. Innymi słowy, będziemy chcieli rozwiązać następujące zadanie algorytmiczne:
Sortowanie
Dane
dodatnia liczba całkowita \(n\)
tablica \(n\) liczb całkowitych \(a[0..n-1]\)
Wynik
tablica \(a\) z tą samą zawartością, ale uporządkowana niemalejąco, czyli \(a[0] \le a[1] \le\ldots\le a[n-1]\).
Przykład
Dla \(n = 5\), \(a = [3,1,5,4,3]\), wynikiem będzie \(a = [1,3,3,4,5]\).
Zobacz tekst nagrania
Co to znaczy sortować? W informatyce sortowanie oznacza porządkowanie według ustalonych reguł. Na przykład uczniów w klasie można uporządkować według wzrostu od najwyższego do najniższego. Słowa w słownikach są uporządkowane leksykograficznie. Najpierw są słowa zaczynające się na literę a, potem na literę b, itd. Słownik jest przykładem dobrze ilustrującym po co warto sortować. Gdyby słowa w słowniku były rozrzucone dowolnie, bardzo trudno by nam było odnaleźć interesujące nas słowo. Ogólnie dużo łatwiej zapanować nad uporządkowaną strukturą niż nad chaosem. Dlatego sortowanie jest jedną z podstawowych operacji wykonywanych przez komputery. Niektórzy twierdzą, że komputery ponad 25% czasu spędzają na porządkowaniu danych.
Sortowanie przez wybór jest koncepcyjnie bardzo proste. Polega ono na wyznaczaniu kolejnych elementów uporządkowanego ciągu od największego do najmniejszego. Najpierw znajdujemy element największy i jego aktualną pozycję w całej tablicy \(a\). Następnie zamieniamy element największy z tym z pozycji \(n-1\). W tym momencie element największy jest już na swojej docelowej pozycji \(n-1\). Teraz znajdujemy element największy z pozycji od 0 do \(n-2\), a następnie zamieniamy go z tym z pozycji \(n-2\). Dwa największe elementy są już na swoich pozycjach. Postępujemy tak dalej, aż do momentu, gdy pozostanie nam ustalić kolejność dwóch elementów na pozycjach 0 i 1.
Oto fragment programu odpowiadający przedstawionemu algorytmowi. Mamy w nim dwie zagnieżdżone pętle for. Pętla zewnętrzna wskazuje kolejne pozycje \(i=n-1,\ldots,1\), na których chcemy umieścić kolejne elementy posortowanego ciągu: największy, drugi największy itd. Pętla wewnętrzna, której zakres zależy od zmiennej sterującej \(i\) zewnętrznej pętli, odpowiada znalezieniu maksimum w początkowym fragmencie tablicy, które to maksimum ma się właśnie znaleźć na pozycji \(i\). Zauważmy, że pętla ta wyznacza zarówno wartość, jak i indeks tego maksimum w tablicy, co jest później przydatne przy zamianie miejscami tego elementu oraz elementu \(i\)-tego tablicy.
for (i = n - 1; i > 0; i--) {
// wiemy, że elementy a[i+1], a[i+2], ..., a[n-1] są największe w tablicy i są
// już uporządkowane: a[i+1] <= a[i+1] <= ... <= a[n-1] oraz że dla każdego k = 0, 1, ..., i,
// a[k] <= a[i+1]
// wyznaczamy element największy w podtablicy a[0..i]
m = 0;
maks = a[0];
for (j = 1; j <= i; j++)
// maks == a[m] jest największym elementem spośród a[0], a[1], ..., a[j-1]
if (a[j] > maks) {
m = j;
maks = a[m];
}
//zamieniamy element a[i] z elementem największym
a[m] = a[i];
a[i] = maks;
}
Zapisaliśmy w ten sposób algorytm sortowania przez wybór (elementu największego). Nie jest to bardzo szybki algorytm sortowania. Dla dużego \(n\), powiedzmy rzędu \(100\,000\), będzie on działał zauważalnie wolno. Dlaczego? Zauważmy, że najczęściej wykonywaną operacją w algorytmie jest sprawdzanie warunku
if (a[j] > maks)
Ile razy ten warunek jest sprawdzany? W każdym kroku wewnętrznej pętli for ten warunek jest sprawdzany \(i\) razy. Ponieważ w algorytmie sortowania \(i\) przyjmuje kolejno wartości: \(n-1, n-2, \ldots, 1\), więc w tym algorytmie warunek ten jest sprawdzany \(n-1 + n-2 + \ldots + 1 = n(n-1)/2\) razy. Dla \(n = 10\,000\) algorytm wykona zatem mniej więcej \(5\,000\,000\,000\) takich sprawdzeń. Jeśli moglibyśmy wykonać \(100\,000\,000\) sprawdzeń na sekundę, to algorytm działałby prawie minutę, a przecież wykonywane są w nim jeszcze inne operacje. A co gdy za \(n\) weźmiemy \(1\,000\,000\)?
Z powodu swojego czasu działania algorytm sortowania przez wybór nie jest wykorzystywany w praktyce dla dużych danych. Za sprawą algorytmików udało się jednak znaleźć szybsze algorytmy, niewiele bardziej skomplikowane od właśnie przedstawionego. To już jednak opowieść na inną okazję.
Część techniczna: Odpluskwianie, czyli błędne odpowiedzi cz. 4
Odpluskwianie (z ang. debuggowanie) polega na wykonywaniu programu krok po kroku w celu znalezienia w nim usterek (tj. pluskiew, bugów). W tej części technicznej pokażemy, jak działa odpluskwianie w środowisku Code Blocks, na przykładzie poprawnego programu wyszukiwania wzorca w tekście oraz błędnych programów z części technicznej w poprzedniej lekcji.
Zobacz tekst nagrania
Aby móc korzystać z odpluskwiania, musisz stworzyć nowy projekt. W tym celu kliknij: Plik, Nowy, Projekt... Dalej wybierz Console Application i postępuj zgodnie z instrukcjami. Główny wybór polega na wpisaniu nazwy projektu i umiejscowienia folderu projektu na dysku. Następnie w menu z lewej ( Management) wybierz opcję Projekty, tam znajdź główny plik projektu i tam umieść swój program.
Podstawowe operacje wykonywania krokowego (wszystkie w menu Odpluskwianie):
- Wejdź do (Shift-F7) – rozpoczyna wykonywanie krokowe.
- Wykonaj wiersz (F7) – wykonuje wszystkie instrukcje zawarte w bieżącym wierszu.
- Okna odpluskwiacza, Obserwatorzy – pokazuje bieżące wartości zmiennych w programie. Można je zwijać, rozwijać, przesuwać.
- Przerwij odpluskwianie (Shift-F8).
- Uruchom / Wznów (F8) – zamienia wykonywanie krokowe na zwykłe; przerywa w przypadku natrafienia na jakieś zatrzymanie, np. na błąd wykonania albo koniec działania programu.
- Wykonaj do kursora (F4) – kontynuuje wykonywanie niekrokowo aż dotrze do położenia kursora w programie.
Odpluskwianie przez wykonywanie krokowe jest ciekawą alternatywą do usuwania usterek przez wypisywanie (już teraz możemy powiedzieć: debuggowania przez wypisywanie). Jednak odradzamy jej nadużywanie, gdyż spowalnia ono pracę programisty. Często, aby znaleźć usterkę, wystarczy poświęcić chwilę na przeczytanie niedziałającego programu ze zrozumieniem (choć wiadomo, wymaga to pewnego skupienia i wysiłku umysłowego), a zamiast tego kusi, aby pójść na łatwiznę i pół godziny wykonywać program krokowo, co wymaga mniej myślenia.