Pętla for i tablice
Część programistyczna: Pętla for i tablice
Prosta pętla for
Wiemy już, że pętle pozwalają nam wielokrotnie wykonywać takie same lub podobne czynności. Jednym z najprostszych przypadków jest sytuacja, gdy chcemy powtórzyć daną czynność i wiemy dokładnie, ile razy chcemy to zrobić. Można do tego celu użyć poznanej już pętli while. Jednak lepiej nadaje się do tego pętla for. W tym nagraniu objaśniamy działanie tej pętli wyjątkowo dokładnie.
Zobacz tekst nagrania
W najprostszej postaci pętla for w języku C++ wygląda tak:
for (int i = początek; i <= koniec; i++)
instrukcja;
W pętli deklarujemy zmienną całkowitą, którą nazwaliśmy \(i\). Jest ona zmienną sterującą pętli. Zmienna ta przemierza kolejno wszystkie wartości od początek do koniec (gdzie początek i koniec może być liczbą, zmienną lub ogólnie wyrażeniem arytmetycznym). Dla każdej z tych wartości po kolei wykonywana jest instrukcja wewnątrz pętli. Podobnie jak poprzednio, może to być albo pojedyncza instrukcja, albo instrukcja złożona umieszczona w nawiasach klamrowych.
W poprzedniej lekcji napisaliśmy program, który wypisywał kolejno liczby od 1 do 10. Za pomocą pętli for możemy go napisać krócej:
#include <iostream>
using namespace std;
int main() {
for (int i = 1; i <= 10; i++)
cout << i << endl;
}
I jeszcze jeden przykład – program wczytujący liczbę całkowitą \(n\) i wyznaczający \(n\)-tą liczbę trójkątną, czyli sumę liczb od 1 do \(n\). Używamy w nim zmiennej pomocniczej \(suma\).
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int suma = 0;
for (int i = 1; i <= n; i++)
suma += i;
cout << suma << endl;
}
Pętla w powyższym programie zastępuje więc serię instrukcji postaci:
suma += 1;
suma += 2;
...
suma += n;
Opowiedzmy jeszcze trochę o innych wariantach pętli for. Pętla ta składa się z trzech części, rozdzielonych średnikami. W pierwszej podajemy początkową wartość zmiennej sterującej. W trzeciej znajduje się krok pętli, czyli informacja, jak ma się zmieniać wartość zmiennej sterującej. Zazwyczaj ma ona każdorazowo wzrastać lub maleć o 1 lub o jakąś większą wartość. Druga część wreszcie zawiera warunek logiczny, którego niespełnienie powoduje zakończenie pętli. Warunek ten sprawdzamy na początku – jeśli od początku nie jest spełniony, pętla nie wykona się ani razu – jak i po każdym wykonaniu kroku pętli. Zmienną sterującą pętli zwyczajowo nazwaliśmy \(i\), ale ogólnie dobór nazwy tej zmiennej może być dowolny.
Przykładowo, gdybyśmy chcieli wypisać wszystkie liczby parzyste od 20 do 0, jak w poprzedniej lekcji, za pomocą pętli for napisalibyśmy tak:
for (int i = 20; i >= 0; i -= 2)
cout << i << endl;
Tablice
Tablice pozwalają przechowywać wiele danych naraz. Świetnie współgrają z pętlą for.
Zobacz tekst nagrania
W poprzedniej lekcji napisaliśmy program, który najpierw wczytuje liczbę \(n\), następnie \(n\) liczb całkowitych, po czym wypisuje sumę tych \(n\) liczb. Zróbmy to samo, tylko z użyciem pętli for:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int suma = 0;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
suma += a;
}
cout << suma << endl;
}
W ten sposób każdą z \(n\) liczb na wejściu wczytaliśmy do tej samej zmiennej \(a\). Teraz opowiemy o innej konstrukcji programistycznej, który pozwoli przechowywać wszystkie wczytane liczby naraz. Są to tablice.
Tablicę liczb całkowitych deklarujemy w języku C++ tak:
int tablica[dlugosc];
W ten sposób zadeklarowaliśmy tablicę o nazwie tablica, która składa się z elementów będących liczbami całkowitymi. Liczbę tych elementów określa długość ( rozmiar) tablicy.
Nazwy tablic możemy dobierać dowolnie, tak jak nazwy zmiennych. Długość tablicy jest najczęściej jedną liczbą, pojedynczą zmienną (odpowiadającą np. długości ciągu liczb) albo prostym wyrażeniem arytmetycznym. Przykładowo:
int t[n];
to tablica o nazwie \(t\) zawierająca \(n\) elementów.
Elementy takiej tablicy to: \(t[0],t[1],\ldots,t[n-1]\). Widzimy, że numerujemy je począwszy od zera. Każdy z elementów odpowiada osobnemu miejscu w pamięci komputera, w którym jest zapamiętana jedna liczba – jest to to samo, co \(n\) zmiennych całkowitych naraz!
Przepiszemy nasz poprzedni program z użyciem tablicy. Ponieważ elementy tablicy numerujemy od zera, więc zmienna sterująca \(i\) będzie tym razem przyjmować wartości \(0,1,\ldots,n-1\):
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int t[n];
int suma = 0;
for (int i = 0; i < n; i++) {
cin >> t[i];
suma += t[i];
}
cout << suma << endl;
}
W tym przykładzie nie było żadnej potrzeby, żeby przechowywać wczytane liczby w tablicy. Dzięki niej możemy jednak najpierw wczytać wszystkie dane, a dopiero potem wykonać żądane obliczenia – a tak się po prostu łatwiej myśli. Możemy też obliczyć coś jeszcze dla tych samych danych, np. minimum w tablicy:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int t[n];
int suma = 0;
for (int i = 0; i < n; i++)
cin >> t[i];
int suma = 0;
for (int i = 0; i < n; i++)
suma += t[i];
cout << suma << endl;
int min = t[0];
for (int i = 1; i < n; i++)
if (t[i] < min)
min = t[i];
cout << min << endl;
}
Inny przykład to program, w którym wczytujemy ciąg liczb o długości \(n\) i chcemy go wypisać od ostatniej liczby do pierwszej. Tego zadania nie da się już rozwiązać bez użycia tablic:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int t[n];
for (int i = 0; i < n; i++)
cin >> t[i];
for (int i = n - 1; i >= 0; i--)
cout << t[i] << " ";
cout << endl;
}
Dodatek: Ogólna pętla for
Jak dotychczas używaliśmy tylko konkretnego, dosyć prostego schematu pętli for. Teraz opiszemy wygląd pętli for w pełnej ogólności. Pozwoli nam to dokładniej zrozumieć, jak działa ta pętla.
for (instrukcja_początkowa; warunek_stopu; krok_pętli)
instrukcja;
Mamy tu trzy zasadnicze części:
- Instrukcja początkowa to instrukcja, która zostaje wykonana na samym początku pętli, niezależnie od wszystkiego. Zazwyczaj jest to instrukcja przypisania, która może wystąpić wraz z deklaracją zmiennej (zmiennych) albo bez, jeśli zmienna (zmienne) są zadeklarowane przed pętlą.
- Warunek stopu to dowolny warunek logiczny (czyli taki jak w instrukcjach
iforazwhile). Niespełnienie tego warunku przed wykonaniem danego obrotu pętli powoduje zakończenie pętli. - Wreszcie krok pętli to instrukcja, która jest wykonywana po każdym obrocie pętli. Często jest ona używana do zmiany wartości zmiennej (zmiennych) sterujących pętli.
A zatem pętla for działa w następującym cyklu:
instrukcja_początkowa;
sprawdź warunek_stopu - jeśli fałszywy, to koniec
instrukcja;
krok_pętli;
sprawdź warunek_stopu - jeśli fałszywy, to koniec
instrukcja;
krok_pętli;
...
Koniec następuje wtedy, gdy warunek stopu przed kolejnym obrotem pętli staje fałszywy. Jeśli to nigdy nie nastąpi, ma miejsce zapętlenie. Dodajmy jeszcze, że każda z części pętli może być pusta (wtedy po prostu nic tam nie piszemy).
Uwaga: Używając tylko pętli while, można napisać ciąg instrukcji równoważny ogólnej pętli for. (Czy potrafisz to zrobić?) Tak więc często taki sam kod można wyrazić albo za pomocą ogólnej pętli for, albo za pomocą pętli while. Programista ma wtedy zupełną dowolność, której metody użyć. Ot, jak mu będzie wygodniej!
Oto przykład zastosowania ogólnej pętli for do zadania o zliczaniu cyfr z poprzedniej lekcji. Według nas wygląda zdecydowanie mniej czytelnie niż z użyciem pętli while.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int liczba_cyfr = 0;
if (n == 0)
liczba_cyfr = 1;
else
for (; n > 0; n /= 10)
liczba_cyfr++;
cout << liczba_cyfr << endl;
}
W tej lekcji wyjątkowo nie umieszczamy komentarza. Kolejna opowieść profesora Krzysztofa Diksa o programowaniu pojawi się już za tydzień!
Część techniczna: Błędy wykonania i błędne odpowiedzi cz. 3
Część techniczną rozpoczniemy dosyć nietypowo. Wprowadzimy ciąg liczb, który pojawia się nierzadko w matematyce, informatyce, lecz także w biologii, muzyce, a nawet w analizie rynków finansowych. Jest to ciąg liczb Fibonacciego. Pierwsze wyrazy tego ciągu wyglądają tak:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Pierwsze dwie liczby Fibonacciego to 0 i 1. Każda kolejna liczba jest sumą dwóch poprzednich. \(n\)-tą liczbę Fibonacciego oznacza się zazwyczaj jako \(F_n\) lub \(Fib_n\).
Zainteresowanych Czytelników zachęcamy do poszukania w sieci więcej informacji o liczbach Fibonacciego. My tymczasem spróbujemy napisać program, który wyznaczy 50-tą liczbę Fibonacciego (zakładamy, że zerowa liczba Fibonacciego to 0).
Zobacz tekst nagrania
Skorzystajmy z tablicy, w której będziemy przechowywać kolejne liczby Fibonacciego. Piszemy i uruchamiamy poniższy program:
#include <iostream>
using namespace std;
int main()
{
int fib[50];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= 50; i++)
fib[i] = fib[i - 1] + fib[i - 2];
cout << fib[50] << endl;
}
Niestety w wyniku działania programu nie otrzymujemy żadnej liczby, a tylko komunikat, że program skończył się z błędem. Jest to tzw. błąd wykonania. Pierwszy przykład błędu wykonania mieliśmy już w lekcji drugiej, gdy w programie wykonującym dzielenie wprowadziliśmy dzielnik równy 0. W tym programie jest inna usterka, która powoduje ten błąd. Otóż wychodzimy indeksem poza tablicę. Rzeczywiście, tablica \(fib\) składa się z elementów \(fib[0],\ldots,fib[49]\), a my zarówno w pętli dla \(i=50\), jak i w ostatniej instrukcji korzystamy z pola \(fib[50]\).
Wyjście indeksem poza tablicę (czy też w stronę ujemnych indeksów, czy też ponad rozmiar) jest częstą i zarazem kłopotliwą usterką. Może powodować niezdefiniowane działanie programu: błąd wykonania, błędną odpowiedź, a czasem nawet, jeśli nam się poszczęści, wynik programu jest poprawny. Jest to ponadto niedeterministyczne: program może działać inaczej na jednym komputerze, a inaczej na innym. Dlatego wielu programistów, zwłaszcza w programach pisanych na szybko, wpisuje zawsze rozmiar tablicy o kilka elementów większy niż rozmiar ściśle wymagany – właśnie na wypadek własnego przeoczenia. W naszym przypadku wystarczy wpisać rozmiar 51:
#include <iostream>
using namespace std;
int main()
{
int fib[51];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= 50; i++)
fib[i] = fib[i - 1] + fib[i - 2];
cout << fib[50] << endl;
}
Gdy uruchomimy ten poprawiony program, otrzymujemy w wyniku liczbę:
-298632863
Jest to wynik ewidentnie błędny, gdyż wszystkie liczby Fibonacciego są nieujemne. Co tym razem poszło nie tak? W poprzedniej lekcji, mierząc się z podobnym problemem, wykorzystaliśmy dodatkowe wypisywania. Zróbmy tak samo teraz:
#include <iostream>
using namespace std;
int main()
{
int fib[51];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= 50; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
cout << i << " " << fib[i] << endl;
}
cout << fib[50] << endl;
}
Wyniki programu do pewnego momentu wyglądają rozsądnie, ale gdzieś między 40-tym a 50-tym elementem zaczynają pojawiać się liczby ujemne:
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
...
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170
46 1836311903
47 -1323752223
48 512559680
49 -811192543
50 -298632863
-298632863
Zauważmy, że 46-ta liczba Fibonacciego jest równa prawie \(2 \cdot 10^9\), czyli ledwie mieści się w zakresie typu int. Kolejne liczby po prostu wychodzą już poza zakres, co objawia się ujemnymi (oraz bezsensownymi dodatnimi) wartościami. W tym przypadku wystarczy zmienić typ elementów tablicy na jakiś 64-bitowy, np. long long:
#include <iostream>
using namespace std;
int main()
{
long long fib[51];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= 50; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
cout << i << " " << fib[i] << endl;
}
cout << fib[50] << endl;
}
Dzięki temu już wiemy, jaka jest 50-ta liczba Fibonacciego:
...
40 102334155
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170
46 1836311903
47 2971215073
48 4807526976
49 7778742049
50 12586269025
12586269025
Błąd przekroczenia zakresu zmiennej jest kolejnym typowym błędem popełnianym przez programistów. W tym przypadku wystąpił on dlatego, że liczby Fibonacciego naprawdę szybko rosną. Jeśli nasz program nie działa, dobrze jest sprawdzić kod pod kątem tego typu błędów – zwłaszcza jeśli w programie wykonujemy np. wiele mnożeń.
Na koniec dwa pytania do przemyślenia:
- Czy umiałbyś wyznaczyć pięćdziesiątą liczbę Fibonacciego bez użycia tablicy?
- Jaką największą liczbę Fibonacciego można wyznaczyć, używając typu
long long? A jaką z użyciem typuunsigned long long?