S t r o n a

| 1 WETI Politechnika Gdańska, POP v.1.5.2

Laboratorium 3. Iteracje

Przed zajęciami laboratoryjnymi zapoznaj się z następującymi pozycjami literatury:

1.

Wykład z przedmiotu „Podstawy programowania”

2.

J. Grębosz „Symfonia C++” tom 1. Oficyna Kallimach, Kraków, 1999

Rozdziały: 2.3, 2.4, 2.5 , 2.7, 2.9, 2.10, 4.1.

Przygotowując się do laboratorium przeanalizuj podane poniżej przykłady, odpowiedz na pytania, rozwiąż testy

i napisz odpowiednie programy. Po zajęciach zrób zadania podane w ostatnim punkcie tego opracowania.

Przykłady i pytania

1.

Instrukcje iteracyjne - trzy rodzaje pętli: while, do-while, for

Przykład L3_F0_P1 Przeanalizuj program i odpowiedz na pytania

// L3_F0_P1.cpp

// Program wypisuje liczby od 1 do 20 uzywajac petli while

#include

<iostream>

using namespace

std;

int

main()

{

int

i = 1;

// definicja i inicjalizacja zmiennej i

while

( i <= 20 )

// poczatek petli while

{
cout << i <<

" "

;

// wypisanie wartosci zmiennej i oraz spacji

i++;

// zwiekszenie i. Rownowazne z i = i + 1; albo i +=1;

}

// koniec petli while

cout << endl;

// przejscie do nowej linii

system(

"pause"

);

return

0;

}

Pytania

a)

Jak zastąpić blok ITERACJA przez równoważną instrukcję do-while?

b)

Jak zastąpić blok ITERACJA przez równoważną instrukcję for( pole1 ; pole2 ; pole3 ). Wypełnij pola.

c)

Jak zastąpić blok ITERACJA przez równoważną pętlę nieskończoną while(1) i instrukcję

break.

d)

Jak zastąpić blok ITERACJA instrukcją for

oraz instrukcją

continue, tak aby program wypisywał liczby od 20

do 1 z pominięciem liczby 13.

Skompiluj i uruchom programy i sprawdź poprawność odpowiedzi.

Odpowiedzi

a)

do

{cout << i <<

" "

; i++; }

while

( i <= 20 );

b)

for

( ; i<=20; cout << i <<

" "

, i++);

c)

while

(1){ cout << i <<

" "

;

if

(i==20)

break

; i++;}

d)

for

( i=20; i>= 1; i--) {

if

(i==13)

continue

; cout << i <<

" "

;}

S t r o n a

| 2 WETI Politechnika Gdańska, POP v.1.5.2

2.

Błędy numeryczne w obliczeniach na liczbach zmiennoprzecinkowych

Przykład L3_F0_P2 Przeanalizuj program i odpowiedz na pytania

/*

* L3_F0_P2.cpp

*

* PROGRAM DWUKROTNIE OBLICZA SKONCZONA SUME CIAGU:

* S = 1./1 + 1./2 + 1./3 + 1./4 + ... + 1./n gdzie n=100000000

* Kropki po jedynkach we wzorze wskazuja, ze nie sa to obliczenia na liczbach

* calkowitych ( dla nich wynik bylby staly S=1 ).

* W pierwszej petli for sumowanie rozpoczyna si

ę

od najwiekszego skladnika sumy.

* W drugiej petli for sumowanie rozpoczyna si

ę

od najmniejszego skladnika sumy.

*/

#include

<iostream>

using namespace

std;

int

main()

{

float

fx = 0;

for

(

long int

i=1; i<=100000000; i++)

{
fx = fx + 1./i;
}

cout << fx << endl;

float

fy = 0;

for

(

long int

i=100000000; i>=1; i--)

{
fy = fy + 1./i;
}

cout << fy << endl;

system(

"pause"

);

return

0;

}

Pytania

a)

Sprawdź w Literaturze, jak są reprezentowane liczby zmiennoprzecinkowe. Czy wszystkie liczby

rzeczywiste są dokładnie reprezentowane w zapisie binarnym używanym w komputerze?

b)

Skompiluj, uruchom program i porównaj obliczone sumy. Czy obie sumy są równe? Jeżeli nie są równe, to

dlaczego?

c)

Zastąp typ float typem double, ponownie skompiluj i uruchom program. Porównaj wyniki. Który z użytych

typów liczb zmiennoprzecinkowych dokładniej reprezentuje liczby rzeczywiste?

