Zadania

Zadania z Programowania I w języku C++ w środowisku systemu Linux z dnia 27 grudnia 2005

Środowisko pracy. Program make. Edytor emacs. Debugger ddd. Zad. 1. Dokonaj kompilacji pliku źródłowego hello.cc1 do pliku z programem 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 main.cc i fun.c w celu otrzymania programu main. Uruchom program. Zad. 4. Napisz plik Makefile z jawnymi zasadami kompilacji programów hello i main. Dodatkowo zdefiniuj regułę clean usuwającą wszystkie pliki pośrednie .o oraz wynikowe (hello i main). Zad. 5. Napisz plik Makefile2 z domyślnymi zasadami kompilacji programó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 main. Zad. 6. Wykorzystując predefiniowane reguły kompilacji napisz plik Makefile3 przygotowujący programy hello i main w sposób wymagany dla śledzenia ich pracy debuggerem. Zad. 7. Na przykładzie programów hello, main i pierwsze porównaj jakość kodu (rozmiar, szybkość wykonania) wygenerowanego przez kompilator z opcją -O0 i -O2. Dla pomiaru czasu skorzystaj z polecenia time. Zad. 8. Dokonaj kompilacji programów hello, main i pierwsze z poziomu edytora emacs. Zad. 9. Przy pomocy debuggera ddd prześledź wykonanie programów hello, main i pierwsze. W programie pierwsze zatrzymaj wykonanie dla 17 obliczonej liczby pierwszej, a następnie odczytaj wartości zmiennych i i j. Operacje wejścia/wyjścia Zad. 10. Korzystając ze stałej M_PI zdefiniowanej w pliku nagłówkowym cmath napisz program pi wypisujący do standardowego strumienia wyjściowego 5 kolejnych potęg liczby π z dokładnością liczby cyfr po przecinku równą wykładnikowi potęgi 1

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

1

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. 11. Napisz program liczby odczytujący ze standardowego strumienia wejściowego dwie liczby całkowite (int) i zapisujący do standardowego 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. 12. Począwszy od bieżącego semestru nasz wydziałowy barek wprowadził 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 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

2

Zad. 13. 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++. Instrukcje warunkowe i iteracje Zad. 14. Napisz program znaczace sprawdzajacy liczbę cyfr znaczących typów float i double. P Wskazówka: obliczaj sumę i=0 101 i . Zad. 15. Napisz program kwadraty obliczający sumę 100 X 000 000 i=1

1 i2

Dokonaj sumowania w kolejności 1 1 1 1 + 2 + 2 + ... + 2 1 2 3 100 000 0002 oraz w kolejności odwrotnej 1 1 1 + + ... 2 2 2 100 000 000 99 999 999 1 Obliczenia przeprowadź posługując się zmiennymi typu • float • double Wytłumacz różnice. Który z wyników jest najbliższy prawdzie? P 1 π2 Wskazówka: ∞ i=1 i2 = 6 Zad. 16. 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. 17. Korzystając z instrukcji iteracyjnych napisz program pi3 wypisujący w kolejnych wierszach wartość π z dokładnością do i miejsc po przecinku. 3

3.1 3.14 3.141 3.1415 3.14159

Zad. 18. Korzystając z instrukcji iteracyjnych napisz program pi4 wypisujący w kolejnych wierszach wartość π i z dokładnością do i miejsc po przecinku. potęga wartość ---------------1 3.1 2 9.87 3 31.006 4 97.4091 5 306.01968

Zad. 19. 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. 20. Napisz program slowa odczytujący liczbę słów ze strumienia wejściowego i wypisujący ich liczbę oraz średnią długość. Obliczenia przeprowadź dla tekstów Pana Tadeusza i Hamleta.2 2

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

4

Zad. 21. Napisz program licz będące odpowiednikiem systemowego polecenia wc, zliczającego liczbę znaków, słów i wierszy w standardowym strumieniu wejściowym. Działanie programu sprawdź na jego pliku źródłowym licz.cc i porównaj z programem wc. Zad. 22. Napisz program rzeczywista, który liczbę a podaną jako argument wypisuje w postaci p · 2w Skorzystaj z operacji na bitach i funkcji frexp, ldexp. % ./rzeczywista 2005 0.9790039062500000*2^11

