Pętla while
Część programistyczna: Pętla while
Dotychczasowe instrukcje (instrukcje warunkowe, przypisania) pozwalały jedynie pisać programy wykonujące kilka kroków. Natomiast pętle pozwolą nam rzeczywiście skorzystać z mocy obliczeniowej komputera, gdyż już na standardowym komputerze miliony instrukcji można wykonywać w ułamku sekundy. W dzisiejszej lekcji opowiemy o pierwszej pętli – pętli while.
Zobacz tekst nagrania
Pętla while w języku C++ wygląda następująco:
while (warunek)
instrukcja;
Jest ona z wyglądu dosyć podobna do instrukcji if. W arunek jest warunkiem logicznym (czyli przyjmującym wartość true lub false), natomiast instrukcja jest pojedynczą instrukcją lub (częściej) instrukcją złożoną, czyli grupą kilku instrukcji umieszczonych w nawiasach klamrowych { }. Pętla while wykonuje kolejne obroty. W każdym obrocie najpierw jest sprawdzany warunek. Jeśli jest on prawdziwy, wykonywana jest instrukcja, a w przeciwnym razie pętla kończy się. Czyli jeśli warunek jest prawdziwy, wykonujemy instrukcję, po czym znów sprawdzamy warunek – jeśli jest spełniony, znów wykonujemy instrukcję i tak dalej – aż do chwili, gdy po wykonaniu instrukcji warunek nie będzie już spełniony.
Warto zwrócić uwagę na dwa szczególne przypadki. Jeśli warunek na starcie jest fałszywy, pętla nie wykonuje ani jednego obrotu (czyli instrukcja nie wykonuje się ani razu). Jeśli zaś warunek jest zawsze prawdziwy, pętla obraca się w nieskończoność (o tym drugim przypadku więcej opowiemy w komentarzu).
Można zatem pętle while odczytać tak: "dopóki jest spełniony warunek, wykonuj instrukcję". Trzeba jednak zawsze pamiętać o krokowym charakterze tej pętli: sprawdzenie warunku - wykonanie instrukcji - sprawdzenie warunku - wykonanie instrukcji - ...
Za pomocą pętli while możemy np. wypisać dowolnie wiele liczb. Na przykład wszystkie liczby od 1 do 10:
#include <iostream>
using namespace std;
int main() {
int i = 1;
while (i <= 10) {
cout << i << endl;
i++;
}
}
Jak działa ta pętla? Zaczynamy od \(i=1\). Sprawdzamy warunek pętli – jest spełniony. A zatem wykonujemy instrukcję złożoną: wypisujemy wartość \(i\), czyli 1, i zwiększamy \(i\) o 1. Teraz \(i=2\). Warunek jest wciąż spełniony, więc wypisujemy liczbę 2 i zmienna \(i\) otrzymuje wartość 3. I tak dalej. Na końcu, gdy \(i=10\), po sprawdzeniu warunku i wykonaniu instrukcji mamy \(i=11\). Warunek nie jest już spełniony, pętla kończy się.
Na tę pętlę można spojrzeć jako na ciąg złożony z wielu przypisań. Zmienna \(i\) zmienia się w każdym obrocie pętli. Jest to tzw. zmienna sterująca pętli, gdyż warunkuje ona liczbę obrotów pętli. Bez problemu napiszemy teraz program, który wypisze wszystkie liczby parzyste z zakresu od 0 do 20 włącznie, od największej do najmniejszej:
#include <iostream>
using namespace std;
int main() {
int i = 20;
while (i >= 0) {
if (i % 2 == 0)
cout << i << endl;
i--;
}
}
Lub nieco sprytniej – tak, aby nie "oglądać" po drodze także liczb nieparzystych:
#include <iostream>
using namespace std;
int main() {
int i = 20;
while (i >= 0) {
cout << i << endl;
i -= 2;
}
}
Pętli while możemy także użyć do wczytania wielu liczb i np. zsumowania ich. Musimy jednak napisać jakiś warunek pętli, który określi nam, jak długo mamy wczytywać liczby. Jedną z metod jest przyjęcie, że wczytujemy liczby aż do napotkania jakiejś szczególnej liczby, oznaczającej koniec wejścia. Np. sumowane liczby będą dodatnie, a na końcu musi wystąpić 0.
Ponieważ (póki co) możemy użyć co najwyżej kilku zmiennych, to widać, że kolejne liczby będziemy musieli wczytywać do tej samej zmiennej.
#include <iostream>
using namespace std;
int main() {
int a;
cin >> a;
int suma = a;
while (a != 0) {
cin >> a;
suma += a;
}
cout << suma << endl;
}
Powyższa pętla while wykonuje się tak długo, aż wczytamy 0. Aby warunek "a != 0" zawsze miał sens, pierwszą liczbę wczytujemy jeszcze przed rozpoczęciem pętli. Oprócz zmiennej \(a\) używamy zmiennej pomocniczej \(suma\) do przechowywania aktualnej sumy liczb.
Zazwyczaj w programach stosuje się wygodniejszy sposób wczytywania wielu liczb: wczytujemy najpierw \(n\), czyli liczbę liczb do wczytania, a potem same te liczby:
#include <iostream>
using namespace std;
int main() {
int i = 1, n;
cin >> n;
int suma = 0;
while (i <= n) {
int a;
cin >> a;
suma += a;
i++;
}
cout << suma << endl;
}
Warto prześledzić po kolei, co dzieje się w tym programie. Tym razem zmienna \(i\) jest zmienną sterującą pętli. Wskazuje ona numer liczby wczytywanej w pętli. Natomiast zmiennych \(a\) i \(suma\) używamy do tego samego co wcześniej.
Zliczanie cyfr liczby
Naszym następnym celem jest napisanie programu, który sprawdza, ile cyfr ma dana liczba naturalna. Poniższy program oblicza najmniejszą potęgę liczby 10, która jest większa od wczytanej liczby \(n\). Przy każdym przemnożeniu zmiennej pot10 przez 10, wartość zmiennej \(liczba\_cyfr\) zwiększa się o 1. Zauważmy, że w poniższym programie pojawia się dosyć rozbudowana deklaracja zmiennych.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int liczba_cyfr = 0, pot10 = 1;
while (pot10 <= n) {
pot10 *= 10;
liczba_cyfr++;
}
cout << liczba_cyfr << endl;
}
Pytanie: czy ten program zadziała poprawnie dla \(n = 0\)?
Powyższy program ma jednak jedną ukrytą wadę. Zauważmy, że nie podawaliśmy ograniczenia na wielkość danych wejściowych, czyli w tym przypadku \(n\) – przyjęliśmy tylko milcząco, że zmieści się ona w typie int. Zastanówmy się, coby się stało, gdyby powyższy program wywołać z parametrem \(n = 2\,000\,000\,000\) (dwa miliardy). Wówczas pętla wykonywałaby się aż do chwili, kiedy pot10 \(> n\), ale takie pot10 powinno być równe \(10\,000\,000\,000\). A ponieważ zakres typu int jest od około minus dwóch miliardów do około dwóch miliardów, to szukane pot10 nie zmieściłoby się w typie, co spowodowałoby nieprzewidziane zachowanie programu (w tym przypadku program nie kończy się).
Istnieje jednak sprytniejsze rozwiązanie, które nie ma wyżej opisanego mankamentu. Zamiast stosować metodę wstępującą ("od dołu do góry", czyli dla coraz większych wartości pot10), zastosujemy metodę zstępującą. Będzie ona polegała na "odcinaniu" kolejnych cyfr liczby \(n\) (poczynając od ostatniej), aż osiągnie ona zero. Przy każdym odcięciu zwiększamy zmienną pomocniczą przechowującą aktualną liczbę cyfr. Odcinanie ostatniej cyfry odpowiada podzieleniu liczby przez 10. Przypomnijmy, że dzielenie liczb całkowitych w C++ odrzuca resztę z dzielenia. Przy okazji w poniższym programie zadbamy o poprawny wynik dla przypadku \(n = 0\).
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int liczba_cyfr = 0;
if (n == 0)
liczba_cyfr = 1;
else
while (n > 0) {
liczba_cyfr++;
n /= 10;
}
cout << liczba_cyfr << endl;
}
Tak naprawdę większość powyższych programów nie stanowiła najlepszych przykładów zastosowania pętli while. W kolejnej lekcji poznamy inny rodzaj pętli, który pozwala wczytywać i wypisywać zadaną liczbę zmiennych w nieco wygodniejszy sposób (pętlę for), a także metodę przechowywania wielu zmiennych naraz (tablice). Ale nie warto robić wszystkiego naraz! Dobre zrozumienie pętli while jest już i tak nie lada wyzwaniem.
Komentarz: Zapętlenie
W roku 1999 otwarto na Powiślu nową siedzibę Biblioteki Uniwersyteckiej. Gmach Biblioteki, zaprojektowany przez architektów Marka Budzyńskiego oraz Zbigniewa Badowskiego, od momentu swego otwarcia jest jedną z największych atrakcji architektonicznych Warszawy. Fasadę budynku zdobi osiem miedzianych tablic, które zawierają cytaty z dzieł reprezentujących różne obszary kulturowe, zapis nutowy oraz wzory matematyczno-fizyczne. Co dla nas jest najbardziej interesujące, jednym z tych "wzorów" jest program komputerowy zapisany w języku programowania Pascal, którego lekko zmodyfikowaną wersję w języku C++ przedstawiamy poniżej:
int main() {
int i;
cin >> i;
while (i != 1)
if (i % 2 == 0)
i = i / 2;
else
i = 3 * i + 1;
cout << "KONIEC" << endl;
}
Uwaga: W tym komentarzu zakładamy, że typ int pozwala przechowywać dowolnie duże liczby całkowite.
Zobacz tekst nagrania
Zdjęcie fasady BUW (fot. Kaja Diks)
Gorąco zachęcam czytelników do poeksperymentowania z tym programem, tzn. uruchomienia go dla różnych dodatnich liczb całkowitych podawanych na wejściu. Szybko się przekonamy, że za każdym razem zostanie wypisane słowo "KONIEC". Jako świadomi algorytmicy/programiści chcielibyśmy wiedzieć, czy tak będzie zawsze. Co właściwie robi ten program? Na początku wczytujemy liczbę całkowitą, a następnie, gdy wczytana liczba jest większa od 1, powtarzamy opisaną poniżej czynność, aż osiągniemy liczbę 1:
- jeśli aktualna wartość i jest parzysta, to za nową wartość i przyjmujemy jej aktualną wartość podzieloną przez 2;
- jeśli natomiast aktualna wartość i jest nieparzysta, to nową wartością i zostaje stara wartość pomnożona przez 3 powiększona o 1.
Prześledźmy kolejne wartości i dla wartości początkowej 3:
3, 10, 5, 16, 8, 4, 2, 1.
Powtarzanie określonej czynności nazywamy w programowaniu iteracją, lub bardziej, przyziemnie pętlą.
W jaki sposób zachowywałby się nasz program, gdybyśmy w instrukcji
i = 3*i + 1;
zgubili 1 i zamienili ją na instrukcję
i = 3*i
Oto jak wyglądałby ciąg kolejnych wartości i dla początkowej wartości równej 3:
3, 9, 27, 81, ...
Jeśli dysponowalibyśmy doskonałym komputerem, który potrafiłby liczyć na dowolnie wielkich liczbach całkowitych, to wykonywanie naszej pętli nigdy by się nie skończyło, a zmienna i przyjmowałaby coraz większe wartości równe kolejnym potęgom liczby 3. Innymi słowy, nasz program działałby w nieskończoność. Takie zjawisko nazywamy zapętleniem się programu. Jest ono bardzo niepożądane i zazwyczaj świadczy o źle zaprojektowanym algorytmie (programie). Unikanie zapętlenia jest jest jedną z najtrudniejszych rzeczy przy projektowaniu algorytmów i pisaniu programów.
Dlaczego przedstawiony przez nas program znalazł się na fasadzie Biblioteki Uniwersyteckiej? Jest to przede wszystkim uznanie dla informatyki, jako dziedziny nauki równoprawnej z innymi dziedzinami. Sam program skrywa w sobie nierozwiązaną od lat zagadkę – czy jego wykonanie zawsze się kończy, niezależnie od tego, jaka będzie początkowa wartość zmiennej i. Zakładamy oczywiście, że komputer, na którym wykonujemy obliczenia, może operować na dowolnie dużych liczbach. Zagadka ta jest powszechnie znana pod nazwą problemu Collatza. Według portalu MathWorld, dla każdej początkowej wartości \(i \le 19 \cdot 2^{58} \approx 5.48 \cdot 10^{18}\), nasz program kończy swoje działanie, czyli osiąga zawsze wartość 1. Czy tak jest jednak zawsze? Może Ty znajdziesz odpowiedź na to pytanie!
Część techniczna: Błędne odpowiedzi cz. 2
W części technicznej kontynuujemy temat radzenia sobie z błędnymi odpowiedziami naszych programów. Tym razem założymy, że wiemy, dla jakich danych wejściowych program nie działa, i musimy zlokalizować usterkę w programie. Warto w tym celu przeczytać uważnie program, wiersz po wierszu - może w ten sposób uda się wykryć błąd. Czasem jednak to nie pomaga. Możemy wtedy próbować znaleźć usterkę, wypisując dodatkowe informacje w trakcie działania programu.
Zobacz tekst nagrania
Jako przykład rozważymy nasz wcześniejszy program służący do zliczania cyfr liczby z drobnym błędem:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int liczba_cyfr;
if (n == 0)
liczba_cyfr = 1;
else
while (n > 0) {
liczba_cyfr++;
n /= 10;
}
cout << liczba_cyfr << endl;
}
Gdy uruchomiliśmy ten program i podaliśmy na wejściu liczbę 1234, uzyskaliśmy wynik:
1999525998
który niewątpliwie nie ma zbyt wiele wspólnego z oczekiwanym wynikiem 3. Ewidentnie coś jest bardzo nie tak.
Aby spróbować znaleźć błąd, spróbujmy wypisać wartości zmiennych \(n\) oraz \(liczba\_cyfr\) w kolejnych obrotach pętli:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int liczba_cyfr;
if (n == 0)
liczba_cyfr = 1;
else
while (n > 0) {
liczba_cyfr++;
n /= 10;
cout << n << " " << liczba_cyfr << endl;
}
cout << liczba_cyfr << endl;
}
Wyjście tego programu (dla liczby 1234) wskazuje, że z pętlą while najwyraźniej wszystko jest w porządku, ale coś nie gra ze zmienną \(liczba\_cyfr\).
123 1999525995
12 1999525996
1 1999525997
0 1999525998
1999525998
Aby rozjaśnić jeszcze sytuację, możemy dodać takie samo wypisanie także przed pętlą while:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int liczba_cyfr;
if (n == 0)
liczba_cyfr = 1;
else {
cout << n << " " << liczba_cyfr << endl;
while (n > 0) {
liczba_cyfr++;
n /= 10;
cout << n << " " << liczba_cyfr << endl;
}
}
cout << liczba_cyfr << endl;
}
Oto wynik działania tego programu:
1234 1999525994
123 1999525995
12 1999525996
1 1999525997
0 1999525998
1999525998
Przed pętlą while nic się z tą zmienną nie dzieje. Wiemy już, czego nie zrobiliśmy - nie przypisaliśmy zmiennej \(liczba\_cyfr\) początkowej wartości 0. Zmienna, której nie przypisaliśmy żadnej wartości i której wartości nie wczytaliśmy od użytkownika, może mieć w programie zupełnie dowolną wartość (w zakresie typu zmiennej). Co więcej, wartość ta może być różna, gdy uruchamiamy program na różnych komputerach, a nawet przy kolejnych uruchomieniach programu na tym samym komputerze! Czasem można mieć nawet takie "szczęście", że program zadziała poprawnie na naszym komputerze (gdyż zmienna będzie miała akurat wartość 0), ale wysłany np. do serwisu Szkopuł będzie działał błędnie. Jest to dość często popełniany błąd, nazywany popularnie niezainicjowaniem lub niewyzerowaniem zmiennej.
I jeszcze druga błędna wersja naszego programu:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int liczba_cyfr = 0;
if (n == 0)
liczba_cyfr = 1;
else
while (n >= 0) {
liczba_cyfr++;
n /= 10;
}
cout << liczba_cyfr << endl;
}
Gdy uruchomimy nasz program dla liczby 1234, wygląda na to, że działa w nieskończoność. Nie bardzo wiadomo, co jest nie tak. Dodajmy wypisywanie:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int liczba_cyfr = 0;
if (n == 0)
liczba_cyfr = 1;
else
while (n >= 0) {
liczba_cyfr++;
n /= 10;
cout << n << " " << liczba_cyfr << endl;
}
cout << liczba_cyfr << endl;
}
Wynikiem programu jest "ściana" liczb wyglądających mniej więcej tak:
......
0 3507
0 3508
0 3509
0 3510
0 3511
0 3512
......
Najwyraźniej w programie od pewnego momentu zachodzi \(n=0\), a tylko zwiększa się \(liczba\_cyfr\). Tym razem wszystkiemu winny jest warunek w pętli while:
while (n >= 0) {
Dla \(n=0\) pętla wykonuje się, ale instrukcja:
n /= 10;
nie zmienia wartości \(n\), więc pętla działa w nieskończoność. Jest to właśnie przykład błędu zapętlenia (o takich błędach była mowa w komentarzu do lekcji).
W obu przypadkach proste wypisywanie pozwoliło nam szybko wykryć usterkę. Jest to jedna z najczęściej stosowanych metod usuwania usterek z programów. Oprócz prostoty, jej zaletą jest to, że może być stosowana tam, gdzie z różnych powodów inne metody nie mogą być używane.
Zadania
Oto trzy kolejne zadania do samodzielnego rozwiązania.