Odpowiedzi

a)

Nie.

b)

Nie. Z powodu kumulujących się błędów numerycznych.

c)

Typ double.

S t r o n a

| 3 WETI Politechnika Gdańska, POP v.1.5.2

3.

Pętle zagnieżdżone (pętle wewnątrz innych pętli)

Przykład L3_F0_P3 Program rysuje brzeg prostokąta znakami ’x’. Długości boków użytkownik podaje na

standardowym wejściu jako liczby całkowite z przedziału [2, 60].

Przeanalizuj program i odpowiedz na pytania

// L3_F0_P3.cpp

/* Program rysuje brzeg prostok

ą

ta znakami ’x’.

xxxxxxxxxxxxxxxxxxxxx

x x

x x b

x x

xxxxxxxxxxxxxxxxxxxxx

a

*/

#include

<iostream>

using namespace

std;

int

main()

{

int

a;

// dlugosc boku a

int

b;

// dlugosc boku b

// wczytaj boki: a oraz b

cout <<

"Podaj dlugosc boku a [2,60]: "

;

cin >> a;
cout <<

"Podaj dlugosc boku b [2,60]: "

;

cin >> b;

// zakładamy ze podane dane sa poprawne

for

(

int

i = 1; i <= a; i++)

cout <<

'x'

;

// rysowanie gornej linii

cout << endl;

for

(

int

j = 2; j <= b-1; j++)

// petla kolejnych wierszy - rysowanie linii bocznych

{
cout <<

'x'

;

// znak ’x’ na lewym brzegu

for

(

int

i = 2; i < a; i++)

// wypisanie a-2 spacji we wn

ę

trzu j-tego wiersza

cout <<

' '

;

cout <<

'x'

<< endl;

// znak ’x’ na prawym brzegu

}

for

(

int

i = 1; i <= a; i++)

cout <<

'x'

;

// rysowanie dolnej linii

cout << endl;

system(

"pause"

);

return

0;

}

Pytania

a)

Skompiluj i uruchom program dla (a = 60, b = 20) oraz (a = 2, b = 2). Jaka jest kolejność wypisywania

znaków na ekranie?

b)

W programie użyto 4 pętli for, przy czym pętla druga jest zagnieżdżona w pętli trzeciej. Czy ilość

zagnieżdżeń jest ograniczona? Czy można zagnieżdżać w sobie pętle różnego typu?

c)

Napisz program L3_F0_P3.cpp tak, aby użyć tylko dwóch instrukcji iteracji (można dodatkowo użyć

instrukcji warunkowych). Ponownie skompiluj i uruchom program.

Odpowiedzi

a)

Wierszami, z góry na dół. W wierszu, od lewej do prawej.

b)

Nie. Tak.

S t r o n a

| 4 WETI Politechnika Gdańska, POP v.1.5.2

c)

//-------------------------------------------------------------rysowanie--------

for

(

int

y = 1; y <= b; y++)

// petla wierszy

{

for

(

int

x = 1; x <= a; x++)

// petla kolumn

{

if

( (y == 1) || (y == b) )

// pierwszy i ostatni wiersz rysujemy

cout <<

'x'

;

// jako linie ciagla ( znaki ‘x’)

else

if

( (x == 1) || (x == a) )

// pierwsza i ostatnia kolumne rowniez

cout <<

'x'

;

// rysujemy jako linia ciagla ( znaki ‘x’)

else

cout <<

' '

;

// pozostaly obszar wypelniamy spacjami

}

// koniec petli kolumn

cout << endl;

// po kazdym wierszu przejscie do nowej linii

}

//--------------------------------------------------------------------------------

Testy

1.

Co wypiszą na ekranie następujące iteracje?

a)

int

i=5;

while

(i >= 0) {

cout << i+1 <<

' '

;

i--;
}

cout << endl;

b)

int

j=8;

do

{

cout <<

'-'

;

j--;

if

(j<5)

continue

;

cout <<

'+'

;

}

while

(j);

cout << endl;

c)

int

x=1, max=1;

for

(

int

k=0; k<3 ; k+=1){

while

(x <= max) cout << x++;

cout << endl;
max++;
x=1;
}

2.

Czy poniższe pętle są równoważne, w sensie wypisywanych wyników, z iteracją z Testu 1 a)?

a)

for

(

int

i=7, k=2 ; ; k++){

cout << i-k+1 <<

' '

;

if

(k > i-1)

break

;

}

b)

int

i=5;

do

{

cout << i+1 <<

' '

; i-=1;

}

