C Zadania z Programowania

background image

Zadania z Programowania C++ M

z dnia 5 stycznia 2007

Środowisko pracy. Program make. Debugger ddd.

Zad. 1.

Dokonaj kompilacji pliku źródłowego hello.cc

1

do pliku z pro-

gramem binarnym hello. Uruchom program.

Zad. 2.

Dokonaj kompilacji pliku żródłowego hello.cc do pliku hello.o,

a następnie do pliku hello. Uruchom program.

Zad. 3.

Dokonaj kompilacji plików źródłowych hellobis.cc i pisz.cc w

celu otrzymania programu hellobis. Uruchom program.

Zad. 4.

Przygotuj wersje binarne programów hello i hellobis

a) z wykorzystaniem bibliotek dynamicznych,

b) w wersji statycznej.

Zad. 5.

Napisz plik Makefile z jawnymi zasadami kompilacji programów

hello i hellobis. Dodatkowo zdefiniuj regułę clean usuwającą wszystkie
pliki pośrednie .o oraz wynikowe (hello i hellobis).

Zad. 6.

Napisz plik Makefile z domyślnymi zasadami kompilacji progra-

mów w językach C i C++. Następnie korzystając z tych zasad dopisz reguły
związane z przygotowaniem programów hello i hellobis.

Zad. 7.

Wykorzystując predefiniowane reguły kompilacji napisz plik Ma-

kefile przygotowujący programy hello i hellobis w sposób wymagany dla
śledzenia ich pracy debuggerem.

Zad. 8.

Korzystając z jawnych poleceń napisz plik Makefile, który dla

pliku sprawozdanie.tex będzie umożliwiał utworzenie wersji .dvi (make
sprawozdanie.dvi), .ps i .pdf. Zadbaj aby proces L

A

TEXowania wykonać

dwukrotnie. Następnie stwórz kolejny plik Makefile z domyślnymi zasadami
L

A

TEXowania dla plików źródłowych o nazwach zakończonych na .tex.

Zad. 9.

Na przykładzie programów hello, hellobis i pierwsze porównaj

jakość kodu (rozmiar, szybkość wykonania) wygenerowanego przez kompila-
tor z opcją -O0 i -O2. Dla pomiaru czasu skorzystaj z polecenia time.

Zad. 10.

Dokonaj kompilacji programów hello, hellobis i pierwsze z

poziomu edytora (np. Emacs w systemie Linux, Scintilla w systemie MS
Windows).

1

Wersje źródłowe programów dostępne są w katalogu ~pablo/progs.

1

background image

Zad. 11.

Przy pomocy debuggera (ddd w systemie Linux, td32 w systemie

MS Windows) prześledź wykonanie programów hello, hellobis i pierwsze.
W programie pierwsze obserwuj wartości zmiennych i i j oraz zmień war-
tość zmiennej i. Następnie poleceniem strip usuń z pliku binarnego dane
potrzebne do śledzenia pracy programu.

Operacje wejścia/wyjścia

Zad. 12.

Korzystając ze stałej M_PI zdefiniowanej w pliku nagłówkowym

cmath napisz program pi wypisujący do standardowego strumienia wyjścio-
wego 5 kolejnych potęg liczby π z dokładnością liczby cyfr po przecinku równą
wykładnikowi potęgi

potęga wartość
----------------
1

3.1

2

9.87

3

31.006

4

97.4091

5

306.01968

Przygotuj dwie werjse rozwiązania: pierwszą w oparciu o funkcję printf
charakterystyczną dla języka C i drugą korzystającą z biblioteki iostream
języka C++.

Zad. 13.

Napisz program liczby odczytujący ze standardowego stru-

mienia wejściowego dwie liczby całkowite (int) i zapisujący do standardo-
wego strumienia wyjściowego wartości odczytanych liczb, ich iloraz i sumę.
Sprawdź działanie programu dla następujących danych wejściowych

• 1, 3

• 2, 0

• 3, 1.5

• 7, a

Następnie dokonaj zmiany odczytywanych liczb na rzeczywiste (double) i
ponownie sprawdź działanie programu.

Zad. 14.

Począwszy od bieżącego semestru nasz wydziałowy barek wpro-

wadził nowy sposób obsługi dla klientów będących studentami zapisanymi
w systemie USOS. Barek udziela kredytu, pod warunkiem, że osoba zamówi
dokładnie 3 rzeczy. W celu rozliczenia przesyła następnie studentowi maila
z rachunkiem, np. w pliku rachunek.txt

2

background image

kanapka: 2.50
szarlotka: 1.50
woda mineralna: 1.50

Treść listu składa się zawsze z 3 wierszy. Każdy wiersz zawiera nazwę towaru,
dwukropek, cenę w złotych. Nazwa towaru może się składać z dowolnej liczby
słów oddzielonych odstępami, a słowa wyłącznie z liter.

Napisz program suma obliczający całkowitą należność do zapłaty. Podaj

dwa rozwiązania: pierwsze charakterystyczne dla języka C, drugie dla języka
C++.

% ./suma < rachunek.txt
2.50+1.50+1.50=5.50

Zad. 15.

Plik 2pi.txt zawiera dwa wiersze. W każdym wierszu zapisana

jest wyłącznie wartość liczby π z losowo wybraną liczbą cyfr po przecinku
∈ h100, ∞). Napisz program zamiana, który zamieni kolejność tych liczb
w pliku. Podaj dwa rozwiązania: pierwsze charakterystyczne dla języka C,
drugie dla języka C++.

Zad. 16.

Korzystając z operatora sizeof sprawdź rozmiary następujących

typów danych w wykorzystywanym przez siebie kompilatorze.

• char

• short int

• int

• long int

• float

• double

• bool

• enum

• char*

Instrukcje warunkowe i iteracje

3

background image

Zad. 17.

Napisz program znaczace sprawdzajacy liczbę cyfr znaczących

typów float i double.
Wskazówka: obliczaj sumę

P

i=0

1

10

i

.

Zad. 18.

Napisz program kwadraty obliczający sumę

100 000 000

X

i=1

1

i

2

Dokonaj sumowania w kolejności

1

1

2

+

1

2

2

+

1

3

2

+ . . . +

1

100 000 000

2

oraz w kolejności odwrotnej

1

100 000 000

2

+

1

99 999 999

2

+ . . .

1

1

2

Obliczenia przeprowadź posługując się zmiennymi typu

• float

• double

Wytłumacz różnice. Który z wyników jest najbliższy prawdzie?
Wskazówka:

P


i=1

1

i

2

=

π

2

6

Zad. 19.

Napisz program anagram, który odczytuję nazwę pliku podaną

przez użytkownika, a następnie odwraca kolejność bajtów w tym pliku.

% ./anagram
Podaj nazwę pliku
a.txt
%

Zad. 20.

Korzystając z instrukcji iteracyjnych napisz program pi3 wypi-

sujący w kolejnych wierszach wartość π z dokładnością do i miejsc po prze-
cinku.

3.1
3.14
3.141
3.1415
3.14159

Zad. 21.

Korzystając z instrukcji iteracyjnych napisz program pi4 wy-

pisujący w kolejnych wierszach wartość π

i

z dokładnością do i miejsc po

przecinku.

4

background image

potęga wartość
----------------
1

3.1

2

9.87

3

31.006

4

97.4091

5

306.01968

Zad. 22.

Napisz program tworzący zadany rysunek. Warunek: instrukcję

wypisującą znak (np. *) lub liczbę w tabelce można użyć tylko jeden raz.

**********
**

*

* *

*

*

*

*

*

*

*

*

*

*

*

*

*

*

* *

*

**

**********

-------------------------
|

1

|

2

|

3

|

4

|

-------------------------
|

2

|

4

|

6

|

8

|

-------------------------
|

3

|

6

|

9

| 12

|

-------------------------
|

4

|

8

| 12

| 16

|

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

Zad. 23.

Napisz program slowa odczytujący liczbę słów ze strumienia

wejściowego i wypisujący ich liczbę oraz średnią długość. Obliczenia przepro-
wadź dla tekstów Pana Tadeusza i Hamleta.

2

Zad. 24.

Napisz program licz będące odpowiednikiem systemowego po-

lecenia wc, zliczającego liczbę znaków, słów i wierszy w standardowym stru-
mieniu wejściowym. Działanie programu sprawdź na jego pliku źródłowym
licz.cc i porównaj z programem wc.

Zad. 25.

Napisz program rzeczywista, który liczbę a podaną jako argu-

ment wypisuje w postaci

p

· 2

w

Skorzystaj z operacji na bitach i funkcji frexp, ldexp.

2

Teksty utworów dostępne są w plikach ~pablo/pt.txt i ~pablo/h.txt.

5

background image

% ./rzeczywista 2005
0.9790039062500000*2^11

Nie uwzględniaj szczególnej reprezentacji wartości 0.

Zad. 26.

Mając daną zmienną typu rzeczywistego double i wiedząc, że

jest postaci

p

· 2

w

oraz posługując się operacjami bitowymi i funkcjami frexp, ldexp skonstruuj
liczbę

p

· 2

b

w

2

c

Nie uwzgędniaj szczególnej reprezentacji wartości 0.

Zad. 27.

Napisz program pierwiastek, który oblicza pierwiastek kwa-

dratowy zadanej liczby. Nie korzystaj z istniejącej funkcji sqrt lecz zaimple-
mentuj wzór Newtona, dla którego

x = lim

n

→∞

a

n

,

gdzie (a

n

) jest ciągiem zadanym rekurencyjnie a

n+1

=

1
2

(a

n

+

x

a

n

). Wykonaj

10 iteracji przez kopiowanie fragmentu programu. Zwróć uwagę, na

a) szybkość zbiegania w zależności od początkowej wartości a

0

,

b) zachowanie dla ujemnych x.

Dla ustalenia wartości a

0

skorzystaj z poprzedniego zadania.

Zad. 28.

Korzystając ze wzoru Gaussa napisz program dzien, który ob-

licza dzień tygodnia na podstawie daty.

Numer dnia określony jest następującym wzorem

r/4

− r/100 + r/400 + 367m/12 + d + 365r ,

gdzie d

∈ {1, . . . } jest dniem miesiąca, m ∈ {1, . . . , 12} – miesiącem, r –

rokiem. Dzielenie jest typu całkowitego. Ponadto za początek roku należy
przyjąć dzień 1 marca.

Zad. 29.

Napisz program podatki obliczający wysokość podatku docho-

dowego w 2003 roku. Przyjmij następujące dane: skala 19 % dla dochodów
poniżej 37024 zł, 30 % dla dochodów poniżej 74048 zł, 40 % dla dochodów
poniżej 600000 zł, 50 % dla pozostałych. Kwota wolna od podatku to 530.08
zł.

6

background image

Dane dotyczące wysokości kwot i podatku odpowiadające poszczególnym

progom zapisz w tablicy.

Zad. 30.

Napisz program dziennik, który oblicza ile dni upłynęło od po-

danej daty do dnia uruchomienia programu. Skorzystaj z doświadczeń pro-
gramu dzien i funkcji time przekazującej liczbę sekund jakie upłynęły od
godziny 0

00

dnia 1 stycznia 1970 roku.

W zależności od wprowadzonych danych wynikiem działania programu

powinno być wypisanie jednego sposród poniższych komunikatów:

a) Dziś masz mały jubileusz!

b) Jutro masz mały jubileusz!

c) Pojutrze masz mały jubileusz!

d) Do najbliższej 1000-nicy zostało Ci n dni.

e) Czy na pewno się już urodziłeś?

Zad. 31.

Korzystając z liczb całkowitych typu int napisz program silnia

obliczający silnię zadanej liczby oraz liczbę wystąpień cyfry 7 w jej zapisie
dziesiętnym. Silnie jakiej największej liczby możemy policzyć tym progra-
mem?

Zad. 32.

Napisz program podzielne znajdujący wszystkie liczby z za-

kresu od 1 do 1000, które są podzielne przez sumę swoich cyfr.

Zad. 33.

Napisz program podzielne2 znajdujący wszystkie liczby z za-

kresu od 1 do 1000, które są jednocześnie podzielne przez sumy swoich pa-
rzystych i nieparzystych cyfr.

Zad. 34.

Napisz program cezar, który czyta bajty ze standardowego stru-

mienia wejściowego (funkcja cin.get) i przepisuje do standardowego stru-
mienia wyjściowego (cout.put) zastępując litery alfabetu łacińskiego lite-
rami znajdującymi się w alfabecie o n pozycji dalej. Wartość n odczytaj z
parametru uruchomienia programu.

Zad. 35.

Napisz program wielomian obliczający wartość wielomianu

w(x) = 100x

3

− 625x

2

+ 1183.19x

− 660.489 = 100(x − 3.19)(x − 2.05)(x − 1.01)

w zadanym punkcie. Obliczenie wartości wielomianu różnymi sposobami

a) 100 * x * x * x - 625 * x * x + 1183.19 * x - 660.489

b) ( ( 100 * x - 625 ) * x + 1183.19 ) * x - 660.489

7

background image

c) 100 * ( x - 3.19 ) * ( x - 2.05 ) * ( x - 1.01 )

d) 100 * pow( x, 3 ) - 625 * pow( x, 2 ) +

1183.19 * x - 660.489

zapisz w postaci osobnych funkcji w1, w2, w3. Porównaj wyniki obliczeń zre-
alizowanych różnymi sposobami.

Następnie zapisując na kartce wyniki i traktując program jako programo-

walny kalkulator, dzięki któremu mamy łatwość liczenia wartości wielomianu
w poszczególnych punktach, znajdź metodą bisekcji miejsca zerowe.

Zad. 36.

Napisz program bisekcja – rozwinięcie programu wielomian –

umożliwiający obliczanie miejsc zerowych wielomianu

w(x) = 100x

3

− 625x

2

+ 1183.19x

− 660.489

metodą bisekcji.

Uzyskane wyniki porównaj z dokładnymi wartościami miejsc zerowych

wielomianu.

Zad. 37.

Napisz program styczne będący modyfikacją programu bisek-

cja, znajdujący metodą stycznych, w której „kandydata” x

n

na miejsce ze-

rowe funkcji f (x) zastępujemy „kandydatem lepszym”

x

n+1

= x

n

f (x

n

)

f

0

(x

n

)

Zad. 38.

Napisz program rekurencja porównujący rekurencyjne i itera-

cyjne obliczanie

a) silni,

b) liczb Fibonacciego.

Liczby Fibonacciego zadane są rekurencyjnie f

n+2

= f

n+1

+ f

n

oraz f

0

=

f

1