Nie uwzględniaj szczególnej reprezentacji wartości 0. Zad. 23. Mając daną zmienną typu rzeczywistego double i wiedząc, że jest postaci p · 2w oraz posługując się operacjami bitowymi i funkcjami frexp, ldexp skonstruuj liczbę w

p · 2b 2 c Nie uwzgędniaj szczególnej reprezentacji wartości 0. Zad. 24. Napisz program pierwiastek, który oblicza pierwiastek kwadratowy zadanej liczby. Nie korzystaj z istniejącej funkcji sqrt lecz zaimplementuj wzór Newtona, dla którego √ x = lim an , n→∞

gdzie (an ) jest ciągiem zadanym rekurencyjnie an+1 = 12 (an + axn ). Wykonaj 10 iteracji przez kopiowanie fragmentu programu. Zwróć uwagę, na a) szybkość zbiegania w zależności od początkowej wartości a0 , b) zachowanie dla ujemnych x. Dla ustalenia wartości a0 skorzystaj z poprzedniego zadania. Zad. 25. Korzystając ze wzoru Gaussa napisz program dzien, który oblicza dzień tygodnia na podstawie daty. Numer dnia określony jest następującym wzorem r/4 − r/100 + r/400 + 367m/12 + d + 365r , 5

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. 26. Napisz program podatki obliczający wysokość podatku dochodowego 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ł. Dane dotyczące wysokości kwot i podatku odpowiadające poszczególnym progom zapisz w tablicy. Zad. 27. Napisz program dziennik, który oblicza ile dni upłynęło od podanej daty do dnia uruchomienia programu. Skorzystaj z doświadczeń programu dzien i funkcji time przekazującej liczbę sekund jakie upłynęły od godziny 000 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. 28. 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 programem? Zad. 29. Napisz program podzielne znajdujący wszystkie liczby z zakresu od 1 do 1000, które są podzielne przez sumę swoich cyfr. Zad. 30. Napisz program podzielne2 znajdujący wszystkie liczby z zakresu od 1 do 1000, które są jednocześnie podzielne przez sumy swoich parzystych i nieparzystych cyfr. Zad. 31. Napisz program cezar, który czyta bajty ze standardowego strumienia wejściowego (funkcja cin.get) i przepisuje do standardowego strumienia wyjściowego (cout.put) zastępując litery alfabetu łacińskiego literami znajdującymi się w alfabecie o n pozycji dalej. Wartość n odczytaj z parametru uruchomienia programu. 6

Zad. 32.

Napisz program wielomian obliczający wartość wielomianu

w(x) = 100x3 − 625x2 + 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 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ń zrealizowanych różnymi sposobami. Następnie zapisując na kartce wyniki i traktując program jako programowalny kalkulator, dzięki któremu mamy łatwość liczenia wartości wielomianu w poszczególnych punktach, znajdź metodą bisekcji miejsca zerowe. Zad. 33. Napisz program bisekcja – rozwinięcie programu wielomian – umożliwiający obliczanie miejsc zerowych wielomianu w(x) = 100x3 − 625x2 + 1183.19x − 660.489 metodą bisekcji. Uzyskane wyniki porównaj z dokładnymi wartościami miejsc zerowych wielomianu. Zad. 34. Napisz program styczne będący modyfikacją programu bisekcja, znajdujący metodą stycznych, w której „kandydata” xn na miejsce zerowe funkcji f (x) zastępujemy „kandydatem lepszym” xn+1 = xn −

f (xn ) f 0 (xn )

Zad. 35. Napisz program rekurencja porównujący rekurencyjne i iteracyjne obliczanie a) silni, b) liczb Fibonacciego.

7

