Darmowy fragment publikacji:
• Kup książkę
• Poleć książkę
• Oceń książkę
• Księgarnia internetowa
• Lubię to! » Nasza społeczność
Spis treści
Rozdział 1. Odkrywamy i stosujemy algorytmy
1.1. Wstęp
1.2. Struktura programu
1.3. Lista bibliotek używanych w przykładach
1.4. Najczęściej używane typy danych i przykłady deklaracji
1.5. Podstawowe konstrukcje algorytmiczne
1.5.1. Instrukcja warunkowa
1.5.2. Instrukcje iteracyjne
1.5.3. Operacje na łańcuchach
1.6. Przykłady programów wykorzystujących opisane konstrukcje
1.7. Algorytmy numeryczne i teorioliczbowe
1.7.1. Obliczanie pierwiastka kwadratowego — algorytm Newtona-Raphsona
1.7.2. Obliczanie miejsca zerowego funkcji metodą połowienia
przedziałów — metoda bisekcji
1.7.3. Obliczanie pola obszaru pod krzywą w zadanym przedziale
w układzie współrzędnych — całkowanie numeryczne
1.7.4. Rozszerzony algorytm Euklidesa
1.7.5. Arytmetyka modularna
1.7.6. Chińskie twierdzenie o resztach (jedno z najważniejszych
w teorii liczb i kryptografi i)
1.7.7. Potęgowanie modularne
1.8. Algorytmy rekurencyjne
1.8.1. Ciąg Fibonacciego
1.8.2. QuickSort
1.8.3. Problem Józefa Flawiusza
1.9. Struktury danych
1.9.1. Drzewa
1.9.2. Stos
1.9.3. Kolejka
1.9.4. Kopiec
1.10. Algorytmy grafowe
1.10.1. Reprezentacja grafu w pamięci komputera
1.10.2. Przeszukiwanie grafu
1.10.3. Przeszukiwanie wszerz BFS
7
7
8
9
9
10
10
12
13
14
21
22
23
23
25
28
30
32
36
39
40
41
42
43
49
51
52
54
55
58
59
Spis treści
3
Kup książkęPoleć książkę 1.10.4. Przeszukiwanie w głąb DFS
1.10.5. Cykl Eulera — przez każdą krawędź przechodzimy tylko raz
1.10.6. Cykl Hamiltona
1.11. Elementy teorii gier
1.11.1. Gra w życie
1.11.2. Gra logiczna NIM
1.11.3. Dodawanie nimliczb
1.11.4. Mnożenie nimliczb
1.11.5. Potęgowanie nimliczb
1.12. Sprawdź się — zadania na koniec rozdziału
Rozdział 2. Matematyka finansowa — arkusz kalkulacyjny
pomocnikiem młodego inwestora
2.1. Stopy procentowe
2.2. Kredyty, lokaty, depozyty, renty
2.3. Cash flow
2.4. Sprawdź się — zadania na koniec rozdziału
Rozdział 3. Linux
3.1. Pierwsze uruchomienie
3.2. Powłoki
3.3. Struktura systemu
3.4. Terminal
3.5. Połączenie z siecią bezprzewodową
3.5.1. Zapora sieciowa (firewall)
3.6. Podstawowe polecenia w trybie tekstowym
3.6.1. Składnia poleceń
3.6.2. Zarządzanie katalogami
3.6.3. Znaczenie znaków
3.7. Prawa dostępu
3.8. Zarządzanie użytkownikami i grupami
3.9. Procesy
3.9.1. Stany procesów
3.9.2. Polecenia służące do zarządzania procesami
3.10. Zarządzanie pakietami, źródłami, archiwami
4
Spis treści
63
64
66
68
68
71
73
73
74
75
85
85
87
95
97
100
101
103
104
105
107
108
111
112
112
114
114
117
121
121
121
123
Kup książkęPoleć książkę 3.11. Skrypty
3.11.1. Tworzenie skryptu
3.11.2. Uruchamianie skryptu
3.11.3. Instrukcje warunkowe i iteracyjne w skryptach
3.11.4. Wywoływanie skryptu z parametrami
3.12. Okna dialogowe
3.12.1. Składnia poleceń
3.13. Informacje sieciowe, komunikacja
3.13.1. Informacja o interfejsach sieciowych
3.13.2. Wyświetlenie aktywnych połączeń
3.13.3. Wyświetlenie bramy domyślnej
3.13.4. Komunikacja między użytkownikami
3.14. Serwer WWW
3.15. Tworzenie dysków startowych z pamięci USB
3.16. Instalacja Ubuntu obok Windowsa
3.16.1. Zmiana kolejności uruchamiania systemów
3.17. Sprawdź się — zadania na koniec rozdziału
Rozdział 4. Sieciowi eksperci
4.1. Budowa i działanie
4.1.1. Podział sieci
4.1.2. Topologie sieci
4.2. Modele sieciowe, standardy komunikacyjne
4.2.1. Model OSI (Open Systems Interconnection)
4.2.2. Model TCP/IP
4.2.3. Kapsułkowanie danych
4.2.4. Sposoby transmisji danych
4.3. Podstawowe urządzenia sieciowe
4.3.1. Karta sieciowa
4.3.2. Wtórnik (repeater)
4.3.3. Koncentrator (hub)
4.3.4. Most (bridge)
4.3.5. Przełącznik (switch)
4.3.6. Router
4.4. Media sieciowe
126
126
127
129
130
132
133
136
136
136
136
137
137
139
140
142
143
145
145
145
146
146
147
147
148
149
149
149
149
149
149
150
150
150
Spis treści
5
Kup książkęPoleć książkę 4.5. Podstawy adresowania hostów
4.5.1. Adresy fizyczne (sprzętowe)
4.5.2. Adresy logiczne
4.5.3. Adresowanie klasowe
4.5.4. Adresowanie bezklasowe
4.6. Przepustowość i przepływność pasma
4.7. Kontrola ruchu w sieci
4.7.1. Praktyczne polecenia
4.7.2. Geograficzne śledzenie tras i jakości łącza
4.7.3. Usługi i porty
4.7.4. Ochrona prywatności
4.8. Sprawdź się — zadania na koniec rozdziału
151
151
151
153
155
158
159
159
162
163
164
168
6
Spis treści
Kup książkęPoleć książkę W
s
k
a
z
ó
w
k
a
D
e
fi
n
i
c
j
a
4. Przechodzenie pre-order — zapisujemy wierzchołki odwiedzane po raz pierwszy:
K – P – W – G. Sumujemy krawędzie 105+313+321 i dodajemy wagę między K i G
— 250.
Dla niektórych grafów można znaleźć wiele drzew spełniających warunek drzewa mi-
nimalnego. Jeżeli myślisz, że to jeden z takich przypadków, masz rację J
Implementację tego algorytmu zostawiam najbardziej dociekliwym. Powodzenia!
1.11. Elementy teorii gier
Teoria gier to dział matematyki zajmujący się badaniem optymalnych zachowań
w przypadku sytuacji konfliktowych. Celem gracza w każdej grze jest oczywiście wy-
grana, która łączy się z osiągnięciem korzyści (zebranie skarbów, zdobycie władzy czy
po prostu przetrwanie, przeżycie). Teorie gier mają zastosowanie w wielu dziedzinach.
Ich zadaniem jest badanie strategii, jakie powinien przyjąć gracz, żeby osiągnąć jak
najlepszy wynik.
Przy opracowywaniu strategii zawsze należy brać pod uwagę:
• zbiór graczy,
• reguły,
• możliwe straty,
• możliwe wyniki,
• wypłaty (korzyści).
Zajmiemy się analizą popularnych problemów w teorii gier — grą w życie i grą logiczną NIM.
1.11.1. Gra w życie
W drugiej połowie XX wieku John Conway wymyślił grę, która zdobyła bardzo dużą popu-
larność. Gra jest modelem rodzenia się, ewolucji, śmierci kolonii organizmów. Rozgrywa się
w przestrzeni (dwuwymiarowa plansza podzielona na komórki) i czasie (kolejne pokolenia).
Grę rozpoczynamy od „zasiedlenia” komórek.
Zasady gry według Conwaya:
• Martwa komórka, która ma trzech sąsiadów, rodzi się.
• Żywa komórka pozostaje żywa, jeżeli ma dwóch lub trzech sąsiadów.
68
Rozdział 1. Odkrywamy i stosujemy algorytmy
Kup książkęPoleć książkę • Jeżeli żywa komórka ma mniej niż dwóch sąsiadów, umiera z samotności.
• Jeżeli żywa komórka ma więcej niż trzech sąsiadów, umiera z zatłoczenia.
Do komputerowej realizacji tego algorytmu wykorzystamy tablicę, która będzie symulować
kolonię żywych organizmów. Komórki niezamieszkałe zapełniamy literą „o”, pojawienie się
organizmu zaznaczamy literą „x”. Potrzebna nam jest druga plansza, która przechowuje stan
kolejnego pokolenia. Zawartości kolonii nie możemy zmieniać dynamicznie, bo przecież
procesy „rodzenia się” i „umierania” zachodzą w tym samym czasie.
Tworzymy dwie plansze o rozmiarze stosownym do symulacji, którą chcemy prze-
prowadzić. Wypełniamy je na początku „o” (oczyszczamy z intruzów J). Kontrolnie
możemy wyświetlić, że wszystko jest gotowe.
W
s
k
a
z
ó
w
k
a
char plansza[20][20];
char nowa_plansza [20][20];
int i,j,w,k,ilosc=0,pokolenie,p=0;
for( i=0;i 20;i++)
{ for ( j=0;j 20;j++)
{ plansza[i][j]= o ;
nowa_plansza [i][j]= o ;
cout plansza[i][j] ;
}
Następnie zasiedlamy kolonię, podając współrzędne wiersza (w) i kolumny (k), gdzie ma
„pojawić się życie”. Przy wyborze miejsc do zasiedlenia pamiętajmy, żeby w żadnym po-
koleniu nie przekroczyć zakresu tablicy. Zmienna ilość określa, ile mamy żywych organi-
zmów do zasiedlenia. Wyświetlimy sobie od razu schemat naszej kolonii.
cin ilosc;
for (int l=0; l ilosc; l++)
{cin w;
cin k;
plansza[w][k]= x ;
}
cout Kolonia: endl;
for( i=0;i 20;i++)
{ for (int j=0;j 20;j++)
cout plansza[i][j] ;
cout endl;
}
1.11. Elementy teorii gier
69
Kup książkęPoleć książkę W
s
k
a
z
ó
w
k
a
Pozostało nam napisanie fragmentu kodu, który zawiera zasady gry. Żeby nie „wy-
skoczyć” poza planszę, proponuję zacząć od indeksów równych 1 i skończyć na 15.
Oczywiście można uzupełnić program o funkcję informującą, czy w aktualnym roz-
miarze tablicy możliwy jest dalszy rozwój, do czego zachęcam.
Poniższy fragment kodu wykona symulację dla jednego pokolenia. Jeżeli chcemy sy-
mulacji dla n-tego, należy wywołać go n-krotnie.
for (i=1; i 15;i++)
for (j=1; j 15; j++)
//Zmienna zliczająca liczbę sąsiadów
{ilosc=0;
//Pojawia się nowe życie
if (plansza[i-1][j-1]== x ) ilosc++;
if (plansza[i-1][j]== x ) ilosc++;
if (plansza[i-1][j+1]== x ) ilosc++;
if (plansza[i][j-1]== x ) ilosc++;
if (plansza[i][j+1]== x ) ilosc++;
if (plansza[i+1][j-1]== x ) ilosc++;
if (plansza[i+1][j]== x ) ilosc++;
if (plansza[i+1][j+1]== x ) ilosc++;
if (ilosc==3) nowa_plansza[i][j]= x ;
//Nic się nie zmienia
if (ilosc==2) nowa_plansza[i][j]=plansza[i][j];
//Organizm umiera z zatłoczenia
if (ilosc 3) nowa_plansza[i][j]= o ;
//Organizm umiera z samotności
if (ilosc 2) nowa_plansza[i][j]= o ;
}
//Funkcja kopiująca struktury, w konkretnym przypadku tablicę
//„nowa_plansza” do „plansza” (kolejne pokolenie jest bazowym
//dla następnego). Trzecim argumentem jest funkcja określająca
//liczbę kopiowanych elementów
memcpy(plansza, nowa_plansza, sizeof(plansza));
Mamy już wszystkie fragmenty gry. Pozostaje połączyć je w całość. Powodzenia!
Zadanie 1.28 Wykorzystując napisany program, sprawdź, jak będzie wyglądać kolonia
bakterii w piątym pokoleniu dla struktur przedstawionych na rysunku 1.17.
70
Rozdział 1. Odkrywamy i stosujemy algorytmy
Kup książkęPoleć książkę Rysunek 1.17. Kolonie bakterii
Gra w życie jest przykładem automatu komórkowego. Automaty komórkowe stanowią już
właściwie odrębny dział nauki i znajdują wiele zastosowań. Czy potrafi sz wymienić przykłady?
1.11.2. Gra logiczna NiM
Czy znasz zabawę polegającą na zabieraniu przedmiotów (np. zapałek, kamieni) z kilku
stosów (rzędów), taką że na starcie każdy miał różną liczbę elementów? W myśl zasad gry,
wykonując ruch, gracz może zabrać dowolną liczbę elementów, ale tylko z jednej sterty. Ten,
kto zabiera ostatni element, wygrywa lub przegrywa, w zależności od przyjętej koncepcji.
Zaimplementowanie takiej gry do komputera wydaje się banalne. Przeanalizuj umiesz-
czony niżej przykład dla trzech rzędów po maksymalnie 10 elementów. Liczbę elementów
do każdego rzędu losuje komputer. Podczas wyświetlania elementy są symbolizowane zna-
kiem @. W implementacji zakładamy, że gracz potrafi liczyć i nie zabiera z rzędu więcej
elementów, niż się w nim znajduje J
Gra NIM dla dwóch graczy; wygrywa osoba, która weźmie ostatni
kamyczek
#include iostream
#include cstdlib
using namespace std;
void wyswietl(int i1,int i2,int i3)
{int i;
for ( i=1; i =i1; i++)
cout @ ;
cout endl;
for (i=1; i =i2; i++)
cout @ ;
cout endl;
for (i=1; i =i3; i++)
cout @ ;
cout endl;
}
1.11. Elementy teorii gier
71
Kup książkęPoleć książkę int main ()
{int rzad1[10],rzad2[10],rzad3[10];;
int rzad, ilosc;
int i,i1=0,i2=0,i3=0,gracz1,gracz2,numer=0;
srand(time(NULL));
for (i=0; i 10; i++)
{rzad1[i]=rand() 2;
if (rzad1[i]==1) i1++;
}
for (i=0; i 10; i++)
{rzad2[i]=rand() 2;
if (rzad2[i]==1) i2++;
}
for (i=0; i 10; i++)
{rzad3[i]=rand() 2;
if (rzad3[i]==1) i3++;
}
wyswietl(i1,i2,i3);
while ((i1+i2+i3) 0)
{numer++;
if (numer 2==0) cout Gracz 2 endl;
else cout Gracz 1 endl;
cout podaj numer wiersza i ile zabierasz endl;
cin rzad;
cin ilosc;
if (rzad==1) i1=i1-ilosc;
if (rzad==2) i2=i2-ilosc;
if (rzad==3) i3=i3-ilosc;
wyswietl(i1,i2,i3);
if (i1+i2+i3==0) cout Wygrana!! endl;
}
system( pause );
return 0;
}
Przeprowadź symulację (możesz oczywiście zmienić liczbę wierszy i kamyków) i zastanów
się nad zwycięską strategią. Czy potrafisz napisać program, w którym jednym z grających
jest komputer?
72
Rozdział 1. Odkrywamy i stosujemy algorytmy
Kup książkęPoleć książkę W klasycznej grze wygrywa ten, kto zabierze ostatni element. Strategią wygrywającą jest
ta, w której suma wartości elementów (dodawanie nimliczb) jest równa 0. Tylko... co to są
te nimliczby?
Nimliczby — liczby, które różnią się od liczb naturalnych sposobem wykonywania
działań.
1.11.3. Dodawanie nimliczb
• Suma dwóch równych nimliczb wynosi 0: 7⊕7 = 0.
• Jeżeli większa z nimliczb jest potęgą dwójki, dodaje się je jak zwykłe liczby: 8⊕7 = 15.
Dodawanie nimliczb odpowiada operacji XOR (w C++ operator ^) na cyfrach rozwinięcia
dwójkowego danej liczby.
Dodajmy dwie liczby:
37D = 100101B
51D = 110011B
Wynikiem operacji XOR jest prawda wtedy, gdy oba elementy są różne
(1 XOR 1 = FAŁSZ, 0 XOR 0 = FAŁSZ, 0 XOR 1 = PRAWDA, 1 XOR 2 = PRAWDA).
W
s
k
a
z
ó
w
k
a
W
s
k
a
z
ó
w
k
a
XOR
NIM — suma
100101B
110011B
010110B
37⊕51 = 22
Powyższe działanie w C++ zapisujemy tak:
wynik = 37 ^ 51;
37D
51D
22D
1.11.4. Mnożenie nimliczb
• Jeżeli większa z nimliczb jest równa elementowi ciągu 1, 2, 4, 16, 256, …, to mnożenie
• Jeżeli nimliczbę mnoży się przez siebie, to wynik jest równy sumie dwóch nimliczb —
odbywa się na zwykłych zasadach.
jej samej i części całkowitej jej połowy: 9⊙9 = 9⊕9/2 = 9⊕4 = 13.
1.11. Elementy teorii gier
73
Kup książkęPoleć książkę 1.11.5. Potęgowanie nimliczb
• Potęgowanie odbywa się na standardowych zasadach — poprzez wielokrotne mnoże-
nie nimliczb, czyli:
x3 = x*x*x.
Zadanie 1.29 Napisz program — kalkulator wykonujący operacje dodawania, mnożenia
i potęgowania nimliczb. Korzystanie z niego podczas gry w NIM ułatwi wygrywanie J
Powróćmy do strategii wygrywającej. Mamy trzy rzędy elementów.
FTP
Ilość w systemie
Ilość w systemie
Elementy
binarnym
dziesiętnym
I I I I I
I I I I I I I
I I I
Numer rzędu
1
2
3
NIM suma (operacja XOR)
Żeby NIM suma była równa 0, wystarczy z dowolnego rzędu zabrać jeden element. Znaj-
dziemy się wtedy na pozycji wygrywającej.
Istnieje ryzyko, że liczba elementów do zabrania przekracza liczbę elementów w najwięk-
szym stosie. Jak w tym przykładzie.
5
7
3
5^7^3 = 1
101
111
011
001
Ilość w systemie
Ilość w systemie
Elementy
binarnym
dziesiętnym
I I I I I I I I I
I I I I I I I
I I I
9
7
3
9^7^3 = 13
Numer rzędu
1
2
3
NIM suma (operacja XOR)
W takiej sytuacji należy od otrzymanej liczby odjąć liczbę elementów w największym sto-
sie i zostawić na nim liczbę elementów równą otrzymanej różnicy:
13–9 = 4
Zabieramy 9–4 = 5
1001
0111
0011
1101
Numer rzędu
Elementy
Ilość w systemie
Ilość w systemie
dziesiętnym
binarnym
I I I I
1
I I I I I I I
2
3
I I I
NIM suma (operacja XOR)
Zadanie 1.30 Napisz program pt. „Gra NIM” dla trzech stosów po 10 elementów. Jed-
nym z grających jest komputer.
4
7
3
4^7^3 = 0
100
111
011
000
FTP
FTP
74
Rozdział 1. Odkrywamy i stosujemy algorytmy
Kup książkęPoleć książkę Zadanie 1.31 Zmień w swoim programie warunek wygranej — ten, kto zabiera ostatni
element, przegrywa.
1.12. Sprawdź się — zadania na koniec rozdziału
p
Zadanie 1.32 Każdy ułamek zwykły postaci q
względnie pierwszymi) można przedstawić w postaci ułamka łańcuchowego:
(gdzie p i q są liczbami całkowitymi,
FTP
1
1
a
0
+
p
q
=
a
1
+
a
2
1
...
++
1
na
Napisz program, który dla podanego p (licznika) i q (mianownika) wypisuje ciąg liczb a0,
a1, ..., an.
Dane wejściowe:
Liczby naturalne p i q oznaczające odpowiednio licznik i mianownik.
Wyjście:
Ciąg ułamków postaci a/b.
Przykładowy rezultat:
Dla danych wejściowych:
9 11
Wynik:
1 4 2
Funkcję najlepiej zdefi niować rekurencyjnie. Algorytm sprowadza się do „odwracania
ułamka” i wyłączania całości, dopóki licznik nie osiągnie wartości 1.
W
s
k
a
z
ó
w
k
a
FTP
Zadanie 1.33 Silnię podwójną oznacza się jako n!! Jest to iloczyn kolejnych liczb natu-
ralnych do n z krokiem 2.
1.12. Sprawdź się — zadania na koniec rozdziału
75
Kup książkęPoleć książkę
Pobierz darmowy fragment (pdf)