= 1.

Następnie oblicz 10!, 20!, 50!, f

10

, f

20

, f

50

. Skomentuj uzyskane wyniki.

Zad. 39.

Napisz program euklides znajdujący największy wspólny dziel-

nik korzystając z algorytmu Euklidesa: znalezienie N W D(a, b), gdzie a > b
sprowadza się do (poza przypadkiem kiedy a jest wielokrotnością b) do zna-
lezienia N W D(b, reszta z dzielenia a przez b). Rozwiązanie zapisz na dwa
sposoby: iteracyjnie i rekurencyjnie.

8

background image

Zad. 40.

Napisz program newton znajdujący dla zadanego punktu x

0

miejsce zerowe wielomianu w(x) = (x

− 1)(x − 2)(x − 3)(x − 4) przy po-

mocy metody Newtona (stycznych; polegającej na „zastąpieniu” kandydata
x

i

na miejsce zerowe na ogół „lepszym” kandydatem x

i+1

= x

i

w(x

i

)

w

0

(x

i

)

). Obli-

czenia wykonaj w dziedzinie zespolonej. Następnie oblicz miejsca zerowe dla
następujących wartości początkowych x

0

:

a) 1.05, 2.1, 2.9, 4.1,

b) 2.5,

c) 2.4, 2.6.

Poniżej przedstawiono działanie przykładowego rozwiązania.

% ./newton (0.95,0.1)
w((9.4999999999999996e-01,1.0000000000000001e-01)) =

(2.0920625000000023e-01,-7.0835000000000004e-01)

w((1.0080677933838893e+00,1.8067861263060966e-02)) =

(-5.1237462461980618e-02,-1.0518620817044756e-01)

w((1.0005141051464106e+00,-5.2136674958264129e-04)) =

(-3.0847118896539993e-03,3.1223053063340199e-03)

w((1.0000000151267927e+00,9.8408636207405684e-07)) =

(-9.0771406412290008e-08,-5.9045178449450769e-06)

w((1.0000000000017750e+00,-5.4577759886899162e-14)) =

(-1.0650147430589576e-11,3.2746655931926366e-13)

%

Zad. 41.

Plik meteo.txt

3

zawiera wyniki pomiarów stacji meteorologicz-

nej działającej w budynku na ul. Pasteura. Pomiary zapisane są w kolejnych
wierszach. Każdy wiersz zawiera 11 liczb całkowitych oddzielonych spacjami,
których znaczenie jest następujące.

• 32-bitowa liczba całkowita bez znaku, czas pomiaru w konwencji sys-

temu UNIX, tzn. liczba sekund jakie upłynęły od północy 1 stycznia
1970 roku według czasu UTC (ang. Universal Time Coordinate).

• 16-bitowa liczba całkowita ze znakiem, temperatura powietrza w

1

16

C.

Wartości 10000 i 10001 oznaczają błąd podczas pomiaru.

• Osiem kolejnych 12-bitowych liczb całkowitych bez znaku to napię-

cia zmierzone na ośmiu wejściach przetwornika A/C wyrażone w mV .
Aktualnie do pierwszego wejścia przetwornika podłączony jest czujnik
wilgotności, a do piątego ciśnienia.

3

Plik znajduje się w katalogu ~pablo.

9

background image

• 8-bitowa liczba całkowita bez znaku numerująca restart stacji (np. po

chwilowym braku zasilania).

Napisz program, który

a) Przetworzy dane w taki sposób, że jego rezultatem będą wiersze zawie-

rające tylko dwie liczby: czas pomiaru i temperaturę.

b) Dodatkowo pominie wiersze zawierające błędny pomiar (wartość 10000

lub 10001).

c) W każdym wierszu dokona sprawdzenia czy składa się on z 11 liczb i

wypisze informacje o błędnych wierszach.

Wskazówka. Dla odczytania całego wiersza skorzystaj z funkcji getline.

Zad. 42.

Wyniki pomiarów pewnego eksperymentu składają się z par liczb

(U, I), gdzie U jest wartością napięcia, a I wartością prądu. Pary (U, I) zapi-
sywane są w kolejnych wierszach po 12 znaków w każdym. Pierwszy symbol
wiersza + lub - określa znak wartości napięcia U . Drugi symbol wiersza + lub
- określa znak wartości prądu I. Kolejne 6 symboli to cyfry przedstawiające
wartość napięcia U wyrażoną w mV . Ostatnie 4 cyfry przedstawiają wartość
prądu I wyrażoną w 10 mA. Napisz program, który przepisze tak zapisane
dane do postaci dwóch liczb rzeczywistych odpowiadających U wyrażonemu
w V i I wyrażonemu w A oddzielonych spacją.

Wskazówka. Dla odczytania fragmentu napisu ze zmiennej string sko-

rzystaj z metody substr.

Tworzenie rysunków przy wykorzystaniu programu gnuplot

Zad. 43.

Korzystając z doświadczeń programu cezar napisz program litery1

obliczający częstość występowania poszczególnych znaków (spacji i małych
liter alfabetu łacińskiego) oraz przygotowujący plik z danymi dla programu
gnuplot. Następnie korzystając z tego programu przygotuj wykres słupkowy.

Zad. 44.

Rozbuduj program litery1 do programu litery2 aby przykła-

dowe obliczenia

% ./litery2 pt.txt h.txt

przygotowały dane (pliki pt.txt.dat, h.txt.dat oraz skrypt.gp) dla otrzy-
mania rysunku programem gnuplot:

% gnuplot -persist skrypt.gp

10

background image

Zad. 45.

Napisz program kopiuj kopiujący maksymalnie n znaków pomię-

dzy standardowym strumieniem wejściowym, a standardowym strumieniem
wyjściowym. Następnie korzystając z tego programu stwórz pliki pt100.txt,
pt1000.txt i pt10000.txt zawierające odpowiednio 100, 1000 i 10000 pierw-
szych znaków Pana Tadeusza i przy pomocy programu litery2 stwórz wy-
kres porównawczy częstotliwości występowania liter.

Program gnuplot (w wersji 4) umożliwia kolorowanie płaszczyzny. Dane w
pliku składają się z trójek (x, y, z) gdzie x, y są współrzędnymi punktu zaś
wartości z zostanie przyporządkowany kolor. Ciągi trójek (x, y, z) wyznaczają
izolinie (w terminologii gnuplotowo–fizycznej scan’y), a ciągi izolinii rysunek.
Poszczególne izolinie rozdzielają puste wiersze.

Program test przygotowuje dane kolorujące kwadrat o współrzędnych

przeciwległych wierzchołków (

−50, −50) i (50, 50) kolorem w zależności od

odległości od środka układu współrzędnych.

// Program przygotowuje dane dla programu gnuplot kolorujące punkty kwadratu
// w funkcji odległości od środka układu współrzędnych.
//
// Paweł Klimczewski, 27 listopada 2005

#include <iostream>
#include <cmath>

using namespace std;

int main()
{

for ( int y = -50; y <= 50; ++y )
{

for ( int x = -50; x <= 50; ++x )
{

double r = sqrt( x * x + y * y );
cout << x << ’ ’ << y << ’ ’ << r << endl;

}
cout << endl;

}
return 0;

}

Dokonując obliczeń i wczytując dane do programu gnuplot

% ./test > test.dat
% gnuplot

G N U P L O T
Version 4.0 patchlevel 0

11

background image

last modified Thu Apr 15 14:44:22 CEST 2004
System: Linux 2.4.26

> set pm3d map
> splot "test.dat"

otrzymujemy rysunek

Zad. 46.

Napisz program newton2 przygotowujący dane dla pokolorawa-

nia prostokątnego obszaru płaszczyzny w następujący sposób. Dla każdego
punktu (x, y) wyznaczonego przez podział siatką N na N oczek staraj się
znaleźć (metodą Newtona) miejsce zerowe wielomianu z

n

= 1 wykonując nie

więcej niż maxcnt iteracji. Jeżeli po wykonaniu i-tej iteracji znajdziemy się
nie dalej niż  od j-tego miejsca zerowego to przerywamy iteracje i jako war-
tość z (odpowiadającą kolorowi punktu) przyjmujemy j. Jeżeli po maxcnt
iteracjach nie znajdziemy się odpowiednio blisko żadnego z miejsc zerowych
jako wartość z przyjmujemy 0. Program powinien pytać o współrzędne ob-
szaru xmin, ymin, xmax, ymax, stopień wielomianu n, maksymalną liczbę
iteracji maxcnt i liczbę oczek siatki N .

Zad. 47.

Napisz program mandelbrot rysujący bodajże najsłynniejszego

fraktala jakim jest zbiór Mandelbrota. Punkt P (x, y) płaszczyzny należy do
zbioru Mandelbrota jeżeli ciąg (a

k

) : a

k

∈ Z, a

0

= 0, a

k+1

= a

k

2

+ x + iy jest

ograniczony. Okazuje się, że jeżeli

∃k, |a

k

| > 2 to ciąg nie jest ograniczony.

W programie obliczenia są skończone, zatem generowany rysunek będzie od-
powiednim przybliżeniem.

Dla każdego punktu zbadaj nie więcej niż n wyrazów ciągu (a

k

). Jeżeli

wszystkie wyrazy spełniają warunek

|a

k

| ≤  to przyjmij, że punkt należy do

zbioru Mandelbrota i pokoloruj go wartością 0. Pozostałe punkty pokoloruj w
zależności od szybkości rozbiegania (najmniejszej liczbie i, dla której

|a

i

| > ).

Jako parametry początkowe przyjmij środek kwadratu x =

−0.5, y = 0,

długość boku a = 3, n = 100,  = 2.

Biblioteka STL

Zad. 48.

Napisz program filtr odczytujący ze standardowego strumienia

wejściowego liczby rzeczywiste x

i

i wypisujący do standardowego strumienia

wyjściowego, te które należą do przedziału (¯

x

− σ, ¯

x + σ). Skorzystaj z klasy

vector.

σ =

s

P

n
i=1

x

− x

i

)

2

n

− 1

12

background image

jest średnim odchyleniem standardowym, a

¯

x =

x

1

+ . . . + x

n

n

jest średnią arytmetyczną.

Zad. 49.

Napisz program pierwsze obliczający wszystkie liczby pierw-

sze mniejsze od 1 000 000. Sprawdzenie czy i jest liczbą pierwszą wykonaj
przez obliczanie reszt z dzielenia i przez kolejne liczby całkowite z przedziału
h2, b

i

ci. Następnie zmodyfikuj program tak, aby zapamiętywał obliczane

liczby pierwsze na liście (klasa list) i sprawdzał jedynie reszty z dzielenia i
przez liczby pierwsze nie większe od

b

i

c. Porównaj szybkość obliczeń obu

wersji. (

bxc oznacza największą liczbę całkowitą nie większą od x.)

Zad. 50.

Napisz program totolotek losujący 6 różnych liczb z 49 i wy-

pisujący je do standardowego strumienia wyjściowego w sposób uporządko-
wany. Skorzystaj z klasy set. Dla wylosowania liczby skorzystaj z funkcji
rand i srand. Ograniczenie zakresu do przedziału 1, . . . , 49 wykonaj przy
pomocy reszty z dzielenia.

Zad. 51.

Wprowadzając słownik (klasa map) dla zapamiętywana już ob-

liczonych wartości wyrazów ciągu Fibonacciego popraw efektywność liczenia
n–tego wyrazu tego ciągu metodą rekurencyjną.

int fibonacci( int n )
{

return n > 1 ? fibonacci( n - 1 ) + fibonacci( n - 2 ) ? 1;

}

Zad. 52.

Napisz program lustro odczytujący ze standardowego strumie-

nia wejściowego wiersze i wypisujący je w kolejności odwrotnej, a każdy wiersz
od końca do początku. Zadbaj o „wyrównanie” do prawego marginesu tak
aby dla danych

1
23
456

otrzymać następujący wynik

654

32

1

Zad. 53.

Napisz program ciagi obliczający liczbę, parami różnych, n–

elementowych ciągów znaków w standardowym strumieniu wejściowym. Do-
konaj obliczeń dla tekstów Pana Tadeusza i Hamleta.

13

background image

Zad. 54.

Napisz program najczestsze odczytujący ze standardowego

strumienia wejściowego słowa i wypisujący pierwszą dziesiątkę najczęściej
powtarzających się słów wraz z odpowiadającymi liczbami powtórzeń. Do-
konaj obliczeń dla tekstów Pana Tadeusza i Hamleta.

Zad. 55.

Poszczególnym literom alfabetu łacińskiego przyporządkowujemy

liczby w następujący sposób: a

7→ 17, . . . , j 7→ 26, k 7→ 1, l 7→ 2, . . . , z 7→ 16.

Każdemu słowu przyporządkowujemy liczbę równą iloczynowi liczb odpo-
wiadających literom. Napisz program milion odczytujący słowa (składające
się wyłącznie z małych liter alfabetu łacińskiego) i znajdujący te o warto-
ściach najbliższych 1000000. Dokonaj obliczeń dla tekstów Pana Tadeusza i
Hamleta.

Zad. 56.

Na półce ustawiono obok siebie w sposób losowy 4 zielone, 5

czerwonych i 8 niebieskich książek. Oblicz prawdopodobieństwo zdarzenia,
że losowo wybrana książka posiada z każdej strony po n bezpośrednich sąsia-
dów tego samego koloru. Kolory książek sąsiadujących ze strony lewej mogą
być różne od książek ze strony prawej. Przykładowo zaznaczona nawiasami
kwadratowymi książka

n c z z n [ c ] c c c z c c n z

posiada bezpośrednio ze strony lewej jednego sąsiada w kolorze niebieskim, a
ze strony prawej trzech sąsiadów w kolorze czerwonym. Skorzystaj z funkcji
next_permutation i prev_permutation.

Zad. 57.

Napisz program kalkulator będący kalkulatorem liczącym w

Odwrotnej Notacji Polskiej. Program powinien czytać dane ze standardo-
wego strumienia wejściowego. Jeżeli wprowadzona dana jest liczbą program
dopisuje ją na wierzchołku stosu. Jeżeli jest jednym z symboli działań arytme-
tycznych (+,-,*,/) program odczytuje i usuwa z wierzchołka stosu dwie liczby,
które traktuje jak argumenty działania, oblicza wynik działania i umieszcza
na wierzchołku stosu. Po każdej operacji wypisuje na ekranie wartość ele-
mentu z wierzchołka stosu. Skorzystaj z klasy stack.

Zad. 58.

Napisz program odleglosci odczytujący ze standardowego stru-

mienia wejściowego liczby zespolone z