Liczby Fibonacciego zadane są rekurencyjnie fn+2 = fn+1 + fn oraz f0 = f1 = 1. Następnie oblicz 10!, 20!, 50!, f10 , f20 , f50 . Skomentuj uzyskane wyniki. Zad. 36. Napisz program euklides znajdujący największy wspólny dzielnik 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 znalezienia N W D(b, reszta z dzielenia a przez b). Rozwiązanie zapisz na dwa sposoby: iteracyjnie i rekurencyjnie. Zad. 37. Napisz program newton znajdujący dla zadanego punktu x0 miejsce zerowe wielomianu w(x) = (x − 1)(x − 2)(x − 3)(x − 4) przy pomocy metody Newtona (stycznych; polegającej na „zastąpieniu” kandydata i) xi na miejsce zerowe na ogół „lepszym” kandydatem xi+1 = xi − ww(x 0 (x ) ). Oblii czenia wykonaj w dziedzinie zespolonej. Następnie oblicz miejsca zerowe dla następujących wartości początkowych x0 : 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) %

Tworzenie rysunków przy wykorzystaniu programu gnuplot Zad. 38. 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. 39. Rozbuduj program litery1 do programu litery2 aby przykładowe obliczenia 8

% ./litery2 pt.txt h.txt

przygotowały dane (pliki pt.txt.dat, h.txt.dat oraz skrypt.gp) dla otrzymania rysunku programem gnuplot: % gnuplot -persist skrypt.gp "pt.txt.dat" "h.txt.dat" 0.2

0.15

0.1

0.05

0 _

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

r

s

t

u

v

w

x

y

z

Zad. 40. 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 pierwszych znaków Pana Tadeusza i przy pomocy programu litery2 stwórz wykres 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. //

9

// Paweł Klimczewski, 27 listopada 2005 #include #include using namespace std; int main() { for ( int y = -50; y { for ( int x = -50; { double r = sqrt( cout << x << ’ ’ } cout << endl; } return 0; }

<= 50; ++y ) x <= 50; ++x ) x * x + y * y ); << y << ’ ’ << r << endl;

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 last modified Thu Apr 15 14:44:22 CEST 2004 System: Linux 2.4.26 > set pm3d map > splot "test.dat"

otrzymujemy rysunek

10

"test.dat" 60 80 70 60 50 40 30 20 10 0

40

20

0

-20

-40

-60 -60

-40

-20

0

20

40

60

Zad. 41. Napisz program newton2 przygotowujący dane dla pokolorawania 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 wartość 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 obszaru xmin, ymin, xmax, ymax, stopień wielomianu n, maksymalną liczbę iteracji maxcnt i liczbę oczek siatki N . Zad. 42. 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 (ak ) : ak ∈ Z, a0 = 0, ak+1 = ak 2 + x + iy jest ograniczony. Okazuje się, że jeżeli ∃k, |ak | > 2 to ciąg nie jest ograniczony. W programie obliczenia są skończone, zatem generowany rysunek będzie odpowiednim przybliżeniem. Dla każdego punktu zbadaj nie więcej niż n wyrazów ciągu (ak ). Jeżeli wszystkie wyrazy spełniają warunek |ak | ≤  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 |ai | > ). Jako parametry początkowe przyjmij środek kwadratu x = −0.5, y = 0, 11