while

(i);

c)

int

k=2;

for

(k--, k--; k<6; cout << 6-k <<

' '

, k+=1);

3.

Które pętle kompilator uzna za nieprawidłowe ze względu na błędy syntaktyczne?

a)

for

(;0;)

for

(;1;)

for

(;2;);

b)

for

(

int

a=11, b=a+4; ; b-=1, cout<<b);

c)

for

(

int

a=2,,a++)

if

(a==2)

break

;

d)

while

(1)(cout <<

"hello\n"

;

break

;)

e)

do

{cout <<

"witaj\n"

;

break

;}

while

{1};

S t r o n a

| 5 WETI Politechnika Gdańska, POP v.1.5.2

4.

Wskaż pętle, które nigdy się nie kończą:

Pętla 1:

int

k = 12;

while

(k){ cout <<

"Jupi!\n"

; }

Pętla 2:

for

(

int

i = 0; i < 100; i = i-2)

cout <<

":) "

;

Pętla 3:

int

progress = 1;

cout <<

"Loading, please wait"

;

do

{

cout <<

"."

;

if

(progress == 100)

break

;

progress = progress + 2;

}

while

(1);

Pętla 4:

int

j = 15;

do

{

if

(j%2 == 0) j = j-2;

else

j = j-1;

}

while

(j);

Pętla 5:

int

j = 15;

do

{

if

(j%2 == 0) j = j-2;

else

j = j-1;

}

while

(j = 8);

5.

Podaj liczby, jakie należy wczytać w poniższych pętlach, aby pętle zakończyły się:

a)

int

c, d;

do

{

cin >> c >> d;
d = d+1;
}

while

( !(c==d-3 and d==5));

b)

int

m, n;

do

{

cin >> m >> n;
}

while

( n!=m-2 or m!=5);

Odpowiedzi

Test 1:

a)

6 5 4 3 2 1

b)

-+-+-+-----

c)

1

12

123

Test 2: a) tak, b) nie, c) tak.

Test 3: a), b) – prawidłowe; c), d), e) – nieprawidłowe.

Test 4: Pętle 1, 2, 3 i 5 nie kończą się. Pętla 4 kończy się dla każdej początkowej dodatniej liczby j .

Test 5: a) c = 2, d = 4, b) m = 5, n = 3.

S t r o n a

| 6 WETI Politechnika Gdańska, POP v.1.5.2

Zadania przygotowujące do laboratorium

Napisz, uruchom i przetestuj następujące programy

Zadanie L3_F0_Z1

Napisz program wyznaczający sumę n iloczynów liczb naturalnych o postaci:

= 1 ∙ 2 + 2 ∙ 3 + ⋯ + ( + 1)

gdzie n jest podawane z klawiatury przez użytkownika.

Program nie wykonuje obliczeń i podaje komunikat "Zła wartość n", gdy n nie należy do przedziału [2, 100].

Przykład:

dla n = 2 wynik jest w postaci:

= 1 ∙ 2 + 2 ∙ 3 = 6

dla n = 10 wynik jest w postaci:

= 1 ∙ 2 + 2 ∙ 3 + ⋯ + 10 ∙ 11 = 440

Polecenie: W podanym niżej szkielecie programu L3_F1_S1.cpp uzupełnij linie oznaczone przez //$$$. Nie zmieniaj

pozostałych części szkieletu.

// L3_F0_S1.cpp Suma iloczynow – Iteracja ograniczona

#include

<iostream>

using namespace

std;

int

main()

{

int

i;

// licznik petli

int

n;

// dana wejsciowa n

int

suma ;

// suma iloczynow

//---------------------------------------------------------------------------------

cout <<

"Program wyznacza sume 1*2+2*3+...+n*(n+1)"

<< endl;

cout << endl <<

"Podaj wartosc n: "

;

//$$$ wczytanie n

if

( ) {

//$$$ czy n jest poprawne?

suma = ;

//$$$

i = ;

//$$$

while

( ) {

//$$$ petla - obliczanie sumy

suma =

//$$$

i++;

// to samo co i=i+1; albo i += 1;

}
cout << endl <<

" 1*2+...+"

<< <<

'*'

<< <<

" = "

<< << endl;

//$$$

}

else

cout << endl << << endl;

//$$$

//---------------------------------------------------------------------------------

cout << endl;
system (

"pause"

);

return

0;

}

S t r o n a

| 7 WETI Politechnika Gdańska, POP v.1.5.2