i

i przepisujący je do plików:

a) do pliku z1.txt uporządkowane względem odległości od początku układu

współrzędnych (najpierw liczby bliższe potem dalsze),

b) do pliku z2.txt uporządkowane względem odległości od prostej y = x

(najpierw liczby dalsze potem bliższe).

Zad. 59.

Napisz program poeta dopisujący kontynuację zadanego tekstu.

Program uruchomiony w sposób

14

background image

% ./poeta n < pt.txt

powinien odczytać ze standardowego strumienia wejściowego wszystkie k zna-
ków z

i

obliczając statystykę S

n

(k) częstości wystąpień n–elementowych pod-

ciągów znaków. Następnie program powinien obliczyć taki znak z

k+1

, dla

którego odległość d(S

n

(k), S

n

(k + 1)) będzie najmniejsza. I kolejno obliczać

dalsze znaki z

k+2

, z

k+3

itd.

Statystyka S

n

jest n! składnikowym wektorem. Odległość d jest zwykłą

odległością kartezjańską w przestrzeni n! wymiarowej unormowanych wekto-
rów S

n

. (Jako miarę identyczności statystyk można także przyjąć euklidesowy

iloczyn skalarny

hS

n

(k), S

n

(k + 1)

i unormowanych wektorów S

n

.)

Klasy

Zad. 60.

Napisz klasę A składającą się z

1. konstruktora domyślnego wypisującego komunikat Tworzę i–ty obiekt

klasy A,

2. konstruktora kopiującego wypisującego komunikat Tworzę i–ty obiekt

klasy A na podstawie j–go obiektu,

3. destruktora wypisującego komunikat Niszczę i-ty obiekt klasy A.

Następnie sprawdź działanie programu

int main()
{

A a;
for ( int i = 0; i < 2; ++i )
{

A b;
for ( int j = 0; j < 2; ++j )
{

A c( b );

}
A d;

}
return 0;

}

Ostatecznie deklarację klasy zapisz w pliku nagłówkowym a.h, definicję w
pliku a.cc a program w pliku main.cc.

Zad. 61.

Napisz klasę Z100, która reprezentuje liczbę całkowitą będącą

resztą z dzielenia przez 100. W klasie zdefiniuj

15

background image

1. konstruktor z argumentem typu int umożliwiający utworzenie obiektu

i nadanie mu wartości początkowej,

2. operator przypisania (operator=) umożliwiający przypisanie nowej war-

tości z innego obiektu klasy Z100,

3. operator konwersji do liczby całkowitej (operator int) umożliwiający

posługiwanie się obiektami klasy Z100 w wyrażeniach matematycznych.

Działanie klasy sprawdź przy pomocy programu

int main()
{

Z100 a = 2006;
cout << "a = " << a << endl;
a = a * a * a;
cout << "a * a * a = " << a << endl;
return 0;

}

Ostatecznie cały program zapisz w trzech plikach z100.h, z100.cc i main.cc.

Zad. 62.

Napisz klasę Tablica reprezentującą nieskończoną tablicę liczb

całkowitych int o indeksach z zakresu 0 . . .

∞ i początkowych wartościach

komórek równych 0. W klasie zdefiniuj jedynie operator indeksowania (int
operator[]). Deklarację zapisz w pliku tablica.h, a definicję w tablica.cc.

Wskazówka. W celu zapamiętania wartości komórek skorzystaj z klasy

vector.

Zad. 63.

Napisz klasę Tablica2 analogiczną do Tablica o zakresie indek-

sów

−∞ . . . ∞.

Zad. 64.

Napisz klasę Rysunek służącą do tworzenia wykresów programem

gnuplot. Zdefiniuj następujące metody

1. void punkt( double x, double y ) — dodaje do rysunku punkt o

współrzędnych (x, y),

2. void rysuj() — przygotowuje pliki z danymi, poleceniami oraz uru-

chamia program gnuplot,

3. void zeruj() — usuwa wszystkie zapamiętane punkty wykresu.

Zad. 65.

Korzystając z podanego poniżej schematu napisz klasę Wektor

reprezentującą wektor o współrzędnych (x, y) w przestrzeni R

2

o początku w

punkcie (0, 0). Następnie korzystając z tej klasy napisz program obliczający

16

background image

i wypisujący wartości wyrażeń ~a + ~b, ~b

· ~c, ~a + ~b + ~c gdzie ~a, ~b i ~c są danymi

wektorami o współrzędnych równych odpowiednio ~a = (5, 1), ~b = (3,

−2),

~c = (

−8, 1).

class Wektor
{

public:

// Konstruktor tworzy obiekt reprezentujący wektor o współrzędnych (x,y).
Wektor( double x, double y );
// Operator + oblicza wektor vs=(x1+x2,y1+y2) będący sumą dwóch wektorów
// u=(x1,y1) i v=(x2,y2).
Wektor operator+( Wektor v );
// Operator * oblicza iloczyn skalarny x1*x2+y1*y2.
double operator*( Wektor v );
// Funkcja wypisz wypisuje do standardowego strumienia cout współrzędne
// wektora w nawiasach i rozdzielone przecinkiem, np. (2,3).
void wypisz();

// Ewentualne dalsze składowe klasy potrzebne do konstrukcji.
// ...

};

Zad. 66.

Korzystając z podanego poniżej schematu napisz klasę Punkt

reprezentującą punkt o współrzędnych (x, y) na płaszczyźnie R

2

i realizującą

operację przesunięcia o zadany wektor. Następnie korzystając z tej klasy
napisz program obliczający i wypisujący współrzędne punktów P = (0, 0),
R = (3, 10), Q = (1, 2) przesuniętych o wektor ~

v = (v

x

, v

y

), gdzie o wartości

v

x

i v

y

należy spytać użytkownika programu.

class Punkt
{

public:

// Konstruktor tworzy obiekt reprezentujący punkt o współrzędnych (x,y).
Punkt( double x, double y );
// Funkcja translacja przesuwa punkt o zadany wektor (x,y).
void translacja( double x, double y );
// Funkcja oblicza odległość pomiędzy dwoma punktami.
double odleglosc( const Punkt& p );
// Funkcja wypisz wypisuje do standardowego strumienia cout współrzędne
// punktu w nawiasach i rozdzielone przecinkiem, np. (2,3).
void wypisz();

// Ewentualne dalsze składowe klasy potrzebne do konstrukcji.
// ...

};

Zad. 67.

Korzystając z podanego poniżej schematu napisz klasę Srednia

służącą do obliczania średniej arytmetycznej. W tym celu klasa powinna zli-
czać ilość oraz całkowitą sumę kolejno podawanych liczb. Korzystając z tej

17

background image

klasy napisz program obliczający średnią arytmetyczną ciągu liczb zmienno-
pozycyjnych wczytanych ze standardowego strumienia wejściowego.

class Srednia
{

public:

// Konstruktor przygotowuje obiekt do obliczania średniej.
Srednia();
// Funkcja dodaj_liczbe uwzględnia podany argument w obliczeniach.
void dodaj_liczbe( double x );
// Funkcja wypisz wypisuje do standardowego strumienia cout średnią
// arytmetyczną wszystkich liczb podanych przy pomocy dodaj_liczbe.
void wypisz();

// Ewentualne dalsze składowe klasy potrzebne do konstrukcji.
// ...

};

Zad. 68.

Korzystając z podanego poniżej schematu napisz klasę Sigma

służącą do obliczania średniego odchylenia standardowego σ. W tym celu
klasa powinna zliczać ilość, całkowitą sumę i sumę kwadratów kolejno po-
dawanych liczb. Korzystając z tej klasy napisz program obliczający średnie
odchylenie standardowe ciągu liczb zmiennopozycyjnych wczytanych ze stan-
dardowego strumienia wejściowego.
Wskazówka:

¯

x =

1

n

n

X

i=1

x

i

,

σ =

s

P

n
i=1

(x

i

− ¯

x)

2

n

− 1

=

v
u
u
t



P

n
i=1

x

2
i

+ n¯

x

2

− 2¯

x

P

n
i=1

x

i



n

− 1

class Sigma
{

public:

// Konstruktor przygotowuje obiekt do obliczania średniej.
Sigma();
// Funkcja dodaj_liczbe uwzględnia podany argument w obliczeniach.
void dodaj_liczbe( double x );
// Funkcja wypisz wypisuje do standardowego strumienia cout średnie
// odchylenie standardowe wszystkich liczb podanych przy pomocy
// dodaj_liczbe.
void wypisz();

// Ewentualne dalsze składowe klasy potrzebne do konstrukcji.
// ...

};

18

background image

Zad. 69.

Korzystając z podanego poniżej schematu napisz klasę NWD repre-

zentującą liczbę całkowitą dodatnią. Klasę wyposaż w operację / odpowia-
dającą obliczeniu największego wspólnego dzielnika według algorytmu Eukli-
desa. Następnie zastosuj ją do obliczenia największego wspólnego dzielnika
dla ciągu liczb całkowitych dodatnich odczytanych ze standardowego stru-
mienia wejściowego.

class NWD
{

public:

// Konstruktor nadaje obiektowi początkową wartość.
NWD( int i );
// Operator / oblicza największy wspólny dzielnik swoich argumentów.
NWD operator/( const NWD& i );
// Funkcja wypisz wypisuje do standardowego strumienia cout
// liczbę będącą wartością obiektu.
void wypisz();

// Ewentualne dalsze składowe klasy potrzebne do konstrukcji.
// ...

};

// Wskazówka: funkcja oblicza nwd( a, b ) algorytmem Euklidesa.
int nwd( int a, int b )
{

if ( a < b )
{

return nwd( b, a );

}
while ( b > 0 )
{

int r = a % b;
a = b;
b = r;

}
return a;

}

Zad. 70.

Korzystając z podanego poniżej schematu napisz klasę Z17 re-

prezentującą liczby całkowite będące resztami z dzielenia przez 17, tzn. nale-
żące do zbioru

{0, 1, 2, . . . , 15, 16}. Zdefiniuj operator * odpowiadający mno-

żeniu w tym zbiorze. Dla a i b

∈ {0, . . . , 16} wartością mnożenia * jest

(a

·b) mod 17. Korzystając z tej klasy napisz program kalkulator obliczający

iloczyn dwóch liczb o wartościach odczytanych w czasie działania programu.

class Z17
{

19

background image

public:

// Konstruktor nadaje obiektowi początkową wartość równą reszcie
// z dzielenia i przez 17. Dla jednoznaczności przyjmujemy, że reszta
// jest nieujemna.
Z17( int i );
// Operator * oblicza iloczyn dwóch swoich argumentów.
Z17 operator*( const Z17& i );
// Funkcja wypisz wypisuje do standardowego strumienia cout
// liczbę będącą wartością obiektu.
void wypisz();

// Ewentualne dalsze składowe klasy potrzebne do konstrukcji.
// ...

};

Zad. 71.

Napisz klasę Figura reprezentującą abstrakcyjną figurę geome-

tryczną i umożliwiającą obliczenie jej obwodu i pola powierzchni

class Figura
{

public:

virtual double obwod()=0;
virtual double pole()=0;
virtual string nazwa()=0;

};

a następnie zdefiniuj klasy pochodne Trojkat, Kwadrat i Kolo odpowiadające
odpowiednio trójkątowi równobocznemu i kwadratowi o długości boku x oraz
kołu o średnicy długości x. Wartość x powinna być argumentem konstruktora.

Następnie napisz funkcję

void suma( vector< Figura* > v );

obliczającą i wypisującą na ekranie sumę obwodów i pól powierzchni wszyst-
kich figur będących elementami wektora v.

Wykonaj obliczenia dla 10 losowo utworzonych figur geometrycznych.

20

background image

Rozwiązania zadań

Zad. 1.

% g++ -o hello hello.cc
% ./hello
Programowanie w C++ jest proste i przyjemne!
%

Zad. 2.

% g++ -c hello.cc
% g++ -o hello hello.o
% ./hello
Programowanie w C++ jest proste i przyjemne!
%

Zad. 3.

% g++ -c hellobis.cc
% g++ -c pisz.cc
% g++ -o hellobis hellobis.o pisz.o
% ./hellobis
Hello world
%

Zad. 4.

a)

% g++ -o hello hello.cc
% ldd hello
linux-gate.so.1 =>

(0xffffe000)

libstdc++.so.6 => /usr/lib/libstdc++.so.6 (0x4001d000)
libm.so.6 => /lib/tls/libm.so.6 (0x400fe000)
libgcc_s.so.1 => /lib/libgcc_s.so.1 (0x40125000)
libc.so.6 => /lib/tls/libc.so.6 (0x40130000)
/lib/ld-linux.so.2 (0x40000000)

b)

% g++ -static -o hello hello.cc
% ldd hello
not a dynamic executable

21

background image

Zad. 5.

.PHONY: all
all: hello hellobis

hello: hello.cc

g++ -o hello hello.cc

hellobis: hellobis.cc pisz.cc pisz.h

g++ -c hellobis.cc
g++ -c pisz.cc
g++ -o hellobis hellobis.o pisz.o

.PHONY: clean
clean:

rm -f *.o hello hellobis

Zad. 6.

%.o: %.c

gcc -c -o $@ $<

%.o: %.cc

g++ -c -o $@ $<

%: %.o

g++ -o $@ $^

.PHONY: all
all: hello hellobis

hello: hello.o

hellobis: hellobis.o pisz.o

Zad. 7.

CCFLAGS += -g
CXXFLAGS += -g

.PHONY: all
all: hello hellobis

hello: hello.o

$(CXX) -o $@ $<

hellobis: hellobis.o pisz.o

$(CXX) -o $@ $^

22

background image

Zad. 8.

1.

sprawozdanie.dvi: sprawozdanie.tex

latex sprawozdanie.tex
latex sprawozdanie.tex

sprawozdanie.ps: sprawozdanie.dvi

dvips -o sprawozdanie.ps sprawozdanie.dvi

sprawozdanie.pdf: sprawozdanie.tex

pdflatex sprawozdanie.tex
pdflatex sprawozdanie.tex

2.

%.dvi: %.tex

latex $<
latex $<

%.ps: %.dvi

dvips -o $@ $<

%.pdf: %.tex

pdflatex $<
pdflatex $<

Zad. 9.

% g++ -O0 -o pierwsze pierwsze.cc
% time pierwsze > /dev/null
7.900u 0.000s 0:07.90 100.0%

0+0k 0+0io 265pf+0w

% g++ -O2 -o pierwsze pierwsze.cc
% time pierwsze > /dev/null
7.490u 0.000s 0:07.49 100.0%