długość boku a = 3, n = 100,  = 2. Biblioteka STL Zad. 43. Napisz program filtr odczytujący ze standardowego strumienia wejściowego liczby rzeczywiste xi i wypisujący do standardowego strumienia wyjściowego, te które należą do przedziału (¯ x − σ, x¯ + σ). Skorzystaj z klasy vector. sP n x − xi )2 i=1 (¯ σ= n−1 jest średnim odchyleniem standardowym, a x¯ =

x1 + . . . + xn n

jest średnią arytmetyczną. Zad. 44. Napisz program pierwsze obliczający wszystkie liczby pierwsze 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 ici. 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 ic. Porównaj szybkość obliczeń obu wersji. (bxc oznacza największą liczbę całkowitą nie większą od x.) Zad. 45. Napisz program totolotek losujący 6 różnych liczb z 49 i wypisujący je do standardowego strumienia wyjściowego w sposób uporządkowany. 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. 46. Wprowadzając słownik (klasa map) dla zapamiętywana już obliczonych 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. 47. Napisz program lustro odczytujący ze standardowego strumienia 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 12

1 23 456

otrzymać następujący wynik 654 32 1

Zad. 48. Napisz program ciagi obliczający liczbę, parami różnych, n– elementowych ciągów znaków w standardowym strumieniu wejściowym. Dokonaj obliczeń dla tekstów Pana Tadeusza i Hamleta. Zad. 49. 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ń. Dokonaj obliczeń dla tekstów Pana Tadeusza i Hamleta. Zad. 50. 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 odpowiadają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. 51. 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ąsiadó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. 52. Napisz program kalkulator będący kalkulatorem liczącym w Odwrotnej Notacji Polskiej. Program powinien czytać dane ze standardowego strumienia wejściowego. Jeżeli wprowadzona dana jest liczbą program dopisuje ją na wierzchołku stosu. Jeżeli jest jednym z symboli działań arytmetycznych (+,-,*,/) program odczytuje i usuwa z wierzchołka stosu dwie liczby, które traktuje jak argumenty działania, oblicza wynik działania i umieszcza 13

na wierzchołku stosu. Po każdej operacji wypisuje na ekranie wartość elementu z wierzchołka stosu. Skorzystaj z klasy stack. Zad. 53. Napisz program odleglosci odczytujący ze standardowego strumienia wejściowego liczby zespolone zi 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. 54. Napisz program poeta dopisujący kontynuację zadanego tekstu. Program uruchomiony w sposób % ./poeta n < pt.txt

powinien odczytać ze standardowego strumienia wejściowego wszystkie k znaków zi obliczając statystykę Sn (k) częstości wystąpień n–elementowych podciągów znaków. Następnie program powinien obliczyć taki znak zk+1 , dla którego odległość d(Sn (k), Sn (k + 1)) będzie najmniejsza. I kolejno obliczać dalsze znaki zk+2 , zk+3 itd. Statystyka Sn jest n! składnikowym wektorem. Odległość d jest zwykłą odległością kartezjańską w przestrzeni n! wymiarowej unormowanych wektorów Sn . (Jako miarę identyczności statystyk można także przyjąć euklidesowy iloczyn skalarny hSn (k), Sn (k + 1)i unormowanych wektorów Sn .)

14

Rozwiązania zadań Zad. 1. % g++ -o hello hello.cc % ./hello Programowanie w C++ jest proste i przyjemne! %

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

Zad. 3. % g++ -c -o main.o main.cc % gcc -c -o fun.o fun.c % g++ -o main main.o fun.o % ./main Hello world %

Zad. 4. all: hello main hello: hello.cc g++ -o hello hello.cc main: main.cc fun.c fun.h g++ -c -o main.o main.cc gcc -c -o fun.o fun.c g++ -o main main.o fun.o .PHONY: clean clean: rm -f *.o hello main

15

Zad. 5. %.o: %.c gcc -c -o $@ $< %.o: %.cc g++ -c -o $@ $< %: %.o g++ -o $@ $^ all: hello main hello: hello.o main: main.o fun.o

Zad. 6. CCFLAGS += -g CXXFLAGS += -g all: hello main hello: hello.o $(CXX) -o $@ $< main: main.o fun.o $(CXX) -o $@ $^

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

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

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

Zad. 10. // 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 #include

16

int main() { printf("potęga wartość\n" "----------------\n"); printf("1 %5.1f\n",M_PI); printf("2 %6.2f\n",M_PI*M_PI); 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 #include #include using namespace std; int main() { cout<<"potęga wartość"<<endl; cout<<"-----------------"<<endl<
Zad. 11. // Program odczytuje dwie liczby i wypisuje ich iloraz i sumę. // Wersja w stylu C++. // // Paweł Klimczewski, 10 października 2005 #include using namespace std; int main() { cout<<"Podaj pierwszą liczbę"<<endl;

17

int i; cin>>i; cout<<"Podaj drugą liczbę"<<endl; int j; cin>>j; cout<<"Pierwsza odczytana liczba "<<<endl; cout<<"Druga odczytana liczba "<<j<<endl; cout<<"Iloraz "< 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. 12. // Program oblicza zadłużenie wobec barku wydziałowego na podstawie rachunku // nadesłanego w pliku;) // // Paweł Klimczewski, 10 października 2005 #include int main() { double cena1; scanf("%*[A-Za-z ]:%lf\n",&cena1); double cena2; scanf("%*[A-Za-z ]:%lf\n",&cena2);

18

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

Zad. 13. // Program zamienia miejscami liczby zapisane w pliku 2pi.txt. // // Paweł Klimczewski, 10 października 2005 #include #include <string> using namespace std; int main() { fstream f("2pi.txt"); string s1, s2; f>>s1>>s2; f.seekp(0,ios::beg); f<<s2<<endl<<s1<<endl; return 0; }

Zad. 14. // Program sprawdza liczbę cyfr znaczących dla zmiennych typu float, double // i long double. // // Paweł Klimczewski, 19 października 2005 #include #include #include using namespace std; int main() { // dla łatwiejszego porównania wyników cout << setprecision( 40 ); // float cout << "----- float" << endl; float fsuma = 0, poprzednia_fsuma; int i = 0;

19

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. 15. // Program oblicza sumę odwrotności kwadratów z zakresu 1...10^8 posługując // się zmiennymi typu float, double i long double. // // Paweł Klimczewski, 19 października 2005 #include #include #include

20

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; // 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; }

21

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. 16. // Program zamienia kolejność znaków w pliku. // // Paweł Klimczewski, 4 listopada 2005 #include #include #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 ); char c2 = f.get(); f.seekp( i, ios::beg ); f.put( c2 ); f.seekp( -( i + 1 ), ios::end ); f.put( c1 ); } return 0; }

22

Zad. 17. // Program wypisuje w kolejnych wierszach coraz dokładniejszą wartość // liczby pi. // // Paweł Klimczewski, 4 listopada 2005 #include #include #include 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. 18. // Program wypisuje w kolejnych wierszach coraz dokładniejszą wartość // kolejnej potęgi liczby pi. // // Paweł Klimczewski, 4 listopada 2005 #include #include #include using namespace std; int main() { cout << "Podaj liczbę wierszy" << endl; int i;

23

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. 19. // Program rysuje kwadrat z przekątną. // // Paweł Klimczewski, 4 listopada 2005 #include using namespace std; int main() { cout << "Podaj rozmiar int n; cin >> n; if ( !cin || n <= 0 || { cout << "Niepoprawne } else { for ( int y = 0; y < { for ( int x = 0; x { char znak = ’ ’; if ( !x || !y || {

kwadratu" << endl;

n > 20 ) dane!" << endl;

n; ++y ) < n; ++x )

