POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA STRUKTURALNEGO
(ZAP - zima 2013)
Język programowania: C/C++
Środowisko programistyczne: Qt Creator
Wykład 2 : Pętle typu while i pętla for.
Program wykładu
2
Temat 1: Podstawowe pojęcia i proste programy.
Pojęcia algorytmu, programu, kodu wykonywalnego.
Kompilacja i wykonanie programu. Sieci działań. Struktura
programu. Komentarze i dokumentacja programu.
Zmienne i ich nazwy, podstawowe typy: całkowite,
rzeczywiste, znakowe i napisowe. Definicje zmiennych.
Instrukcje: czytania, pisania, przypisania. Klasyfikacja
typów. Stałe, wyrażenia i funkcje standardowe. Instrukcje:
warunkowa, złożona. Instrukcje cykliczne: pętla for, pętle
sterowane warunkiem. Instrukcje przerywające wykonanie
pętli. Instrukcja wielokrotnego wyboru.
Temat 2: Tablice, rekordy i pliki. Tablice: definiowanie tablic, zmienna tablicowa i
indeksowana. Operacje na tablicach. Algorytmy sortowania i przeszukiwania w tablicach,
porównanie złożoności obliczeniowej. Struktury i rekordy, operacje wykonywane na rekordach.
Definiowanie plików, zasady dostępu, operacje wejścia  wyjścia.
Temat 3: Funkcje i rekurencja. Zasady definiowania i
wywołania funkcji. Parametry formalne i aktualne.
Wiązanie parametrów przez wartość i referencję. Zasięg
nazw, zasłanianie. Rekurencja jako jedna z podstawowych
technik konstruowania algorytmów. Zasada działania
rekurencji i warunek końca. Przykłady algorytmów
rekurencyjnych.
Program wykładu (c.d.)
3
Temat 4: Wskaz
niki i listy. Zmienne dynamiczne i wskaz
niki. Przydział i zwalnianie
pamięci. Dynamiczna rezerwacja tablic. Listy jednokierunkowe: zasada tworzenia, podstawowe
operacje na listach. Listy dwukierunkowe i cykliczne. Iteracyjne i rekurencyjne algorytmy
przetwarzania list.
Temat 5: Struktury drzewiaste. Drzewa binarne i binarne drzewa sortowane (BST).
Podstawowe operacje na drzewach z wykorzystaniem rekurencji. Drzewa wyważone (AVL i
RBT). Kopce, B-drzewa, zastosowania do baz danych. Złożoność obliczeniowa.
Temat 6: Przegląd algorytmów, algorytmy grafowe. Przegląd zasad konstruowania
algorytmów: programowanie typu  dziel i zwyciężaj , programowanie dynamiczne, algorytmy z
powrotami, metody zachłanne. Grafy i algorytmy grafowe: przeszukiwanie grafu, problem
najkrótszej ścieżki, minimalne drzewa rozpinające grafów.
Temat 7: Przygotowanie do egzaminu. Przykłady zadań egzaminacyjnych z
rozwiązaniami. Przegląd najczęściej popełnianych błędów, wskazówki, jak ich unikać.
Literatura uzupełniająca
4
1. P. Wnuk, B. Putz: Informatyka 2 - Programowanie. Wersja w języku C/C++.
Multimedialny podręcznik internetowy, OKNO PW, 2004-2010, dostępny online w
SKS: http://iair.mchtr.pw.edu.pl/studenci/witryna/login.php
2. B. Putz, A. Putz jr, P. Wnuk : Algorytmy i struktury danych. Multimedialny podręcznik
internetowy, OKNO PW, 2006-2010, dostępny online w SKS.
3. S. Prata: Język C++. Wydanie V, Helion 2006.
4. J. Grębosz: Symfonia C++ standard. Tom I. Edition 2000 Kraków, 2005-2008.
4. B. Eckel: Thinking in C++. Edycja polska. Helion 2002.
6. N. Wirth: Algorytmy+struktury danych=programy. WNT 2004.
7. P. Wróblewski: Algorytmy, struktury danych i techniki programowania. Wyd. IV, Helion
2010.
8. T.H. Cormen et al.: Wprowadzenie do algorytmów. WNT 2007, PWN 2012 (nowe
wydanie).
5
Operatory inkrementacji i dekrementacji
Operatory ++ (inkrementacji) i -- (dekrementacji)
pozwalają na krótsze zapisywanie instrukcji przypisania.
Zamiast:
Zamiast:
a = a+1;
a = a-1;
można napisać:
można napisać:
a++ ;
a-- ;
lub
lub
++a;
--a;
czyli: zwiększ a o 1
czyli: zmniejsz a o 1
Zalety:
" zwięzły zapis
" od razu pokazuje, że instrukcja przypisania dotyczy tylko
jednej zmiennej
6
Dodatkowe operatory przypisania
Operatory stojące przed znakiem przypisania
pozwalają na krótszy zapis instrukcji przypisania.
Zamiast:
Zamiast:
a = a+b;
a = a*b;
można napisać:
można napisać:
a += b ;
a *= b ;
czyli: zwiększ a o b
czyli: pomnóż a przez b
Zestawienie:
operator przykład znaczenie
+= a += b a = a + b
-= a -= b a = a - b
*= a *= b a = a * b
/= a /= b a = a / b
%= a %= b a = a % b
7
Wyrażenia w notacji przyrostkowej i przedrostkowej
a++ notacja przyrostkowa (post-inkrementacja)
To są wyrażenia, a nie
instrukcje (brak średnika)
++a notacja przedrostkowa (pre-inkrementacja)
" wartością wyrażenia a++ jest wartość zmiennej a przed dodaniem 1
" wartością wyrażenia ++a jest wartość zmiennej a po dodaniu 1.
Te różnice są widoczne tylko wtedy, gdy użyjemy wyrażeń a++
lub ++a w jakichś innych wyrażeniach lub instrukcjach, np. :
b = a++; // wstaw a do b, a potem zwiększ a o 1
// czyli: b stanie się równe wartości a przed dodaniem 1
b = ++a; /* zwiększ a o 1, a potem wstaw a do b
czyli: b stanie się równe wartości a po dodaniu 1
przy okazji: to przykład komentarza zawartego w kilku
wierszach */
Można nawet napisać tak (!):
b=2*a++-3; // pod b podstaw 2*a-3, a potem zwiększ a o 1
(ale lepiej po kolei: b=2*a-3; a++;)
8
Instrukcje iteracyjne (pętle): wprowadzenie
" Umożliwiają wielokrotne powtórzenie ciągu instrukcji
" Wymagają uzupełnienia o instrukcje organizujące samą pętlę
Suma trzech Suma 100 wczytanych Suma zależna od ilości
wczytanych wartości wartości powtórzeń w pętli
.......... .......... .........
int x1, x2, x3; int x, s=0; int x, s=0;
cin >>x1>>x2>>x3; cin>>x; POCZ
TEK P
TLI
int s=x1+x2+x3; s=s+x; //s+=x; cin>>x;
& & & cin>>x; s=s+x;
s=s+x; //s+=x; KONIEC P
TLI
cin>>x; ..........
s=s+x; //s+=x; 100 POWTÓRZEC
- suma
100 wartości
// i co dalej& & & & ? !
9
Rodzaje instrukcji cyklicznych (iteracyjnych)
" Pętla o znanej liczbie cykli (iteracji):
" pętla for
" Pętle o nie znanej z góry liczbie cykli:
" pętla while
tzw. pętle sterowane warunkiem
" pętla do-while
10
Instrukcja while
Instrukcja  Dopóki spełniony warunek, wykonuj
Sprawdza warunek przed wykonaniem instrukcji objętej jej zakresem.
zalecany styl
while (warunek)
instrukcja
" Dopóki spełniony jest warunek, powtarzaj instrukcja,
czyli:
" sprawdz
warunek
" jeśli spełniony, wykonaj instrukcja
" sprawdz
warunek
" jeśli spełniony, wykonaj instrukcja
" itd.
" Może nie wykonać się ani razu !
11
Instrukcja do-while
Instrukcja  Wykonuj, dopóki spełniony warunek
Sprawdza warunek po wykonaniu instrukcji.
do
instrukcja
while (warunek) ;
" Powtarzaj instrukcja, dopóki jest spełniony warunek,
czyli:
" wykonaj instrukcja
" sprawdz
warunek
" jeśli spełniony, wykonaj instrukcja
" sprawdz
warunek
" itd.
" Zawsze wykona się przynajmniej jeden raz !
12
Instrukcja złożona w pętlach while
W pętlach typu while może być tylko jedna instrukcja. Ale - może
to być instrukcja złożona, czyli w postaci {...}
zalecany styl 
lepiej użyć while
while (warunek) {
niż do-while
...
...
}
do {
...
...
...
}
while (warunek) ;
13
Zasięg zmiennych
UWAGA :
zmienne zdefiniowane w jakimś bloku (instrukcji złożonej, bloku if, bloku else, bloku
pętli) są dostępne w całym tym bloku poczynając od miejsca tej definicji i
niedostępne poza tym blokiem
do { ...
char zn; // tak nie wolno...
cout << "czy konczymy?" < cin>>zn;
}
while (zn != 'T' && zn != 't' ); // ... bo zmienna zn nie jest tu dostępna
// zmienną zn trzeba więc zdefiniować przed pętlą do
if (a>0)
int b=0;
cout << b; // tak nie wolno, zmienna b nie jest tu dostępna
if (a>0)
int b=0;
else
b=20; // tak nie wolno, zmienna b nie jest tu dostępna
14
Pętle while i do-while: podsumowanie (1)
Wczytać ciąg liczb dodatnich zakończony niedodatnią i obliczyć ich sumę.
Pytanie - wliczać do sumy tę ostatnią niedodatnią (wersja A) czy nie (wersja B)?
// A - wczytuje liczby aż do napotkania niedodatniej
// B - wczytuje liczby aż do napotkania
// i je sumuje, łącznie z tą niedodatnią
// niedodatniej i sumuje tylko te dodatnie
zalecany styl
cin>>a;
zalecany styl
s = a; // pierwsza liczba zawsze wchodzi do sumy
s=0;
while (a>0) {
cin>>a; //pierwsze wczytanie - przed pętlą
cin>>a;
while (a>0) {
s = s+a;
s = s+a;
}
cin>>a; // kolejne wczytane a będzie
// sprawdzone w następnym cyklu pętli
s=0;
do { }
cin>>a;
s = s+a;
s=0;
} do {
while (a>0); cin>>a;
// wersja poprawna, ale pętla do nie jest zalecana
if (a>0) s = s+a;
}
// wersja błędna (ani A, ani B) - przy wejściu do
// pętli while zmienna a nie jest określona
while (a>0);
s=0; // wersja poprawna, ale pętla do nie jest zalecana
// i do tego musimy dwa razy sprawdzić warunek
while (a>0) {
//a>0
cin >> a;
s = s+a;
}
15
Pętle while i do-while: podsumowanie (2)
" Warunek w pętli while jest warunkiem, przy którym pętla ma się  kręcić w kółko .
Jest on więc negacją warunku, przy którym należy wyjść z pętli.
" Wykonując negację warunku, w którym są operatory logiczne, należy pamiętać,
że negacja sumy logicznej zamienia się w iloczyn negacji - i na odwrót.
Przykład:
- jeśli pętla ma się wykonywać aż do napotkania małej litery, to oznacza, że pętla
ma się wykonywać, dopóki znak nie jest małą literą, czyli:
" while (znak< a || znak > z )
Warunek ten można też zapisać następująco:
" while (! (znak>= a && znak<= z ))
// Przykład:
Błędem natomiast jest zapis w postaci:
// pętla wymusza na użytkowniku
// napisanie małej litery:
do {
" while (znak< a && znak > z )
cout<< Napisz mala litere\n ;
cin>>znak;
gdyż warunek w nawiasie jest zawsze
}
niespełniony !!! while (znak< a || znak > z );
16
Pętla for - wprowadzenie
Wczytać N liczb (N - stała) i obliczyć ich sumę.
Pętla do-while
....... Pętla while
.......
s=0; i=0;
s=0; i=0;
do {
while (i cin>>a;
cin>>a;
s+ = a; lepiej:
s+ = a;
i++;
i++;
}
}
while (i// może nie wykonać się ani razu
// pętla zawsze wykona się chociaż raz,
.......
// więc wynik nieprawidłowy, jeśli N<=0
........
Pętle for  wersje równoważne
....... .......
prościej
s=0; s=0;
for ( i=1; i<=N; i++ ) { for ( i=0; i cin>>a; cin>>a;
s+ = a; s+ = a;
} }
// może nie wykonać się ani razu // może nie wykonać się ani razu
....... .......
17
Pętla for
Instrukcja for   Dla
Wykorzystywana jest, gdy znana jest liczba powtórzeń.
for (inicjowanie; warunek; krok)
instrukcja
" Wykonuj instrukcja dla wyrażeń umieszczonych w nawiasie za for, czyli:
" wykonaj inicjowanie;
" sprawdz
warunek;
" jeśli spełniony, wykonaj instrukcję, a potem krok;
" sprawdz
warunek;
" jeśli spełniony, wykonaj instrukcję, a potem krok;
" itd.
" Może nie wykonać się ani razu !
for ( i=1; i<=N; i++ )
cout << i << endl;
// drukuje pod sobą liczby od 1 do N
// po wyjściu z pętli i jest równe N+1
18
Pętla for c.d.
for (inicjowanie; warunek; krok) instrukcja
" inicjowanie i krok można traktować jak instrukcje, z tą różnicą, że one
same w sobie nie kończą się średnikiem
" zarówno inicjowanie, jak i krok mogą być nawet ciągiem instrukcji - bez
średnika, ale oddzielonych przecinkami (które pełnią rolę operatorów)
" każda z trzech składowych (inicjowanie; warunek; krok) może być
pusta, ale średniki je rozdzielające są konieczne. Pusty warunek uważany
jest za prawdziwy
" instrukcja wykonująca się w pętli też może być pusta ( nic nie rób ), jak
każda inna instrukcja:
for ( i=1; i<=N; i++ ); // w tej pętli wykonuje się instrukcja pusta
cout << i << endl; // to wykona się tylko raz (poza pętlą!!!)
niebezpieczna pułapka
UWAGA: warunek (w if-ach, pętlach) może być liczbą
lub ogólnie wyrażeniem dającym się zamienić na liczbę, przy czym:
" wartość równa 0 traktowana jest jako fałsz (stała false)
" wartość różna od 0 traktowana jest jako prawda (stała true).
// pętla nieskończona // to też pętla nieskończona
// i to też pętla nieskończona
for ( ; ; ) { while ( 1 ) {
while ( true ) {
... ...
...
} }
}
zalecany styl
19
Pętla for - zasięg zmiennych
Zmienne inicjowane w pętli for mogą być od razu przy tej okazji definiowane:
for ( int i=1; i cout << i << endl;
Ale UWAGA :
zmienna zdefiniowana w pętli for jest dostępna tylko w obszarze tej pętli:
for ( int i=1; i cout << i << endl;
cout << " po wyjsciu z petli i= " << i; // tak nie wolno - zmienna i nie jest tu dostępna
int main ( ) {
...
int i;
for (i=1; i cout << i << endl ; zmienna i dostępna jest w całym tym obszarze
cout << "po wyjsciu z petli i= " << i;
}
20
Pętle zagnieżdżone
" Jeśli kilka instrukcji ma się wykonywać w pętli, trzeba z nich zrobić jedną,
czyli umieścić w nawiasach {...}
" Instrukcja if, switch, dowolna pętla są pojedynczymi instrukcjami (!) i mogą
być umieszczone w pętli for bez ujmowania ich w nawiasy {...}
W dowolnej pętli może wykonywać się inna pętla, a w niej kolejna...itd.
Kolejność przetwarzania zagnieżdżonych pętli jest taka, że najbardziej
wewnętrzna pętla wykonywana jest w pierwszej kolejności.
Przykład 1:
Dla wszystkich możliwych par (x,y), gdzie x=0, 1...10, zaś y=1,2,4,8,...256 drukować
wartości x, y i wartość funkcji 3x+2y.
// czyli dla każdej wartości x przechodzimy przez wszystkie możliwe wartości y:
for ( x=0; x<=10; x++)
for ( y=1; y<=256; y *=2 )
cout << x << "\t" << y << "\t" << 3*x+2*y < // dzięki znakom tabulacji "\t" lub '\t' wyniki będą drukowane w równych kolumnach
21
Pętle zagnieżdżone c.d.
Przykład 2:
Wydrukować wszystkie możliwe kombinacje
wartości i, j k, zawartych w przedziale od 0 do N.
for ( int i=0; i<=N; i++)
for ( int j=0; j<=N; j++)
for ( int k=0; k<=N; k++)
cout << i << "\t" << j << "\t" << k <" krok pierwszy zmiany i
i=0; j=0; k=0..N;
" krok drugi zmiany i
i=0; j=1; k=0..N;
...
" ...
i=0; j=N; k=0..N;
" krok ostatni zmiany i
i=N; j=0; k=0..N;
i=1; j=0; k=0..N;
i=N; j=1; k=0..N;
i=1; j=1; k=0..N;
...
...
i=N; j=N; k=0..N;
i=1; j=N; k=0..N;