0+0k 0+0io 268pf+0w

Zad. 12.

// Program wypisuje kolejne potęgi liczby pi z zadaną dokładnością
// korzystając z biblioteki języka C.
//
// Paweł Klimczewski, 10 października 2005

#include <cstdio>
#include <cmath>

int main()
{

printf("potęga wartość\n"

"----------------\n");

printf("1

%5.1f\n",M_PI);

printf("2

%6.2f\n",M_PI*M_PI);

23

background image

printf("3

%7.3f\n",M_PI*M_PI*M_PI);

printf("4

%8.4f\n",M_PI*M_PI*M_PI*M_PI);

printf("5

%9.5f\n",M_PI*M_PI*M_PI*M_PI*M_PI);

return 0;

}

// Program wypisuje kolejne potęgi liczby pi z zadaną dokładnością
// korzystając z biblioteki języka C++.
//
// Paweł Klimczewski, 10 października 2005

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{

cout<<"potęga wartość"<<endl;
cout<<"-----------------"<<endl<<fixed;
cout<<"1

"<<setw(5)<<setprecision(1)<<M_PI<<endl;

cout<<"2

"<<setw(6)<<setprecision(2)<<M_PI*M_PI<<endl;

cout<<"3

"<<setw(7)<<setprecision(3)<<M_PI*M_PI*M_PI<<endl;

cout<<"4

"<<setw(8)<<setprecision(4)<<M_PI*M_PI*M_PI*M_PI<<endl;

cout<<"5

"

<<setprecision(5)<<M_PI*M_PI*M_PI*M_PI*M_PI<<endl;

return 0;

}

Zad. 13.

// Program odczytuje dwie liczby i wypisuje ich iloraz i sumę.
// Wersja w stylu C++.
//
// Paweł Klimczewski, 10 października 2005

#include <iostream>

using namespace std;

int main()
{

cout<<"Podaj pierwszą liczbę"<<endl;
int i;
cin>>i;
cout<<"Podaj drugą liczbę"<<endl;
int j;
cin>>j;
cout<<"Pierwsza odczytana liczba "<<i<<endl;

24

background image

cout<<"Druga odczytana liczba "<<j<<endl;
cout<<"Iloraz "<<i/j<<endl;
cout<<"Suma "<<i+j<<endl;
return 0;

}

// Program odczytuje dwie liczby i wypisuje ich iloraz i sumę.
// Wersja w stylu C.
//
// Paweł Klimczewski, 10 października 2005

#include <cstdio>

int main()
{

printf("Podaj pierwszą liczbę\n");
int i;
scanf("%d",&i);
printf("Podaj drugą liczbę\n");
int j;
scanf("%d",&j);
printf("Pierwsza odczytana liczba %d\n",i);
printf("Druga odczytana liczba %d\n",j);
printf("Iloraz %d\n",i/j);
printf("Suma %d\n",i+j);
return 0;

}

Zad. 14.

a)

// Program oblicza zadłużenie wobec barku wydziałowego na podstawie rachunku
// nadesłanego w pliku;)
//
// Paweł Klimczewski, 10 października 2005

#include <cstdio>

int main()
{

double cena1;
scanf("%*[A-Za-z ]:%lf\n",&cena1);
double cena2;
scanf("%*[A-Za-z ]:%lf\n",&cena2);
double cena3;
scanf("%*[A-Za-z ]:%lf\n",&cena3);
printf("%.2f+%.2f+%.2f=%.2f\n",cena1,cena2,cena3,cena1+cena2+cena3);
return 0;

}

25

background image

b)

// Program oblicza zadłużenie wobec barku wydziałowego na podstawie rachunku
// nadesłanego w pliku;)
//
// Paweł Klimczewski, 23 października 2006

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>

using namespace std;

int main()
{

string s;
getline( cin, s );
istringstream is1( s.substr( s.rfind( ’:’ ) + 1 ) );
double cena1;
is1 >> cena1;

getline( cin, s );
istringstream is2( s.substr( s.rfind( ’:’ ) + 1 ) );
double cena2;
is2 >> cena2;

getline( cin, s );
istringstream is3( s.substr( s.rfind( ’:’ ) + 1 ) );
double cena3;
is3 >> cena3;

cout

<< fixed << setprecision( 2 )
<< cena1 << "+" << cena2 << "+" << cena3 << "="
<< cena1 + cena2 + cena3 << endl;

return 0;

}

Zad. 15.

// Program zamienia miejscami liczby zapisane w pliku 2pi.txt.
//
// Paweł Klimczewski, 10 października 2005

#include <fstream>
#include <string>

using namespace std;

int main()

26

background image

{

fstream f("2pi.txt");
string s1, s2;
f>>s1>>s2;
f.seekp(0,ios::beg);
f<<s2<<endl<<s1<<endl;
return 0;

}

Zad. 16.

// Program wypisuje rozmiary zmiennych podstawowych typów.
//
// Paweł Klimczewski, 8 października 2006

#include <iostream>

using namespace std;

int main()
{

enum kolor { czerwony, bialy, niebieski };
cout

<< "sizeof( char ) = " << sizeof( char ) << endl
<< "sizeof( short int ) = " << sizeof( short int ) << endl
<< "sizeof( int ) = " << sizeof( int ) << endl
<< "sizeof( long int ) = " << sizeof( long int ) << endl
<< "sizeof( float ) = " << sizeof( float ) << endl
<< "sizeof( double ) = " << sizeof( double ) << endl
<< "sizeof( bool ) = " << sizeof( bool ) << endl
<< "sizeof( enum ) = " << sizeof( kolor ) << endl
<< "sizeof( char* ) = " << sizeof( char* ) << endl;

return 0;

}

Zad. 17.

// Program sprawdza liczbę cyfr znaczących dla zmiennych typu float, double
// i long double.
//
// Paweł Klimczewski, 19 października 2005

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()

27

background image

{

// dla łatwiejszego porównania wyników
cout << setprecision( 40 );

// float
cout << "-----

float" << endl;

float fsuma = 0, poprzednia_fsuma;
int i = 0;
do
{

poprzednia_fsuma = fsuma;
fsuma = fsuma + pow( 10.f, -i );
i = i + 1;
cout << setw( 2 ) << i << ": " << fsuma << endl;

}
while ( poprzednia_fsuma != fsuma );

// double
cout << "-----

double" << endl;

double dsuma = 0, poprzednia_dsuma;
i = 0;
do
{

poprzednia_dsuma = dsuma;
dsuma = dsuma + pow( 10., -i );
i = i + 1;
cout << setw( 2 ) << i << ": " << dsuma << endl;

}
while ( poprzednia_dsuma != dsuma );

// long double
cout << "-----

long double" << endl;

long double ldsuma = 0, poprzednia_ldsuma;
i = 0;
do
{

poprzednia_ldsuma = ldsuma;
ldsuma = ldsuma + pow( 10.l, -i );
i = i + 1;
cout << setw( 2 ) << i << ": " << ldsuma << endl;

}
while ( poprzednia_ldsuma != ldsuma );

return 0;

}

Zad. 18.

// Program oblicza sumę odwrotności kwadratów z zakresu 1...10^8 posługując
// się zmiennymi typu float, double i long double.

28

background image

//
// Paweł Klimczewski, 19 października 2005

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{

cout << setprecision( 40 ); // dla łatwiejszego porównania wyników

// float, od 1 w górę
float fsuma = 0;
for ( int i = 1; i <= 100000000; ++i )
{

float f = i;
fsuma = fsuma + 1.f / f / f;

}
cout << fsuma << endl;

// float, od 10^8 w dół
fsuma = 0;
for ( int i = 100000000; i >= 1; --i )
{

float f = i;
fsuma = fsuma + 1.f / f / f;

}
cout << fsuma << endl;

// double, od 1 w górę
double dsuma = 0;
for ( int i = 1; i <= 100000000; ++i )
{

double d = i;
dsuma = dsuma + 1. / d / d;

}
cout << dsuma << endl;

// double, od 10^8 w dół
dsuma = 0;
for ( int i = 100000000; i >= 1; --i )
{

double d = i;
dsuma = dsuma + 1. / d / d;

}
cout << dsuma << endl;

29

background image

// long double, od 1 w górę
long double ldsuma = 0;
for ( int i = 1; i <= 100000000; ++i )
{

long double ld = i;
ldsuma = ldsuma + 1.l / ld / ld;

}
cout << ldsuma << endl;

// long double, od 10^8 w dół
ldsuma = 0;
for ( int i = 100000000; i >= 1; --i )
{

long double ld = i;
ldsuma = ldsuma + 1.l / ld / ld;

}
cout << ldsuma << endl;

// suma szeregu nieskończonego
cout << M_PI * M_PI / 6 << endl;

return 0;

}

Zad. 19.

// Program zamienia kolejność znaków w pliku.
//
// Paweł Klimczewski, 4 listopada 2005

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main()
{

cout << "Podaj nazwę pliku" << endl;
string nazwa;
cin >> nazwa;
fstream f( nazwa.c_str() );
f.seekg( 0, ios::end );
int n = f.tellg();
for ( int i = 0; i < n / 2; ++i )
{

f.seekg( i, ios::beg );
char c1 = f.get();
f.seekg( -( i + 1 ), ios::end );

30

background image

char c2 = f.get();
f.seekp( i, ios::beg );
f.put( c2 );
f.seekp( -( i + 1 ), ios::end );
f.put( c1 );

}
return 0;

}

Zad. 20.

// Program wypisuje w kolejnych wierszach coraz dokładniejszą wartość
// liczby pi.
//
// Paweł Klimczewski, 4 listopada 2005

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{

cout << "Podaj liczbę wierszy" << endl;
int i;
cin >> i;
if ( !cin || i <= 0 || i > 9 )
{

cout << "Nierozsądna odpowiedź" << endl;

}
else
{

for ( int j = 0; j < i; ++j )
{

cout << setprecision( 1 + j ) << fixed << M_PI << endl;

}

}
return 0;

}

Zad. 21.

// Program wypisuje w kolejnych wierszach coraz dokładniejszą wartość
// kolejnej potęgi liczby pi.
//
// Paweł Klimczewski, 4 listopada 2005

#include <iostream>

31

background image

#include <iomanip>
#include <cmath>

using namespace std;

int main()
{

cout << "Podaj liczbę wierszy" << endl;
int i;
cin >> i;
if ( !cin || i <= 0 || i > 9 )
{

cout << "Nierozsądna odpowiedź" << endl;

}
else
{

cout << "potęga

wartość" << endl

<< "-------------------------" << endl;

for ( int j = 0; j < i; ++j )
{

double potega = pow( M_PI, j + 1 );
int cyfr = int( log10( potega ) );
cout << setw( 10 - cyfr ) << left << j + 1

<< setprecision( j + 1 ) << fixed << potega
<< endl;

}

}
return 0;

}

Zad. 22.

// Program rysuje kwadrat z przekątną.
//
// Paweł Klimczewski, 4 listopada 2005

#include <iostream>

using namespace std;

int main()
{

cout << "Podaj rozmiar kwadratu" << endl;
int n;
cin >> n;
if ( !cin || n <= 0 || n > 20 )
{

cout << "Niepoprawne dane!" << endl;

}

32

background image

else
{

for ( int y = 0; y < n; ++y )
{

for ( int x = 0; x < n; ++x )
{

char znak = ’ ’;
if ( !x || !y || x == n - 1 || y == n - 1 || x == y )
{

znak = ’*’;

}
cout << znak;

}
cout << endl;

}

}
return 0;

}

// Program rysuje tabelkę.
//
// Paweł Klimczewski, 4 listopada 2005

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{

const int n = 4;
for ( int y = 0; y < n; ++y )
{

cout << "---------------------" << endl;
for ( int x = 0; x < n; ++x )
{

cout << "| " << setw(2) << ( x + 1 ) * ( y + 1 ) << " ";

}
cout << "|" << endl;

}
cout << "---------------------" << endl;
return 0;

}

Zad. 23.

// Program oblicza liczbę odczytanych słów i średnią długość słowa
//
// Paweł Klimczewski, 4 listopada 2005

33

background image

#include <iostream>
#include <string>

using namespace std;

int main()
{

int n = 0, znakow = 0;
string s;
while ( cin >> s )
{

++n;
znakow += s.size();

}
cout << "Liczba słów: " << n << endl

<< "Średnia długość słowa: " << 1. * znakow / n << endl;

return 0;

}

Zad. 24.

// Program stara się naśladować systemowe polecenie wc.
//
// Paweł Klimczewski, 4 listopada 2005

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{

int wierszy = 0, slow = 0, znakow = 0;
string s;
while ( getline( cin, s ) )
{

++wierszy;
istringstream is( s );
while ( is >> s )
{

++slow;
znakow += s.size();

}

}
cout

<< "Wierszy " << wierszy
<< ", słów " << slow

34

background image

<< ", znaków " << znakow << endl;

return 0;

}

Zad. 25.

// Program wypisuje wartość podanej liczby w postaci c*2^m.
//
// Paweł Klimczewski, 11 listopada 2005

#include <iostream>
#include <iomanip>
#include <sstream>
#include <cmath>

using namespace std;

// Odczytanie wartości na podstawie napisu p wraz ze sprawdzeniem
// zapisuję w osobnej funkcji.
template <class T>
void czytaj_z_napisu( T& x, const char* p )
{

if ( !p )
{

cerr << "Należy podać liczbę!" << endl;
exit( 1 );

}
istringstream is( p );
is >> x;
if ( !is )
{

cerr << "To nie jest liczba!" << endl;
exit( 1 );

}
int i = is.tellg();
is.seekg( 0, ios::end );
int j = is.tellg();
if ( i != j )
{

// np. 1x lub 1.2.3 itd.
cerr << "W danej jest coś więcej niż liczba!" << endl;
exit( 1 );

}

}

int main( int argc, char* argv[] )
{

double x;
czytaj_z_napisu( x, argc < 2 ? NULL : argv[ 1 ] );

35

background image

int m;
double c = frexp( x, &m );
cout << fixed << setprecision( 16 ) << c << "*2^" << m << endl;
return 0;

}

Zad. 26.

// Program odczytuje podaną wartość x=c*2^m, a następnie konstruuje liczbę
// c*2^(m/2).
//
// Paweł Klimczewski, 11 listopada 2005

#include <iostream>
#include <iomanip>
#include <cmath>
#include "czytaj.h"

using namespace std;

int main( int argc, char* argv[] )
{

// Dla odczytania wartości podanej przez użytkownika korzystam
// z funkcji czytaj_double z programu rzeczywista.
double x;
czytaj_z_napisu( x, argc < 2 ? NULL : argv[ 1 ] );
int m;
double c = frexp( x, &m );
m >>= 1;
x = ldexp( c, m );
cout << fixed << setprecision( 16 ) << x << endl;
return 0;

}

Zad. 27.

// Program oblicza pierwiastek zadanej liczby metodą Newtona.
//
// Paweł Klimczewski, 11 listopada 2005

#include <iostream>
#include <iomanip>
#include <cmath>
#include "czytaj.h"

using namespace std;

int main( int argc, char* argv[] )
{

36

background image

// Odczytuję liczbę pierwiastkowaną x. Korzystam z funkcji
// czytaj_z_napisu z programu rzeczywista.
double x ;
czytaj_z_napisu( x, argc < 2 ? NULL : argv[ 1 ] );
// Obliczam początkowe przybliżenie pierwiastka.
int m;
double c = frexp( x, &m );
m >>= 1;
double p = ldexp( c, m );
cout << "Kandydat na wartość pierwiastka = " << p << endl;
cout << "Kolejne iteracje" << endl;
cout << left << scientific << setprecision( 16 );
// Iteracyjnie znajduję piewiastek.
for ( int i = 1; ; ++i )
{

double q = 1. / 2 * ( p + x / p );
if ( p == q )
{

// Iteracja nie przyniosła zmian. Przerywam pętlę.
break;

}
cout << setw( 6 ) << i << q << endl;
p = q;

}
return 0;

}

Zad. 28.

// Program oblicza dzień tygodnia.
//
// Paweł Klimczewski, 11 listopada 2005

#include <iostream>
#include <iomanip>
#include <sstream>
#include <cmath>

using namespace std;

// Zadaniem funkcji jest odczytanie ze strumienia cin liczby
// i odpowiednie reagowanie na ewentualne błędy. System operacyjny przesyła
// do programu całe wprowadzone wiersze w momencie naciśnięcia klawisza Enter.
template <class T>
void czytaj_z_wejscia( T& x, const char* p = "Podaj liczbę" )
{

while ( true )
{

cout << p << endl;

37

background image

string s;
getline( cin, s );
if ( !cin )
{

if ( cin.eof() )
{

cerr << "Koniec danych?! Kończę pracę programu!" << endl;
exit( 1 );

}
cerr << "Błąd przy czytaniu wiersza!" << endl;
cin.clear();
continue;

}
istringstream is( s );
is >> x;
if ( !is )
{

cerr << "To nie była liczba!" << endl;
continue;

}
is >> ws;
int j = is.tellg();
if ( j != -1 && j != s.size() )
{

cerr << "To nie była tylko liczba!" << endl;
continue;

}
break;

}

}

int main()
{

int r;
czytaj_z_wejscia( r, "Podaj rok" );
int m;
czytaj_z_wejscia( m, "Podaj miesiąc" );
int d;
czytaj_z_wejscia( d, "Podaj dzień" );
if ( m < 3 )
{

m += 10;
r -= 1;

}
else
{

m -= 2;

}
int n = r / 4 - r / 100 + r / 400 + 367 * m / 12 + d + r * 365;

38

background image

const char* dni_tygodnia[]=
{

"niedziela", "poniedziałek", "wtorek", "środa", "czwartek",
"piątek", "sobota"

};
cout << "To jest " << dni_tygodnia[ n % 7 ] << "." << endl;
return 0;

}

Zad. 29.

// Program oblicza wielkość podatku na podstawie podanego dochodu. zgodnie
// ze skalą z 2005 roku.
//
// Paweł Klimczewski, 13 listopada 2005

#include <iostream>
#include "czytaj.h"

using namespace std;

int main( int argc, char* argv[] )
{

double podstawa;
czytaj_z_napisu( podstawa, argc < 2 ? NULL : argv[ 1 ] );
double progi[] =
{

600000

, 50,

74048

, 40,

37024

, 30,

int( 530.08 / 0.19 * 100 + 0.5 ) / 100., 19,
0

};
double podatek = 0;
for ( int i = 0; progi[ i ]; i += 2 )
{

if ( podstawa > progi[ i ] )
{

podatek += ( podstawa - progi[ i ] ) * progi[ i + 1 ] / 100.;
podstawa = progi[ i ];

}

}
cout << "Należny podatek wynosi " << int( podatek + 0.5 ) << " zł" << endl;
return 0;

}

39

background image

Zad. 30.

// Program oblicza liczbę dni jakie upłynęły od zadanej daty.
//
// Paweł Klimczewski, 11 listopada 2005

#include <iostream>
#include <ctime>
#include "czytaj.h"

using namespace std;

int main()
{

int r;
czytaj_z_wejscia( r, "Podaj rok" );
int m;
czytaj_z_wejscia( m, "Podaj miesiąc" );
int d;
czytaj_z_wejscia( d, "Podaj dzień" );
// Konwersja podanej daty do postaci wymaganej we wzorze Gaussa, czyli
// rok zaczyna się w marcu.
if ( m > 2 )
{

m = m - 2;

}
else
{

m = m + 10;
r = r - 1;

}

// Obliczamy numer podanego dnia ze wzoru Gaussa.
int t = r / 4 - r / 100 + r / 400 + 367 * m / 12 + d + r * 365;

// 1 stycznia 1970 odpowiada we wzorze Gaussa dacie 1 listopada 1969.
// Obliczamy numer tego dnia.
int t0 = 1969 / 4 - 1969 / 100 + 1969 / 400 + 367 * 11 / 12 + 1 + 1969 * 365;

// Zatem od 1 stycznia 1970 do podanego dnia upłynelo t - t0 dni.
// Z drugiej strony funkcja time podaje liczbę sekund jakie upłynęły
// od 1 stycznia 1970 roku od godziny 0.00 do chwili obecnej.
// Razem upłynęło:
int n = t0 - t + time( NULL ) / 3600 / 24;

if ( n > 0 )
{

cout << "Żyjesz już " << n << " dni." << endl;

40

background image

if ( n % 1000 == 0 )
{

cout << "Dziś masz mały jubileusz!" << endl;

}
else
{

long p = 1000 - n % 1000;
if ( p == 1 )
{

cout << "Jutro masz mały jubileusz!" << endl;

}
else if ( p == 2 )
{

cout << "Pojutrze masz mały jubileusz!" << endl;

}
else
{

cout << "Do najblizszej 1000-nicy zostalo Ci " << p << " dni." << endl;

}

}

}
else
{

cout << "Na pewno już się urodziłeś?" << endl;

}
return 0;

}

Zad. 31.

// Program oblicza silnię zadanej liczby oraz ilość cyfr 7 w jej zapisie.
//
// Paweł Klimczewski, 11 listopada 2005

#include <iostream>
#include <sstream>
#include <cmath>
#include "czytaj.h"

using namespace std;

int silnia( int n )
{

return n > 1 ? n * silnia( n - 1 ) : 1;

}

int main()
{

// Dla odczytania wartości podanej przez użytkownika korzystam

41

background image

// z funkcji czytaj_z_wejscia z programu rzeczywista.
int x;
czytaj_z_wejscia( x );
int s = silnia( x );
ostringstream os;
os << s;
string t = os.str();
int n = 0;
for ( int i = 0; i < t.size(); ++i )
{

if ( t[ i ] == ’7’ ) ++n;

}
cout << x << "!=" << s << endl;
cout << "Liczba siódemek w zapisie = " << n << endl;
return 0;

}

Zad. 32.

// Program znajduje wszystkie liczby całkowite z zakresu 1..1000 podzielne
// przez sumę swoich cyfr.
//
// Paweł Klimczewski, 13 listopada 2005

#include <iostream>
#include <sstream>

using namespace std;

int main()
{

for ( int i = 1; i <= 1000; ++i )
{

ostringstream os;
os << i;
const string& s = os.str();
int suma = 0;
for ( int j = 0; j < s.size(); ++j )
{

suma += s[ j ] - ’0’;

}
if ( i % suma == 0 ) cout << i << " ";

}
cout << endl;
return 0;

}

42

background image

Zad. 33.

// Program znajduje wszystkie liczby całkowite z zakresu 1..1000 podzielne
// jednocześnie przez sumy swoich parzystych i nieparzystych cyfr.
//
// Paweł Klimczewski, 13 listopada 2005

#include <iostream>
#include <sstream>

using namespace std;

int main()
{

for ( int i = 1; i <= 1000; ++i )
{

ostringstream os;
os << i;
const string& s = os.str();
int suma_p = 0, suma_n = 0;
for ( int j = 0; j < s.size(); ++j )
{

int c = s[ j ] - ’0’;
( c % 2 ? suma_n : suma_p ) += c;

}
if ( suma_p && i % suma_p == 0 &&

suma_n && i % suma_n == 0 )

cout << i << " ";

}
cout << endl;
return 0;

}

Zad. 34.

// Program szyfruje dane stosując szyfr cezara.
//
// Paweł Klimczewski, 13 listopada 2005

#include <iostream>
#include "czytaj.h"

using namespace std;

int main( int argc, char* argv[] )
{

int n;
czytaj_z_napisu( n, argc < 2 ? NULL : argv[ 1 ] );
if ( n < 0 || n >= 26 )

43

background image

{

cerr << "Wartość parametru powinna należeć do zakresu 0..25!" << endl;
return 1;

}
while ( true )
{

int znak = cin.get();
if ( znak < 0 ) break; // koniec danych
if ( znak >= ’a’ && znak <= ’z’ )

znak = ( znak - ’a’ + n ) % 26 + ’a’;

else if ( znak >= ’A’ && znak <= ’Z’ )

znak = ( znak - ’A’ + n ) % 26 + ’A’;

cout.put( znak );

}
return 0;

}

Zad. 35.

// Program oblicza wartość wielomianu
//
//

w( x ) = 100 x^3 - 625 x^2 + 1183.19 x - 660.489

//
// w zadanym punkcie.
//
// Paweł Klimczewski, 13 listopada 2005

#include <iostream>
#include <iomanip>
#include <cmath>
#include "czytaj.h"

using namespace std;

double w1( double x )
{

return 100 * x * x * x - 625 * x * x + 1183.19 * x - 660.489;

}

double w2( double x )
{

return ( ( 100 * x - 625 ) * x + 1183.19 ) * x - 660.489;

}

double w3( double x )
{

return 100 * pow( x, 3 ) - 625 * pow( x, 2 ) + 1183.19 * x - 660.489;

}

44

background image

int main( int argc, char* argv[] )
{

double x;
czytaj_z_napisu( x, argc < 2 ? NULL : argv[ 1 ] );
cout

<< scientific << setprecision( 16 )
<< "w(" << x << ")=" << endl
<< w1( x ) << endl
<< w2( x ) << endl
<< w3( x ) << endl;

return 0;

}

Zad. 36.

// Program oblicza miejsca zerowe wielomianu
//
//

w( x ) = 100 x^3 - 625 x^2 + 1183.19 x - 660.489

//
// metodą bisekcji.
//
// Paweł Klimczewski, 13 listopada 2005

#include <iostream>
#include <iomanip>
#include <cmath>
#include "czytaj.h"

using namespace std;

double w1( double x )
{

return 100 * x * x * x - 625 * x * x + 1183.19 * x - 660.489;

}

double w2( double x )
{

return ( ( 100 * x - 625 ) * x + 1183.19 ) * x - 660.489;

}

double w3( double x )
{

return 100 * ( x - 3.19 ) * ( x - 2.05 ) * ( x - 1.01 );

}

double w4( double x )
{

return 100 * pow( x, 3 ) - 625 * pow( x, 2 ) + 1183.19 * x - 660.489;

}

45

background image

// Aby porównać miejsca zerowe znalezione dla różnych funkcji obliczających
// wartość wielomianu w punkcie, metodę bisekcji zapisuję w osobnej funkcji.
void bisekcja( double x1, double x2, double (*w)(double) )
{

double y1 = w( x1 ), y2 = w( x2 );
if ( y1 * y2 == 0 )
{

cout << "Masz szczęście - podałeś miejsce zerowe!" << endl;
return;

}
if ( y1 * y2 > 0 )
{

cout << "W obu punktach w(x) ma ten sam znak!. Spróbuj ponownie." << endl;
return;

}
if ( x1 > x2 )
{

double tmp = x1;
x1 = x2;
x2 = tmp;

}
while ( true )
{

double xs = ( x1 + x2 ) / 2, ys = w( xs );
if ( ys == 0 || xs == x1 || xs == x2 )
{

cout << "x = " << xs << ", w(x) = " << ys << endl;
break;

}
if ( ys * y1 > 0 )
{

x1 = xs;

}
else
{

x2 = xs;

}

}

}

int main( int argc, char* argv[] )
{

double x1;
czytaj_z_napisu( x1, argc < 3 ? NULL : argv[ 1 ] );
double x2;
czytaj_z_napisu( x2, argc < 3 ? NULL : argv[ 2 ] );
cout << scientific << setprecision( 16 );
bisekcja( x1, x2, w1 );

46

background image

bisekcja( x1, x2, w2 );
bisekcja( x1, x2, w3 );
bisekcja( x1, x2, w4 );
return 0;

}

Zad. 37.

// Program oblicza miejsca zerowe wielomianu
//
//

w( x ) = 100 x^3 - 625 x^2 + 1183.19 x - 660.489

//
// metodą stycznych.
//
// Paweł Klimczewski, 13 listopada 2005

#include <iostream>
#include <iomanip>
#include <cmath>
#include "czytaj.h"

using namespace std;

double w( double x )
{

return 100 * x * x * x - 625 * x * x + 1183.19 * x - 660.489;

}

double dw( double x )
{

return 300 * x * x - 1250 * x + 1183.19;

}

int main( int argc, char* argv[] )
{

double x;
czytaj_z_napisu( x, argc < 2 ? NULL : argv[ 1 ] );
cout << scientific << setprecision( 16 );
const double EPSILON = 1e-15;
while ( true )
{

cout << "w(" << x << ") = " << w( x ) << endl;
double lepsze_x = x - w( x ) / dw( x );
if ( abs( x - lepsze_x ) < EPSILON )

break;

x = lepsze_x;

}
return 0;

}

47

background image

Zad. 38.

// Program oblicza silnię i wyraz ciągu Fibonacciego iteracyjnie
// i rekurencyjnie.
//
// Paweł Klimczewski, 11 listopada 2005

#include <iostream>
#include <sys/time.h>
#include <unistd.h>
#include "czytaj.h"

using namespace std;

int silnia_r( int n )
{

return n > 1 ? n * silnia_r( n - 1 ) : 1;

}

int silnia_i( int n )
{

int iloczyn = 1;
for ( ; n > 1; --n )
{

iloczyn *= n;

}
return iloczyn;

}

int fib_r( int n )
{

return n > 1 ? fib_r( n - 1 ) + fib_r( n - 2 ) : 1;

}

int fib_i( int n )
{

int poprzedni = 1, biezacy = 1;
for ( ; n >= 2; --n )
{

int nastepny = biezacy + poprzedni;
poprzedni = biezacy;
biezacy = nastepny;

}
return biezacy;

}

// Funkcja przekazuje aktualny czas w mikrosekundach. W tym celu korzystam
// z funkcji systemowej gettimeofday.
unsigned int t()
{

48

background image

timeval tv;
gettimeofday( &tv, NULL );
return tv.tv_sec * 1000000 + tv.tv_usec;

}

int main()
{

// Dla odczytania wartości podanej przez użytkownika korzystam
// z funkcji czytaj_z_wejscia z programu rzeczywista.
int x;
czytaj_z_wejscia( x );

cout << "Silnia iteracyjnie" << endl;
unsigned int t0 = t();
int i = silnia_i( x );
unsigned int t1 = t();
cout << i << ", " << t1 - t0 << endl;

cout << "Silnia rekurencyjnie" << endl;
t0 = t();
i = silnia_r( x );
t1 = t();
cout << i << ", " << t1 - t0 << endl;

cout << "Wyraz ciągu Fibonacciego iteracyjnie" << endl;
t0 = t();
i = fib_i( x );
t1 = t();
cout << i << ", " << t1 - t0 << endl;

cout << "Wyraz ciągu Fibonacciego rekurencyjnie" << endl;
t0 = t();
i = fib_r( x );
t1 = t();
cout << i << ", " << t1 - t0 << endl;

return 0;

}

Zad. 39.

// Program znajduje największy wspólny dzielnik metodą Euklidesa.
//
// Paweł Klimczewski, 11 listopada 2005

#include <iostream>
#include "czytaj.h"

using namespace std;

49

background image

// iteracyjnie
int nwd1( int a, int b )
{

while ( b )
{

int r = a % b;
a = b;
b = r;

}
return a;

}

// rekurencyjnie
int nwd2( int a, int b )
{

if ( b != 0 )

return nwd2( b, a % b );

else

return a;

}

int main()
{

int a;
czytaj_z_wejscia( a, "Podaj pierwszą liczbę" );
int b;
czytaj_z_wejscia( b, "Podaj drugą liczbę" );
cout

<< "NWD( " << a << ", " << b << " ) = "
<< nwd1( a, b ) << " = "
<< nwd2( a, b ) << endl;

return 0;

}

Zad. 40.

// Program oblicza miejsca zerowe wielomianu
//
//

w( x ) = (x-1)(x-2)(x-3)(x-4)

//
// metodą stycznych.
//
// Paweł Klimczewski, 13 listopada 2005

#include <iostream>
#include <iomanip>
#include <cmath>

50

background image

#include <complex>
#include "czytaj.h"

using namespace std;

complex<double> w( complex<double> x )
{

return ( x - 1. ) * ( x - 2. ) * ( x - 3. ) * ( x - 4. );

}

complex<double> dw( complex<double> x )
{

// [ ( x - 1 ) ( x - 2 ) ( x - 3 ) ( x - 4 ) ]’ =
// = [ x^4 - 10 x^3 + 35 x^2 - 50 x + 24 ]’ =
// = 4 x^3 - 30 x^2 + 70 x - 50 = ( ( 4 x - 30 ) x + 70 ) x - 50
return ( ( 4. * x - 30. ) * x + 70. ) * x - 50.;

}

int main( int argc, char* argv[] )
{

complex<double> x;
czytaj_z_napisu( x, argc < 2 ? NULL : argv[ 1 ] );
cout << scientific << setprecision( 16 );
const double EPSILON = 1e-15;
while ( true )
{

cout << "w(" << x << ") = " << w( x ) << endl;
complex<double> lepsze_x = x - w( x ) / dw( x );
if ( norm( x - lepsze_x ) < EPSILON )

break;

x = lepsze_x;

}
return 0;

}

Zad. 41.

a)

// Program przetwarza wyniki pomiarow meteorologicznych przepisujac dla
// kazdego pomiaru jedynie czas i temperature.
//
// Pawel Klimczewski, 22 pazdziernika 2006

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()

51

background image

{

while ( true )
{

string wiersz;
getline( cin, wiersz );
if ( !cin ) break;
istringstream is( wiersz );
int czas;
is >> czas;
int temp;
is >> temp;
cout << czas << " " << temp << endl;

}
return 0;

}

b)

// Program przetwarza wyniki pomiarow meteorologicznych przepisujac dla
// kazdego pomiaru jedynie czas i temperature oraz pomijajac wiersze
// z blednymi wynikami pomiarow.
//
// Pawel Klimczewski, 22 pazdziernika 2006

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{

while ( true )
{

string wiersz;
getline( cin, wiersz );
if ( !cin ) break;
istringstream is( wiersz );
int czas;
is >> czas;
int temp;
is >> temp;
if ( temp == 10000 || temp == 10001 ) continue;
cout << czas << " " << temp << endl;

}
return 0;

}

c)