x == n - 1 || y == n - 1 || x == y )

24

znak = ’*’; } cout << znak; } cout << endl; } } return 0; } // Program rysuje tabelkę. // // Paweł Klimczewski, 4 listopada 2005 #include #include 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. 20. // Program oblicza liczbę odczytanych słów i średnią długość słowa // // Paweł Klimczewski, 4 listopada 2005 #include #include <string> using namespace std; int main() { int n = 0, znakow = 0;

25

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. 21. // Program stara się naśladować systemowe polecenie wc. // // Paweł Klimczewski, 4 listopada 2005 #include #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 << ", znaków " << znakow << endl; return 0; }

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

26

#include #include #include #include

<sstream>

using namespace std; // Odczytanie wartości na podstawie napisu p wraz ze sprawdzeniem // zapisuję w osobnej funkcji. template 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 ] ); int m; double c = frexp( x, &m ); cout << fixed << setprecision( 16 ) << c << "*2^" << m << endl; return 0; }

Zad. 23. // Program odczytuje podaną wartość x=c*2^m, a następnie konstruuje liczbę // c*2^(m/2).

27

// // Paweł Klimczewski, 11 listopada 2005 #include #include #include #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. 24. // Program oblicza pierwiastek zadanej liczby metodą Newtona. // // Paweł Klimczewski, 11 listopada 2005 #include #include #include #include

"czytaj.h"