Rozwiązanie

// L3_F0_Z1.cpp Suma iloczynow – Iteracja ograniczona

#include

<iostream>

using namespace

std;

int

main()

{

int

i;

// indeks petli

int

n;

// dana wejsciowa n

int

suma ;

// suma iloczynow

//-----------------------------------------------------------------------------------

cout <<

"Program wyznacza sume 1*2+2*3+...+n*(n+1)"

<< endl;

cout << endl <<

"Podaj wartosc n: "

; cin >> n;

//$$$

if

( n >= 2 && n <= 100 ) {

//$$$

suma = 0 ;

//$$$

i = 1 ;

//$$$

while

( i <= n ) {

//$$$

suma = suma + i*(i+1);
i++;
}
cout << endl <<

" 1*2+...+"

<< n <<

'*'

<< n+1 <<

" = "

<< suma << endl;

//$$$

}

else

cout << endl <<

"Zla wartosc n"

<< endl;

//$$$

//------------------------------------------------------------------------------------

cout << endl;
system (

"pause"

);

return

0;

}

Zadanie L3_F0_Z2

Napisz program, który na przemian dodaje i odejmuje kolejno wczytane liczby całkowite, aż do wczytania liczby

zero. Po podaniu każdej kolejnej liczby program wyświetla aktualną sumę.

// L3_F0_Z2.cpp Program dodaje i odejmuje (na przemian) liczby - Iteracja warunkowa

#include

<iostream>

using namespace

std;

int

main( )

{

int

liczba;

int

suma = 0;

int

znak = 1;

do

{

if

(znak > 0) cout <<

"Dodaj "

;

else

cout <<

"Odejmij "

;

cout <<

"liczbe calkowita: "

;

cin >> liczba;
suma = suma + znak*liczba;
cout <<

"Suma: "

<< suma << endl << endl;

znak = -znak;
}

while

( liczba != 0 );

system(

"pause"

);

return

0;

}

S t r o n a

| 8 WETI Politechnika Gdańska, POP v.1.5.2

Zadanie L3_F0_Z3

Napisz program rysujący trójkąt prostokątny równoramienny za pomocą znaku ’o’. Długość przyprostokątnych

zadaje użytkownik jako liczbę całkowitą w zakresie od 1 do 30. Program sprawdza poprawność wczytanej liczby.

Przykład: Wynik działania programu dla n = 7

ooooooo
oooooo
ooooo
oooo
ooo
oo
o

// L3_F0_Z3.cpp Rysowanie Trojkata - Petle zagniezdzone

#include

<iostream>

using namespace

std;

int

main()

{

char

znak =

'o'

;

int

n;

// licznik linii = dlugosc przyprostokatnej

cout <<

"Podaj dlugosc przyprostokatnej [1, 30]: "

;

cin >> n;

if

( (n < 1) || (n > 30) )

{
cout <<

"Blad: dlugosc przyprostokatnej spoza zakresu"

<< endl;

system(

"pause"

);

exit(0);
}

// ----------------------------------------------------------rysowanie-------

while

(n) {

// petla liczaca linie, petla trwa dopoki n rozne od zera

for

(

int

i = 1; i <= n; i++)

cout << znak;

// petla rysujaca jedna linie

cout << endl;

// przejdz do nastepnej linii

n--;

// zmniejsz licznik n = n-1;

}

system(

"pause"

);

return

0;

}

Zadanie L3_F0_Z4

Niech

= 1

oraz

=

+

1

Dla danego n (liczba naturalna, 0 < n < 11) obliczyć n pierwszych wyrazów ciągu liczb rzeczywistych

, … , oraz

wyświetlić je w kolejnych liniach na ekranie z dokładnością 4 miejsc po przecinku.

Przykład:

Wej

ś

cie:

Wyj

ś

cie:

3

2.0000

4.5000

13.8333

S t r o n a

| 9 WETI Politechnika Gdańska, POP v.1.5.2

//L3_F0_Z4.cpp - Wypisywanie wyrazow ciagu wg wzoru

#include

<iostream>

#include

<iomanip>

using namespace

std;

int

main ()

{

int

n, i=1;

double

a=1;

cout <<

"Podaj n : "

;

cin >> n;

if

( n<=0 || n>=11 )

{
cout <<

"zle dane\n\n"

;

system(

"PAUSE"

);

exit(0);
}

cout << fixed << setprecision(4);

while

(n--)

{

// wartosc a po prawej stronie wyrazenia jest elem. ciagu z poprzedniej iteracji,

a = a*i + 1./i;

// natomiast po lewej stronie jest elementem ciagu wyznaczanym w biezacej iteracji

i = i + 1;
cout << setw(15) << a << endl;
}

system(

"PAUSE"

);

return

0;

}