// Program przetwarza wyniki pomiarow meteorologicznych wypisujac informacje
// o wierszach, ktorych format danych jest niezgodny z opisem.
//

52

background image

// Pawel Klimczewski, 22 pazdziernika 2006

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{

for ( int i = 1; ; ++i )
{

string wiersz;
getline( cin, wiersz );
if ( !cin ) break;
istringstream is( wiersz );

// Obecnie rozmiar typu int wynosi 4 bajty. Mozemy zatem wykorzystac
// int do zapamietywania wynikow.
unsigned int czas;
is >> czas;
int temp;
is >> temp;
unsigned int u1, u2, u3, u4, u5, u6, u7, u8;
is >> u1 >> u2 >> u3 >> u4 >> u5 >> u6 >> u7 >> u8;
unsigned int id;
is >> id;

if ( !is )
{

cout

<< "Bledny wiersz nr " << i
<< " - nie udalo sie odczytac 11 liczb: " << wiersz << endl;

continue;

}
is >> ws;
if ( int( is.tellg() ) != wiersz.size() )
{

cout

<< "Bledny wiersz nr " << i
<< " - po 11 liczbach wystepuja dodatkowe dane: " << wiersz << endl;

continue;

}
if ( temp >= 0 &&

temp & ~0xffffu ||

temp <

0 && -temp & ~0xffffu )

{

cout

<< "Bledny wiersz nr " << i
<< " - temperatura nie jest liczba 16 bitowa: " << wiersz << endl;

53

background image

continue;

}
if ( u1 & ~0xfffu ||

u2 & ~0xfffu ||
u3 & ~0xfffu ||
u4 & ~0xfffu ||
u5 & ~0xfffu ||
u6 & ~0xfffu ||
u7 & ~0xfffu ||
u8 & ~0xfffu )

{

cout

<< "Bledny wiersz nr " << i
<< " - wartosci napiec nie sa liczbami 12 bitowymi: " << wiersz << endl;

continue;

}
if ( id & ~0xff )
{

cout

<< "Bledny wiersz nr " << i
<< " - wartosc id nie jest liczba 8 bitowa: " << wiersz << endl;

continue;

}

}
return 0;

}