using namespace std; int main( int argc, char* argv[] ) { // 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;

28

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. 25. // Program oblicza dzień tygodnia. // // Paweł Klimczewski, 11 listopada 2005 #include #include #include #include

<sstream>

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 void czytaj_z_wejscia( T& x, const char* p = "Podaj liczbę" ) { while ( true ) { cout << p << endl; 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;

29

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( int m; czytaj_z_wejscia( int d; czytaj_z_wejscia( if ( m < 3 ) { m += 10; r -= 1; } else { m -= 2; } int n = r / 4 - r

r, "Podaj rok" ); m, "Podaj miesiąc" ); d, "Podaj dzień" );

/ 100 + r / 400 + 367 * m / 12 + d + r * 365;

const char* dni_tygodnia[]= { "niedziela", "poniedziałek", "wtorek", "środa", "czwartek", "piątek", "sobota" }; cout << "To jest " << dni_tygodnia[ n % 7 ] << "." << endl; return 0; }

30

Zad. 26. // Program oblicza wielkość podatku na podstawie podanego dochodu. zgodnie // ze skalą z 2005 roku. // // Paweł Klimczewski, 13 listopada 2005 #include #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; }

Zad. 27. // Program oblicza liczbę dni jakie upłynęły od zadanej daty. // // Paweł Klimczewski, 11 listopada 2005 #include #include #include "czytaj.h" using namespace std;

31

int main() { int r; czytaj_z_wejscia( r, int m; czytaj_z_wejscia( m, int d; czytaj_z_wejscia( d, // Konwersja podanej // rok zaczyna się w if ( m > 2 ) { m = m - 2; } else { m = m + 10; r = r - 1; }

"Podaj rok" ); "Podaj miesiąc" ); "Podaj dzień" ); daty do postaci wymaganej we wzorze Gaussa, czyli marcu.

// 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; 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;

32

} 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. 28. // Program oblicza silnię zadanej liczby oraz ilość cyfr 7 w jej zapisie. // // Paweł Klimczewski, 11 listopada 2005 #include #include #include #include

<sstream> "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 // 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 ) {

33

if ( t[ i ] == ’7’ ) ++n; } cout << x << "!=" << s << endl; cout << "Liczba siódemek w zapisie = " << n << endl; return 0; }

Zad. 29. // Program znajduje wszystkie liczby całkowite z zakresu 1..1000 podzielne // przez sumę swoich cyfr. // // Paweł Klimczewski, 13 listopada 2005 #include #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; }

Zad. 30. // 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 #include <sstream> using namespace std;

34

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. 31. // Program szyfruje dane stosując szyfr cezara. // // Paweł Klimczewski, 13 listopada 2005 #include #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 ) { 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’;

35

cout.put( znak ); } return 0; }

Zad. 32. // 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 #include #include #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; } 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; }

36

Zad. 33. // 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 #include #include #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; } // 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;

37

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 ); bisekcja( x1, x2, w2 ); bisekcja( x1, x2, w3 ); bisekcja( x1, x2, w4 ); return 0; }

Zad. 34. // Program oblicza miejsca zerowe wielomianu // // w( x ) = 100 x^3 - 625 x^2 + 1183.19 x - 660.489 // // metodą stycznych. //

38

// Paweł Klimczewski, 13 listopada 2005 #include #include #include #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; }

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

<sys/time.h> "czytaj.h"

using namespace std;

39

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() { 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 );

40

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. 36. // Program znajduje największy wspólny dzielnik metodą Euklidesa. // // Paweł Klimczewski, 11 listopada 2005 #include #include "czytaj.h" using namespace std;

// iteracyjnie int nwd1( int a, int b ) { while ( b ) { int r = a % b; a = b; b = r; } return a;

41

} // 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( int b; czytaj_z_wejscia( cout << "NWD( " << a << nwd1( a, b ) << nwd2( a, b ) return 0; }

a, "Podaj pierwszą liczbę" ); b, "Podaj drugą liczbę" ); << ", " << b << " ) = " << " = " << endl;

Zad. 37. // Program oblicza miejsca zerowe wielomianu // // w( x ) = (x-1)(x-2)(x-3)(x-4) // // metodą stycznych. // // Paweł Klimczewski, 13 listopada 2005 #include #include #include #include #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 ) {