Zadania do samodzielnego rozwiązania po laboratorium

Zadanie L3_F3_Z1

Oblicz przybliżoną wartość funkcji sinus dla kąta x

r

podanego w radianach jako liczba rzeczywista. Przybliżenie

wartości funkcji wyznacz na podstawie jej rozwinięcia w szereg potęgowy:

( ) = 1 − 3! +

5! −. . . =

= # + #

$

+ # + …

Iteracje są kontynuowane dopóki wyraz w

i

szeregu jest większy od zadanej dokładności eps. Skorzystaj z faktu, że

# = &

'(

= 1

−1 ∙

#

−1

2

(2 − 2)(2 − 1)

'(

> 1

*

co oznacza, że kolejny wyraz szeregu można obliczyć na podstawie wartości wyrazu poprzedniego.

Wejście: x

r

oraz eps (obie liczby rzeczywiste np. x

r

= 30.0, eps = 1e-8).

Wyjście: wartości funkcji sinus wyznaczone odpowiednio na podstawie szeregu oraz przy pomocy funkcji sin

z biblioteki <cmath>. Obie liczby wypisz w formacie wykładniczym (10 miejsc po przecinku). Podaj liczbę

wyrazów szeregu większych od eps.

Testując program porównaj wyniki dla różnych wartości eps.

S t r o n a

| 10 WETI Politechnika Gdańska, POP v.1.5.2

Zadanie L3_F3_Z2

Napisz program tablicujący funkcję sinus w zakresie od 0 do 360 stopni z krokiem 5 stopni. Obok wartości kąta

w stopniach oraz wartości funkcji wypisywanych w równych kolumnach, z lewej strony ekranu należy dodatkowo

rysować szkic wykresu funkcji wykorzystując znak ’*’ (patrz rysunek). Przesunięcie gwiazdki o odpowiednią ilość

znaków wylicz na podstawie wartości funkcji. Przyjmij, że przedział [-1,1], do którego należą wartości funkcji,

odpowiada 60 znakom na ekranie.

Przykład:

x sin(x) -1 0 1

-----------------------------------------------------------------------------

0.000 0.000 *

5.000 0.087 *

10.000 0.174 *

15.000 0.259 *

20.000 0.342 *

25.000 0.423 *

30.000 0.500 *

. . . .

. . .

Zadanie L3_F3_Z3

Ciąg Collatz’a jest ciągiem danym następującym wzorem

+

,

= -

1

2 +

.'/ + 01 2 3 45/ 2

3+ + 1 .'/ + 01 2 13 45/ 2

*

Zauważ, że kolejne wyrazy ciągu Collatz’a mogą przyjmować różne wartości w zależności od wartości pierwszego

wyrazu c

0

.

Przykład:

c

0

= 20 C

20

= (20, 10, 5, 16, 8, 4, 2, 1)

c

0

= 19 C

19

= (19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, . . . , 1)

c

0

= 18 C

18

= (18, 9, 28, 14, 7, 22, . . . , 1)

Napisz program, który wypisuje elementy ciągu Collatz’a zaczynającego się od podanej na wejściu programu

liczby całkowitej c

0

będącej pierwszym wyrazem ciągu. Program powinien zakończyć wypisywanie, gdy wartość

kolejnego wyrazu będzie miała wartość równą 1.

Zadanie L3_F3_Z4

Hipoteza Collatz’a mówi, że niezależnie od jakiej liczby c

0

zaczniemy, zawsze dojdziemy do wyrazu o wartości

równej 1. Napisz program, który dla każdego 1 < c

0

< 10

4

sprawdza, czy hipoteza Collatz’a jest prawdziwa.

Hipotezę udowodniono dotychczas dla liczb mniejszych niż 20*2

58

. Program powinien wyznaczyć c

0

, z podanego

powyżej zakresu, dla którego wygenerowany ciąg ma najwięcej elementów oraz podać liczbę tych elementów.

Zastanów się czy jest gwarancja, że program, który napisałeś w zadaniu L3_F3_Z3 jest poprawny? Czy zatrzyma

się on dla każdych danych wejściowych? Jeżeli nie, to jak można zabezpieczyć się przed jego ewentualnym

„zapętleniem”, czyli nieskończonym działaniem?