Zad. 42.

// Program przetwarza wyniki pomiarow napiecia i pradu.
//
// Pawel Klimczewski, 22 pazdziernika 2006

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{

while ( true )
{

string wiersz;
getline( cin, wiersz );
if ( !cin ) break;

string u = wiersz.substr( 0, 1 ) + wiersz.substr( 2, 6 );
istringstream us( u );

54

background image

int u2;
us >> u2;

string i = wiersz[ 1 ] + wiersz.substr( 8, 4 );
istringstream is( i );
int i2;
is >> i2;

cout << u2 / 1000. << " " << i2 / 100. << endl;

}
return 0;

}

Zad. 43.

// Program oblicza częstotliwość występowania liter w tekście odczytanym
// ze standardowego strumienia danych
//
// Paweł Klimczewski, 25 listopada 2005

#include <iostream>

using namespace std;

int main()
{

int liter = 0; // licznik wszystkich znaków
// Wystąpienia poszczególnych znaków zliczam w komórkach tablicy.
// Pierwsza komórka (indeks 0) odpowiada spacji, druga literze ’a’,...,
// dwudziesta siódma literze ’z’.
int tab[ 27 ];
for ( int i = 0; i < 27; ++i )
{

tab[ i ] = 0;

}
// Odczytuję dane ze strumienia
while ( true )
{

int z = cin.get();
if ( z == -1 )

break; // koniec danych w strumieniu

if ( z == ’ ’ || ( z >= ’a’ && z <= ’z’ ) )
{

tab[ z == ’ ’ ? 0 : z - ’a’ + 1 ]++;
liter++;

}

}
// Wyniki zapisuję w na ekranie w formacie "dwukolumnowym"
for ( int i = 0; i < 27; ++i )

55

background image

{

cout << i << " " << 1. * tab[ i ] / liter << endl;

}
return 0;

}

Przy pomocy przekierowań strumieni dokonuję obliczeń (np. dla tekstu

Pana Tadeusza)

% ./litery1 < pt.txt > pt.dat

Następnie przy pomocy programu gnuplot tworzę wykres

% gnuplot

G N U P L O T
Version 4.0 patchlevel 0
last modified Thu Apr 15 14:44:22 CEST 2004
System: Linux 2.4.26

> plot "pt.dat" with boxes

Przy pomocy poleceń set xrange, set xtics itd. możemy ustalić zakres

zmiennych, opisać osie itd.

% gnuplot

G N U P L O T
Version 4.0 patchlevel 0
last modified Thu Apr 15 14:44:22 CEST 2004
System: Linux 2.4.26

> set xrange [-0.5:26.5]
> set style fill solid
> set boxwidth 0.8
> set xtics ("_" 0,"a" 1,"b" 2,"c" 3,"d" 4,"e" 5,"f" 6,"g" 7,"h" 8,"i" 9,
"j" 10,"k" 11,"l" 12,"m" 13,"n" 14,"o" 15,"p" 16,"q" 17,"r" 18,"s" 19,"t" 20,
"u" 21,"v" 22,"w" 23,"x" 24,"y" 25,"z" 26)
> plot "pt.dat" with boxes

Zad. 44.

// Program oblicza częstotliwość występowania liter w tekście
// i przygotowuje pliki z danymi oraz poleceniami dla programu gnuplot.
//
// Paweł Klimczewski, 26 listopada 2005

#include <iostream>

56

background image

#include <fstream>

using namespace std;

int n; // liczba wszystkich wykresów
double mx=0; // największa z obliczonych częstości

// Policzenie znaków zapisuję w postaci osobnej funkcji.
int policz( const string& nazwa_pliku, int numer_pliku )
{

int liter = 0; // licznik wszystkich znaków
int tab[ 27 ]; // licznik poszczególnych znaków
for ( int i = 0; i < 27; ++i )
{

tab[ i ] = 0;

}
ifstream is( nazwa_pliku.c_str() );
// Czytam znaki z pliku.
while ( true )
{

int z = is.get();
if ( z == -1 )

break; // koniec danych

if ( z == ’ ’ || ( z >= ’a’ && z <= ’z’ ) )
{

tab[ z == ’ ’ ? 0 : z - ’a’ + 1 ]++;
liter++;

}

}
// Tworzę plik z danymi dla programu gnuplot.
ofstream os( ( nazwa_pliku + ".dat" ).c_str() );
for ( int i = 0; i < 27; ++i )
{

double x = i + 0.05 + 0.9 / n * ( numer_pliku + 0.5 );
double y = 1. * tab[ i ] / liter;
if ( y > mx )

mx = y;

os << x << " " << y << endl;

}

}

int main( int argc, char* argv[] )
{

n = argc - 1;
if ( n < 1 )
{

cerr << "Podaj nazwy plików z danymi!" << endl;
return 0;

57

background image

}
for ( int i = 1; i < argc; ++i )
{

policz( argv[ i ], i - 1 );

}
ofstream skrypt( "skrypt.gp" );
skrypt

<< "set term aqua" << endl
<< "set xrange [0:27]" << endl
<< "set yrange [0:" << 1.2 * mx << "]" << endl
<< "set style fill solid" << endl
<< "set boxwidth " << 0.9/n << endl
<< "set xtics (";

for ( int i = 0; i < 27; ++i )
{

if ( i > 0 )

skrypt << ",";

skrypt << "\"" << ( i == 0 ? ’_’ : char( ’a’ + i - 1 ) ) << "\" " << i;

}
skrypt << ")" << endl;
skrypt << "plot ";
for ( int i = 1; i < argc; ++i )
{

if ( i > 1 )

skrypt << ", ";

skrypt << "\"" << argv[ i ] << ".dat\" with boxes";

}
skrypt << endl;
return 0;

}

Zad. 45.

// Program kopiuje maksymalnie zadanąliczbę znaków.
//
// Paweł Klimczewski, 26 listopada 2005

#include <iostream>
#include <sstream>

using namespace std;

int main( int argc, char* argv[] )
{

// Sprawdzam czy użytkownik podał argument.
if ( argc < 2 )
{

cerr << "Należy podać liczbę!" << endl;
return 1;

58

background image

}
// Jeżeli tak to odczytuję liczbę całkowitą.
istringstream is( argv[ 1 ] );
int n;
is >> n;
if ( !is )
{

cerr << "Błąd przy odczytaniu liczby!" << endl;
return 1;

}
// Kopiuję maksymalnie n znaków.
for ( ; n > 0; --n )
{

int z = cin.get();
if ( z == -1 )

break; // koniec danych

cout.put( z );

}
return 0;

}

Zad. 46.

// Program przygotowuje dane dla programu gnuplot dla rysunku dorzeczy
// pierwiastków równania z^n=1.
//
// Paweł Klimczewski, 26 listopada 2005

#include <iostream>
#include <sstream>
#include <complex>
#include <cmath>

using namespace std;

int n;

// stopień wielomianu: z^n - 1

int maxcnt;

// maksymalna liczba iteracji dla pojedynczego
// punktu

double eps = 1e-3; // satysfakcjonująca odległość od miesca zerowego