42

// [ ( // = [ // = 4 return

x x^4 x^3 ( (

1 ) ( x - 2 ) ( x - 3 ) ( x - 4 ) ]’ = - 10 x^3 + 35 x^2 - 50 x + 24 ]’ = - 30 x^2 + 70 x - 50 = ( ( 4 x - 30 ) x + 70 ) x - 50 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. 38. // Program oblicza częstotliwość występowania liter w tekście odczytanym // ze standardowego strumienia danych // // Paweł Klimczewski, 25 listopada 2005 #include 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();

43

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 ) { 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

44

0.18 "pt.dat" 0.16

0.14

0.12

0.1

0.08

0.06

0.04

0.02

0 0

5

10

15

20

25

30

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

45

0.18 "pt.dat" 0.16

0.14

0.12

0.1

0.08

0.06

0.04

0.02

0 _

a

b

c

d

e

f

g

h

i

j

k

l

m n

o

p

q

r

s

t

u

v

w

x

y

z

Zad. 39. // 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 #include 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 ) {

46

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; } 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;

47

skrypt << "plot "; for ( int i = 1; i < argc; ++i ) { if ( i > 1 ) skrypt << ", "; skrypt << "\"" << argv[ i ] << ".dat\" with boxes"; } skrypt << endl; return 0; }

Zad. 40. // Program kopiuje maksymalnie zadanąliczbę znaków. // // Paweł Klimczewski, 26 listopada 2005 #include #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; } // 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; }

48

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

<sstream>

using namespace std; int n; int maxcnt;

// // // double eps = 1e-3; //

stopień wielomianu: z^n - 1 maksymalna liczba iteracji dla pojedynczego punktu 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 ) { 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;

49

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 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"

50

"newton.dat" 1 0.8

5

0.6

4

0.4

3

0.2

2

0

1

-0.2

0

-0.4 -0.6 -0.8 -1 -1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

Zad. 42. // Program rysuje zbiór Mandelbrota. // // Paweł Klimczewski, 27 listopada 2005. #include #include #include #include

<sstream>

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 ) {

51

// Ciąg jest rozbieżny. Kolor punktu będzie odpowiadał szybkości // rozbiegania. return 1 + i; } } return 0; } int main() { 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; }

52

"mandelbrot.dat" 1.5 100 1 80 60

0.5

40 0

20 0

-0.5

-1

-1.5 -2

-1.5

-1

-0.5

0

0.5

1

Zad. 43. #include #include #include #include #include



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. // 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 );

53

} 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. 44. #include #include <list> #include 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 ) { is_prime( i ); } return 0; }

54

Zad. 45. #include #include #include #include

<set>

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. 46. #include #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 ]. f[ n ] = fibonacci( n - 1 ) + fibonacci( n - 2 ); } return f[ n ]; }

55

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. 47. #include #include #include #include

<string>

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. vector< string >::iterator it; for ( it = v.begin(); it != v.end(); ++it ) { it->resize( mx, ’ ’ ); reverse( it->begin(), it->end() );

56

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

Zad. 48. #include #include #include #include

<sstream> <deque> <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. 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;

57

return 0; }

Zad. 49. #include #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. 50. #include #include <string> #include <set> using namespace std;

58

// 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. 51. #include #include #include #include #include #include #include

<list>

59

using namespace std; // Sprawdzam czy n-ta ksiązka ma taką samą liczbę sąsiadów z każdej strony. bool sprzyjajace( const vector& 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() ); // Przeglądam wszystkie permutacje. Jeżeli permutacja jest zdarzeniem // sprzyjającym zwiększam zmienną a. do

60

{ 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. 52. #include #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 ); } else { cout << "Błędne dane!" << endl;

61

} 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; }

Zad. 53. #include #include

62

#include #include #include 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; }

Zad. 54. #include #include <sstream>

63

#include #include #include #include

<map> <deque> <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 ) { double s = 0; map< deque< char >, int >::const_iterator iu = u.begin(), iv = v.begin();

64

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 ) ); if ( p.size() < n ) continue; st0[ p ]++; p.pop_front();

65

} 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; }

66