int newton( double x, double y )
{

complex<double> p( x, y );
for ( int i = 0; i < maxcnt; ++i )
{

for ( int j = 0; j < n; ++j )
{

if ( norm( p - polar( 1., 2 * j * M_PI / n ) ) < eps )

59

background image

{

return j + 1;

}

}

complex<double> u( 1, 0 );
for ( int j = 1; j < n; ++j ) u *= p;

p -= ( p * u - 1. ) / ( 1. * n * u );

}
return 0;

}

int main()
{

cerr << "Podaj n ";
cin >> n;
cerr << "Podaj maxcnt ";
cin >> maxcnt;
cerr << "Podaj obszar x_min y_min x_max y_max ";
double x_min, y_min, x_max, y_max;
cin >> x_min >> y_min >> x_max >> y_max;
cerr << "Podaj rozmiar siatki ";
int N;
cin >> N;

for ( int x = 0; x < N; ++x )
{

for ( int y = 0; y < N; ++y )
{

double px = x_min + ( double( x - N ) / N + 1 ) * ( x_max - x_min );
double py = y_min + ( double( y - N ) / N + 1 ) * ( y_max - y_min );
cout

<< px
<< ’ ’
<< py
<< ’ ’
<< newton( px, py )
<< endl;

}
cout << endl;

}
return 0;

}

% ./newton > newton.dat
Podaj n 5
Podaj maxcnt 100
Podaj obszar x_min y_min x_max y_max -1 -1 1 1

60

background image

Podaj rozmiar siatki 600
% gnuplot

G N U P L O T
Version 4.0 patchlevel 0
last modified Thu Apr 15 14:44:22 CEST 2004
System: Linux 2.4.26

> set pm3d map
> splot "newton.dat"

Zad. 47.

// Program rysuje zbiór Mandelbrota.
//
// Paweł Klimczewski, 27 listopada 2005.

#include <iostream>
#include <sstream>
#include <complex>
#include <cmath>

using namespace std;

const int n=100;

// maksymalna liczba iteracji dla pojedynczego punktu

const double eps = 2;

int zbadaj_punkt( double x, double y, int n, double eps)
{

double eps2 = eps * eps;
complex< double > z( 0, 0 );
for ( int i = 0; i < n; ++i )
{

// z = z^2 + x + i * y;
z = z * z + complex< double >( x, y );
// if ( |z| > eps )
if ( norm(z) > eps2 )
{

// Ciąg jest rozbieżny. Kolor punktu będzie odpowiadał szybkości
// rozbiegania.
return 1 + i;

}

}
return 0;

}

int main()
{

61

background image

cerr << "Podaj obszar x_min y_min x_max y_max ";
double x_min, y_min, x_max, y_max;
cin >> x_min >> y_min >> x_max >> y_max;
cerr << "Podaj rozmiar siatki ";
int N;
cin >> N;

for ( int x = 0; x < N; ++x )
{

for ( int y = 0; y < N; ++y )
{

double px = x_min + ( double( x - N ) / N + 1 ) * ( x_max - x_min );
double py = y_min + ( double( y - N ) / N + 1 ) * ( y_max - y_min );
cout

<< px
<< ’ ’
<< py
<< ’ ’
<< zbadaj_punkt( px, py, n, eps )
<< endl;

}
cout << endl;

}
return 0;

}

Zad. 48.

#include <iostream>
#include <vector>
#include <iterator>
#include <cmath>
#include <numeric>

using namespace std;

int main()
{

// Liczby będę pamiętał w wektorze.
vector< double > v;
// Odczytuję liczby.
copy( istream_iterator< double >( cin ),

istream_iterator< double >(),
back_insert_iterator< vector< double > >( v ) );

// Obliczam średnią.
double srednia = accumulate( v.begin(), v.end(), 0. ) / v.size();
// Obliczam średnie odchylenie standardowe.

62

background image

// Korzystam z iteratorów do odczytania elementów wektora.
vector< double >::const_iterator it;
double sigma = 0;
for ( it = v.begin(); it != v.end(); ++it )
{

sigma += pow( *it - srednia, 2 );

}
sigma = sqrt( sigma / ( v.size() - 1 ) );
// Wypisuję wyniki.
// Korzystam z indeksów do odczytania elementów wektora.
for ( int idx = 0; idx < v.size(); ++idx )
{

if ( srednia - sigma < v[ idx ] &&

v[ idx ] < srednia + sigma )

{

cout << v[ idx ] << endl;

}

}
return 0;

}

Zad. 49.

#include <iostream>
#include <list>
#include <cmath>

using namespace std;

// Znalezione liczby pierwszę będę zapisywał na liście.
list< int > primes;

// Funkcja oblicza czy liczba i jest pierwsza.
void is_prime( int i )
{

int p = int( sqrt( i ) );
list< int >::const_iterator it;
for ( it = primes.begin(); it != primes.end() && *it <= p; ++it )
{

if ( i % *it == 0 ) return;

}
primes.push_back( i );
cout << i << " ";

}

int main()
{

for ( int i = 2; i < 1000000; ++i )
{

63

background image

is_prime( i );

}
return 0;

}

Zad. 50.

#include <iostream>
#include <set>
#include <iterator>
#include <cstdlib>

using namespace std;

int main()
{

// Na podstawie aktualnego wskazania zegara inicjuję parametr związany
// z generowaniem liczb pseudolosowych.
srand( time( 0 ) );
// Wylosowane liczby będę pamiętał w zbiorze.
set< int > s;
// Losuję.
while ( s.size() < 6 )
{

s.insert( 1 + rand() % 49 );

}
// Wypisuję wyniki.
copy( s.begin(), s.end(), ostream_iterator< int >( cout, "\n" ) );
return 0;

}

Zad. 51.

#include <iostream>
#include <map>

using namespace std;

// W słowniku f będę pamiętał już obliczone wartości wyrazów ciągu.
// Wartości wszystkich wyrazów ciągu są dodatnie.
map< int, int > f;

int fibonacci( int n )
{

// Jeżeli klucz n nie występuje jeszcze w słowniku to wartością f[ n ]
// będzie 0.
if ( f[ n ] == 0 )
{

// Obliczam f[ n ].

64

background image

f[ n ] = fibonacci( n - 1 ) + fibonacci( n - 2 );

}
return f[ n ];

}

int main()
{

f[ 0 ] = f[ 1 ] = 1;
cout << "Podaj numer wyrazu ciągu" << endl;
int n;
cin >> n;
cout << "f(" << n << ")=" << fibonacci( n ) << endl;
return 0;

}

Zad. 52.

#include <iostream>
#include <string>
#include <vector>
#include <iterator>

using namespace std;

// Funkcja porównuje dwa napisy względem ich długości. Skorzystam z niej
// dla znalezienia najdłuższego wiersza.
bool f( const string& l, const string& r )
{

return l.size() < r.size();

}

int main()
{

// Wiersze będę pamiętał w wektorze.
vector< string > v;
// Czytam kolejne wiersze ze strumienia wejściowego.
while ( true )
{

string s;
getline( cin, s );
if ( !cin ) break;
v.push_back( s );

}
if ( v.size() > 0 )
{

// Znajduje rozmiar najdłuższego wiersza.
int mx = max_element( v.begin(), v.end(), f )->size();
// Wyrównuję rozmiar wszystkich wierszy dopisując końcowe spacje
// i odwracam kolejność znaków.

65

background image

vector< string >::iterator it;
for ( it = v.begin(); it != v.end(); ++it )
{

it->resize( mx, ’ ’ );
reverse( it->begin(), it->end() );

}
// Wypisuję wynik.
copy( v.rbegin(), v.rend(), ostream_iterator< string >( cout, "\n" ) );

}
return 0;

}

Zad. 53.

#include <iostream>
#include <sstream>
#include <deque>
#include <set>

using namespace std;

int main( int argc, char* argv[] )
{

if ( argc < 2 )
{

cout << "Należy podać długość podciągu!" << endl;
return 1;

}
// Odczytuję parametr n.
istringstream is( argv[ 1 ] );
int n;
is >> n;
if ( !is || n <= 0 )
{

cout << "Błędnie podana długość podciągu!" << endl;
return 1;

}
// Obiekt d służy do konstruowania n-elementowego podciągu.
deque< char > d;
// Podciągi wpisuję do zbioru s.
set< deque< char > > s;
while ( true )
{

// Czytam kolejne znaki.
int i = cin.get();
if ( i == -1 ) break;

// Koniec danych.

char c = i;
d.push_back( c );

// Dopisuję kolejny znak do podciągu.

if ( d.size() < n ) continue; // Ciąg jest jeszcze za krótki.

66

background image

s.insert( d );

// Dopisuję podciąg do zbioru.

d.pop_front();

// Usuwam początkowy znak podciągu.

}
cout << "liczba różych " << n << "-elementowych podciągów wynosi "

<< s.size() << endl;

return 0;

}

Zad. 54.

#include <iostream>
#include <map>
#include <set>

using namespace std;

int main()
{

// W słowniku będę zliczał wystąpienia poszczególnych słów.
map< string, int > m;
// Odczytuje kolejne słowa i zapisuję w słowniku.
while ( true )
{

string s;
cin >> s;
if ( !cin ) break;
m[ s ]++;

}
// Na podstawie zawartości słownika tworzę zbiór, którego elementy są
// uporządkowane względem liczby występień słów.
set< pair< int, string > > s;
map< string, int >::iterator it;
for ( it = m.begin(); it != m.end(); ++it )
{

s.insert( make_pair( it->second, it->first ) );

}
set< pair< int, string > >::const_reverse_iterator jt;
// Wypisuję wyniki.
int n = 10;
for ( jt = s.rbegin(); jt != s.rend() && n; ++jt, --n )
{

cout << jt->second << ": " << jt->first << endl;

}
return 0;

}

Zad. 55.

#include <iostream>
#include <string>

67

background image

#include <set>

using namespace std;

// Literze przyporządkowujemy liczbę.
int c2i( char c )
{

return 1 + ( c - ’a’ + 16 ) % 26;

}

// Całemu słowu przyporządkowujemy iloczyn liczb odpowiadających literom.
int s2i( const string& s )
{

int i = 1;
for ( string::const_iterator it = s.begin(); it != s.end(); ++it )

i *= c2i( *it );

return i;

}

int main()
{

// Słowa zapamiętuję w zbiorze jako pary { wartość bezwzględna różnicy
// liczby przyporządkowanej danemu słowu minus 1000000, dane słowo }.
// ,,Najlepsze’’ słowa będą znajdowały się na początku.
set< pair< int, string > > m;
// Odczytuję słowa.
while ( true )
{

string s;
cin>>s;
if (!cin) break;
m.insert( make_pair( abs( s2i( s ) - 1000000 ), s ) );

}
// Wypisuję 10 najlepszych wartości.
int n = 10;
set< pair< int, string > >::const_iterator it;
for ( it = m.begin(); n && it != m.end(); ++it, --n )
{

cout << s2i( it->second ) << ": " << it->second << endl;

}
return 0;

}

Zad. 56.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

68

background image

#include <numeric>
#include <list>
#include <cmath>

using namespace std;

// Sprawdzam czy n-ta ksiązka ma taką samą liczbę sąsiadów z każdej strony.
bool sprzyjajace( const vector<int>& v, int n )
{

// Zliczam sąsiadów po lewej stronie.
int l = 0;
if ( n > 0 )
{

l = 1;
for ( int i = n - 2; i >= 0; --i )
{

if ( v[ i ] != v[ n - 1 ] ) break;
++l;

}

}
// Zliczam sąsiadów po prawej stronie.
int p = 0;
if ( n + 1 < v.size() )
{

p = 1;
for ( int i = n + 2; i < v.size(); ++i )
{

if ( v[ i ] != v[ n + 1 ] ) break;
++p;

}

}
return l == p;

}

int main()
{

int z = 4; // liczba książek zielonych
int c = 5; // czerwonych
int n = 8; // niebieskich
int a = 0, omega = 0; // liczba zdarzeń sprzyjających i wszystkich.
// Poszczególne ustawienia zapamiętuję w wektorze.
vector< int > v;
for ( int i = 0; i < z; ++i ) v.push_back( 1 );
for ( int i = 0; i < c; ++i ) v.push_back( 2 );
for ( int i = 0; i < n; ++i ) v.push_back( 3 );

// Obliczam pierwszą permutację.
while ( prev_permutation( v.begin(), v.end() ) );
next_permutation( v.begin(), v.end() );

69

background image

// Przeglądam wszystkie permutacje. Jeżeli permutacja jest zdarzeniem
// sprzyjającym zwiększam zmienną a.
do
{

for ( int i = 0; i < v.size(); ++i )
{

if ( sprzyjajace( v, i ) ) ++a;
++omega;

}

}
while ( next_permutation( v.begin(), v.end() ) );

// Wypisuję wartość prawdopodobieństwa.
cout << a << "/" << omega << endl;
return 0;

}

Zad. 57.

#include <iostream>
#include <sstream>
#include <stack>

int main()
{

// Liczby zapamiętuję na stosie.
stack< double > stos;
// W pętli odczytuje dane wprowadzone przez użytkownika: liczby i symbole
// operacji arytmetycznych.
while ( true )
{

// Wypisuję wartość liczby ze szczytu stosu.
if ( !stos.empty() )
{

cout << "[" << stos.top() << "]" << endl;

}
// Odczytuję dane.
string s;
cin >> s;
if ( s != "+" && s != "-" && s != "*" && s != "/" )
{

// Skoro nie jest to symbol operacji arytmetycznej to powinna być
// to liczba.
istringstream is( s );
double d;
if ( is >> d )
{

stos.push( d );

70

background image

}
else
{

cout << "Błędne dane!" << endl;

}
continue;

}
// Dla każdej operacji potrzebuję dwóch liczb na stosie.
if ( stos.size() < 2 )
{

cout << "Za mało danych na stosie!" << endl;
continue;

}
// Obliczam wynik działania i zapamiętuję na stosie.
if ( s == "+" )
{

double suma = stos.top();
stos.pop();
suma += stos.top();
stos.pop();
stos.push( suma );

}
else if ( s == "-" )
{

double roznica = stos.top();
stos.pop();
roznica -= stos.top();
stos.pop();
stos.push( roznica );

}
else if ( s == "*" )
{

double iloczyn = stos.top();
stos.pop();
iloczyn *= stos.top();
stos.pop();
stos.push( iloczyn );

}
else if ( s == "/" )
{

double iloraz = stos.top();
stos.pop();
iloraz = stos.top() / iloraz;
stos.pop();
stos.push( iloraz );

}

}
return 0;

}

71

background image

Zad. 58.

#include <iostream>
#include <fstream>
#include <complex>
#include <vector>
#include <cmath>

using namespace std;

// Funkcje f i g służą do zadania relacji porządkującej wymaganej dla funkcji
// sort.

bool f( const complex< double >& l, const complex< double >& r )
{

return abs( l ) < abs( r );

}

bool g( const complex< double >& l, const complex< double >& r )
{

// odległość punktu (x1,y1) od prostej y=x wynosi
// abs( x1 - y1 ) / sqrt( 2 )
return abs( l.real() - l.imag() ) / sqrt( 2 ) >

abs( r.real() - r.imag() ) / sqrt( 2 );

}

int main()
{

// Liczby zapamiętuję w wektorze.
vector< complex< double > > v;
// Odczytuję je ze strumienia wejściowego.
copy( istream_iterator< complex< double > >( cin ),

istream_iterator< complex< double > >(),
back_insert_iterator< vector< complex< double > > >( v ) );

// Porządkuje względem odległości od początku układu.
sort( v.begin(), v.end(), f );
// Zapisuję do pliku z1.txt.
fstream f1( "z1.txt" );
copy( v.begin(), v.end(),

ostream_iterator< complex< double > >( f1, "\n" ) );

// Porządkuję względem odległości od prostej y=x.
sort( v.begin(), v.end(), g );
// Zapisuję do pliku z2.txt.
fstream f2( "z2.txt" );
copy( v.begin(), v.end(),

ostream_iterator< complex< double > >( f2, "\n" ) );

return 0;

}

72

background image

Zad. 59.

#include <iostream>
#include <sstream>
#include <cmath>
#include <map>
#include <deque>
#include <set>

using namespace std;

// Na podstawie argumentu uruchomienia programu odczytuję wartość n.
int czytaj_n( int argc, char* argv[] )
{

if ( argc < 2 )
{

cerr << "Brak parametru n!" << endl;
exit( 1 );

}
istringstream is( argv[ 1 ] );
int n;
is >> n;
if ( !is || n <= 0 )
{

cerr << "Błędny parametr n!" << endl;
exit( 1 );

}
return n;

}

// Elementy słownika możemy traktować jako współrzędne wektora w przestrzeni
// 27^n wymiarowej. Funkcja oblicza długość takiego wektora.
double d( const map< deque< char >, int >& v )
{

double s = 0;
map< deque< char >, int >::const_iterator it;
for ( it = v.begin(); it != v.end(); ++it )
{

s += pow( double( it->second ), 2 );

}
return sqrt( s );

}

// Dzieląc współrzędne wektora przez jego długość otrzymujemy wektor jednostkowy,
// którego koniec leży na jednostkowej sferze. Funkcja oblicza odległość pomiędzy
// dwoma punktami sfery odpowiadającymi wektorom u i v. du i dv są odpowiednio
// długościami u i v.
double odleglosc( const map< deque< char >, int >& u, double du,

const map< deque< char >, int >& v, double dv )

{

73

background image

double s = 0;
map< deque< char >, int >::const_iterator iu = u.begin(), iv = v.begin();

while ( iu != u.end() && iv != v.end() )
{

if ( iu->first < iv->first )
{

s += pow( iu->second / du, 2 );
++iu;
continue;

}
if ( iu->first > iv->first )
{

s += pow( iv->second / dv, 2 );
++iv;
continue;

}
s += pow( iu->second / du - iv->second / dv, 2 );
++iu;
++iv;

}
for ( ; iu != u.end(); ++iu )
{

s += pow( iu->second / du, 2 );

}
for ( ; iv != v.end(); ++iv )
{

s += pow( iv->second / dv, 2 );

}
return sqrt( s );

}

// Rozmiar analizowanych podciągów znaków.
int n;
// Ostatnio odczytany podciąg n znaków.
deque< char > p;
// Statystyka odpowiadająca tekstowi wzorcowemu.
map< deque< char >, int > st0;

// Odczytuję tekst wzorcowy i tworzę jego statystykę.
void czytaj_dane()
{

int zn = 0;
while ( true )
{

int i = cin.get();
if ( i == -1 ) break; // koniec danych
++zn;
p.push_back( char( i ) );

74

background image

if ( p.size() < n ) continue;
st0[ p ]++;
p.pop_front();

}
cerr

<< "Tekst wzorcowy: znaków " << zn
<< ", ciągów " << n << "-elementowych " << st0.size()
<< endl << endl;

}

int main( int argc, char* argv[] )
{

n = czytaj_n( argc, argv );
czytaj_dane();
// Długość wektora odpowiadającego statystyce tekstu wzorcowego.
double d0 = d( st0 );
// Słownik st1 odpowiada statystyce ,,przedłużanego’’ tekstu.
map< deque< char >, int > st1( st0 );
// W pętli obliczam kolejne znaki.
while ( true )
{

// W zbiorze będę pamiętał pary { odległość pomiędzy statystyką tekstu
// wzorcowego a tekstu przedłużonego o dopisany znak, dopisany znak }.
// Biorąc pod uwagę uporządkowanie elementów zbioru względem wartości
// elementów znak pierwszej pary będzie najlepszym wyborem.
set< pair< double, char > > mn;
// Obliczam odległości dla dopisania każdej litery i spacji.
for ( char idx = ’a’ - 1; idx <= ’z’; ++idx )
{

char c = idx < ’a’ ? ’ ’ : idx;
p.push_back( c );
st1[ p ]++;
double d1 = d( st1 );
mn.insert( make_pair( odleglosc( st0, d0, st1, d1 ), c ) );
st1[ p ]--;
p.pop_back();

}
char naj = mn.begin()->second;
cout << naj << flush;
p.push_back( naj );
st1[ p ]++;
p.pop_front();

}
return 0;

}

Zad. 60.

• a.h

75

background image

#ifndef __A_H
#define __A_H

class A
{

private:

int i;

// kolejny numer obiektu

static int n; // licznik utworzonych obiektów

public:

A();
A( const A& a );
~A();

};

#endif // __A_H

• a.cc

#include <iostream>
#include "a.h"

using namespace std;

int A::n = 0;

A::A() : i( ++n )
{

cout << "Tworzę " << i << "-ty obiekt klasy A." << endl;

}

A::A( const A& a ) : i( ++n )
{

cout

<< "Tworzę " << i << "-ty obiekt klasy A, na podstawie "
<< a.i << "-go obiektu." << endl;

}

A::~A()
{

cout << "Usuwam " << i << "-ty obiekt klasy A." << endl;

}

• main.cc

#include "a.h"

using namespace std;

int main()

76

background image

{

A a;
for ( int i = 0; i < 2; ++i )
{

A b;
for ( int j = 0; j < 2; ++j )
{

A c( b );

}
A d;

}
return 0;

}

Zad. 61.

• z100.h

#ifndef __Z100_H
#define __Z100_H

class Z100
{

private:

int i;

public:

Z100( int _i );
Z100& operator=( const Z100& z );
operator int() const;

};

#endif // __Z100_H

• z100.cc

#include "z100.h"

Z100::Z100( int _i ) : i( _i % 100 )
{
}

Z100& Z100::operator=( const Z100& z )
{

i = z.i;
return *this;

}

Z100::operator int() const

77

background image

{

return i;

}

• main.cc

#include <iostream>
#include "z100.h"

using namespace std;

int main()
{

Z100 a = 2006;
cout << "a = " << a << endl;
a = a * a * a;
cout << "a * a * a = " << a << endl;
return 0;

}

Zad. 62.

• tablica.h

#ifndef __TABLICA_H
#define __TABLICA_H

#include <vector>

using namespace std;

class Tablica
{

private:

vector< int > v;

public:

int& operator[]( int idx );

};

#endif // __TABLICA_H

• tablica.cc

#include "tablica.h"

using namespace std;

int& Tablica::operator[]( int idx )

78

background image

{

while ( v.size() < idx + 1 )
{

v.push_back( 0 );

}
return v[ idx ];

}

Zad. 63.

• tablica2.h

#ifndef __TABLICA2_H
#define __TABLICA2_H

#include <vector>

using namespace std;

class Tablica2
{

private:

vector< int > v1, v2;

public:

int& operator[]( int idx );

};

#endif // __TABLICA2_H

• tablica2.cc

#include "tablica2.h"

using namespace std;

int& Tablica2::operator[]( int idx )
{

if ( idx >= 0 )
{

while ( v1.size() < idx + 1 )
{

v1.push_back( 0 );

}
return v1[ idx ];

}
else
{

idx = -idx - 1;
while ( v2.size() < idx + 1 )

79

background image

{

v2.push_back( 0 );

}
return v2[ idx ];

}

}

Zad. 64.

#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <complex>

using namespace std;

class Rysunek
{

vector< pair< double, double > > v;

public:

void punkt( double x, double y );
void rysuj();
void zeruj();

};

void Rysunek::punkt( double x, double y )
{

v.push_back( make_pair( x, y ) );

}

void Rysunek::rysuj()
{

if ( v.size() == 0 )
{

cerr << "Brak punktów!" << endl;
exit( 1 );

}

ofstream dane( "rysunek.dat" );
for ( int i = 0; i < v.size(); ++i )
{

dane << v[ i ].first << " " << v[ i ].second << endl;

}
dane.close();

ofstream polecenia( "rysunek.gp" );
double x_min = v[ 0 ].first, x_max = x_min;

80

background image

double y_min = v[ 0 ].first, y_max = y_min;
for ( int i = 1; i < v.size(); ++i )
{

x_min = min( x_min, v[ i ].first

);

x_max = max( x_max, v[ i ].first

);

y_min = min( y_min, v[ i ].second );
y_max = max( y_max, v[ i ].second );

}
polecenia

<< "set xrange [" << x_min << ":" << x_max << "]" << endl
<< "set yrange [" << y_min << ":" << y_max << "]" << endl
<< "plot ’rysunek.dat’ with lines" << endl;

polecenia.close();

system( "gnuplot -persist rysunek.gp" );

}

void Rysunek::zeruj()
{

v.clear();

}

int main()
{

Rysunek r;
complex< double > z( 1.0, 0.0 );
for ( int i = 0; i < 2006; ++i )
{

r.punkt( z.real(), z.imag() );
z *= polar( pow( 0.9, 1. / 360 ), M_PI / 180 );

}
r.rysuj();
r.zeruj();
r.punkt( -1.,

0. );

r.punkt(

0., -1. );

r.punkt(

1.,

0. );

r.punkt(

0.,

1. );

r.punkt( -1.,

0. );

r.rysuj();
return 0;

}

Zad. 65.

#include <iostream>

using namespace std;

class Wektor

81

background image

{

private:

double x, y; // współrzędne wektora

public:

Wektor( double _x, double _y ) : x( _x ), y( _y )
{
}
Wektor operator+( Wektor v )
{

return Wektor( x + v.x, y + v.y );

}
double operator*( Wektor v )
{

return x * v.x + y * v.y;

}
void wypisz()
{

cout << "[" << x << ", " << y << "]" << endl;

}

};

int main()
{

Wektor a( 5, 1 ), b( 3, -2 ), c( -8, 1 );
cout << "a + b = ";
(a + b).wypisz();
cout << endl;
cout << "b * c = " << b * c << endl;
cout << "a + b + c = ";
(a + b + c).wypisz();
cout << endl;
return 0;

}

Zad. 71.

#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <vector>
#include <ctime>

using namespace std;

class Figura
{

public:

virtual double obwod()=0;

82

background image

virtual double pole()=0;
virtual string nazwa()=0;

};

class Trojkat : public Figura
{

private:

double a; // dlugość boku

public:

Trojkat( double _a ) : a( _a )
{
}
double obwod()
{

return 3 * a;

}
double pole()
{

return sqrt( 3 ) / 4. * a * a;

}
string nazwa()
{

ostringstream os;
os << "trójkąt równoboczny o boku długości " << a;
return os.str();

}

};

class Kwadrat : public Figura
{

private:

double a; // długość boku

public:

Kwadrat( double _a ) : a( _a )
{
}
double obwod()
{

return 4 * a;

}
double pole()
{

return a * a;

}
string nazwa()
{

ostringstream os;
os << "trójkąt o boku długości " << a;
return os.str();

83

background image

}

};

class Kolo : public Figura
{

private:

double d; // średnica

public:

Kolo( double _d ) : d( _d )
{
}
double obwod()
{

return d * M_PI;

}
double pole()
{

return M_PI * d * d / 4.;

}
string nazwa()
{

ostringstream os;
os << "koło o średnicy " << d;
return os.str();

}

};

void suma( vector< Figura* > v )
{

double s = 0; // sumaryczne pole powierzchni
double l = 0; // sumaryczna długość obwodów
vector< Figura* >::iterator it;
for ( it = v.begin(); it != v.end(); ++it )
{

s += (*it)->pole();
l += (*it)->obwod();
cout << "dodaję " << (*it)->nazwa() << endl;

}
cout

<< "s = " << s << endl
<< "l = " << l << endl;

}

int main()
{

srand( time( 0 ) );
vector< Figura* > v;
while ( v.size() < 10 )
{

84

background image

double x = rand() / ( RAND_MAX + 1.);
x = 1 + 9 * x; // 1 <= x < 10

switch ( rand() % 3 )
{

case 0:

v.push_back( new Trojkat( x ) );
break;

case 1:

v.push_back( new Kwadrat( x ) );
break;

case 2:

v.push_back( new Kolo( x ) );
break;

}

}
suma( v );
return 0;

}

85


Wyszukiwarka

Podobne podstrony:
zadanienia-programowanie, smf, , programowanie
ZADANIA Z PROGRAMOWANIA
Java Zadania z programowania z przykładowymi rozwiązaniami
6 2 Zadania programowania liniowego
AM, Liniowe zadanie decyzyjne, Model matematyczny zadania programowania liniowego
Browary, Zadania programowania kwadratowego
C++ Zadania z programowania z przykładowymi rozwiązaniami [PL]
Zadanie PROGRAMOWANIE, Informatyka
tp-zadania cz3, Szkoła, Programowanie, C++, Zadania z programowania cz.3
Stroop.eksp.zadanie, Programowanie procedur badawczych
Algorytmy-zadania, Programowanie, wykłady C++
C Zadania z programowania 9788324637072
27.2 wskazniki - zadania, Programowanie, Klasa III
Optymalizacja Cw 3 Zadanie programowania nieliniowego bez ograniczeń algorytmy optymalizacji lokaln
mathcad, Podstawy Informatyki - zadania z programu Mathcad
zadania z programowania, szkola, programowanie
27.4 - zadanie, Programowanie, Klasa III
Zadania z programowania w Turbo Pascalu na ocenę 5, Informatyka

więcej podobnych podstron