wtorek, 25 marca 2014
Spotkanie 43. Anagramy w tekstach
poniedziałek, 24 marca 2014
Spotkanie 42. Przybliżona wartość miejsca zerowego - metoda połowienia przedziałów.
1. Miejsce zerowe.
To argument x, dla którego funkcja przyjmuje wartość zero f(0)=0.
Naszym zadaniem jest znalezienie przybliżonej wartości miejsca zerowego, czyli punktu przecięcia wykresyu z osią Ox. Będziemy posługiwali się metodą "dziel i zwyciężaj".
Jednak aby algorytm działał poprawnie muszą być spełnione warunki:
To argument x, dla którego funkcja przyjmuje wartość zero f(0)=0.
Naszym zadaniem jest znalezienie przybliżonej wartości miejsca zerowego, czyli punktu przecięcia wykresyu z osią Ox. Będziemy posługiwali się metodą "dziel i zwyciężaj".
Jednak aby algorytm działał poprawnie muszą być spełnione warunki:
- funkja f(x), której wykres jest linią ciągła w przedziale [p,q];
- wartość funkcji w punktach p i q są przeciwnych znaków, czyli spełniają warunki f(p) * f(q) < 0;
środa, 19 marca 2014
Spotkanei 41. Obliczanie pola obszaru ograniczonego wykresem funkcji.
Metoda całkowanie numerycznego - zajmuje się obliczaniem pola obszaru ograniczonego wykresem funkcji.
Wyróżniamy metody:
Wyróżniamy metody:
- prostokątów;
- trapezów;
wtorek, 18 marca 2014
piątek, 14 marca 2014
Spotkanie 39. Sortowanie przez scalanie. Sortowanie szybkie.
1. Sortowanie przez scalanie.
Metoda sortowania przez scalanie zaliczana jest do algorytmów wykorzystujących porównania. Jednocześnie jednak jest to metoda wykorzystująca ‘’dziel i zwyciężaj’ .
W tej metodzie wyróżniamy 2 etapy:
Wynika stąd, że głównym celem jest tutaj scalenie dwóch uporządkowanych ciągów w jeden posortowany.
2. Sortowanie szybkie.
Metoda sortowania szybkiego jest oparta na następującej własności: jeśli w tablicy T [0…n-1] istnieje element o indeksie k taki, że wszystkie elementy o mniejszych numerach mają wartość mniejszą od T [k], to aby uzyskać posortowany ciąg, wystarczy osobno posortować elementy tablicy T[0…k-1] i T[k+1…n-1].
W każdym kolejnym kroku powtarzane są te same czynności, zmienia się tylko fragment ciągu, na którym wykonujemy określone operacje. Indeks pierwszego wyrazu oznaczamy jako lewy, ostatniego – prawy.
Realizacje każdego kroku algorytmu należy rozpocząć od wybrania wyrazu ŚRODKOWEGO , którego wartość wyznaczamy : srodek – T [(lewy+prawy/2].Znajdowanie wyrazów w ciągu do zmiany rozpoczynamy od wyrazów skrajnych : LEWY i PRAWY, a dalej przesuwamy się w stronę wyrazu środkowego SRODEK. Szukamy z lewej strony elementu T [i] mniejsze/równe srodek, a z prawej elementu T[j] większy/równy srodek. Po znalezieniu pary spełniającej podane warunki wykonujemy zamianę elementów T[i] z T[j]. Czynności te powtarzamy tak długo, aż indeksy I i J się spotkają, dochodząc z obsu stron do elementu srodek.
Metoda sortowania przez scalanie zaliczana jest do algorytmów wykorzystujących porównania. Jednocześnie jednak jest to metoda wykorzystująca ‘’dziel i zwyciężaj’ .
W tej metodzie wyróżniamy 2 etapy:
- Podział - faza wykonywana jest rekurencyjnie , polega na podzieleniu ciągu na podciągi zawierające jedną wartość
- Scalanie - realizowana jest podczas łączenia podciągów i polega na scalaniu ich, z jednoczesnym sortowaniem
2. Sortowanie szybkie.
Metoda sortowania szybkiego jest oparta na następującej własności: jeśli w tablicy T [0…n-1] istnieje element o indeksie k taki, że wszystkie elementy o mniejszych numerach mają wartość mniejszą od T [k], to aby uzyskać posortowany ciąg, wystarczy osobno posortować elementy tablicy T[0…k-1] i T[k+1…n-1].
W każdym kolejnym kroku powtarzane są te same czynności, zmienia się tylko fragment ciągu, na którym wykonujemy określone operacje. Indeks pierwszego wyrazu oznaczamy jako lewy, ostatniego – prawy.
Realizacje każdego kroku algorytmu należy rozpocząć od wybrania wyrazu ŚRODKOWEGO , którego wartość wyznaczamy : srodek – T [(lewy+prawy/2].Znajdowanie wyrazów w ciągu do zmiany rozpoczynamy od wyrazów skrajnych : LEWY i PRAWY, a dalej przesuwamy się w stronę wyrazu środkowego SRODEK. Szukamy z lewej strony elementu T [i] mniejsze/równe srodek, a z prawej elementu T[j] większy/równy srodek. Po znalezieniu pary spełniającej podane warunki wykonujemy zamianę elementów T[i] z T[j]. Czynności te powtarzamy tak długo, aż indeksy I i J się spotkają, dochodząc z obsu stron do elementu srodek.
poniedziałek, 10 marca 2014
Spotkanie 38. Sortowanie ciągów liczbowych.
Sortowanie - jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.
Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwienia stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.
Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego.
Wyróżniamy:
Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwienia stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.
Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego.
Wyróżniamy:
- sortowanie bąbelkowe;
- sortowanie przez wybieranie;
- sortowanie przez zliczanie;
- sortowanie przez wstawianie;
- sortowanie kubełkowe;
czwartek, 6 marca 2014
Spotkanie 37. Monotoniczność ciągu liczbowego.
1. Monotoniczność.
Ciągi: malejące, rosnące, nierosnące, niemalejące noszą wspólną nazwę ciągów monotonicznych . Przyjęto również nazywać ciągi malejące lub rosnące ściśle monotonicznymi, ciągi zaś niemalejące lub nierosnące - monotonicznymi w szerszym sensie.
Aby zbadać monotoniczność ciągu o danym wyrazie ogólnym, należy zbadać znak różnicy an+1 - an.
Jeśli jest ona dodatnia wtedy ciąg jest rosnący, jeśli ujemna ciąg jest malejący, a jeśli równa 0, to ciąg jest stały.
an= n^2: 1, 4, 9, 16, 25, ... - ciąg rosnący
an= 3 - n: 2, 1, 0, -1, -2, ... - ciąg malejący
2. C++
Ciągi: malejące, rosnące, nierosnące, niemalejące noszą wspólną nazwę ciągów monotonicznych . Przyjęto również nazywać ciągi malejące lub rosnące ściśle monotonicznymi, ciągi zaś niemalejące lub nierosnące - monotonicznymi w szerszym sensie.
Aby zbadać monotoniczność ciągu o danym wyrazie ogólnym, należy zbadać znak różnicy an+1 - an.
Jeśli jest ona dodatnia wtedy ciąg jest rosnący, jeśli ujemna ciąg jest malejący, a jeśli równa 0, to ciąg jest stały.
an= n^2: 1, 4, 9, 16, 25, ... - ciąg rosnący
an= 3 - n: 2, 1, 0, -1, -2, ... - ciąg malejący
2. C++
Spotkanie 36. Lider w zbiorze.
1. Lider.
Lider to taka wartość w zbiorze elementów, która powtarza się więcej niż razy. Jeśli istnieje taka wartość, to jest ona tylko jedna.
2. Przykłady:
Lider to taka wartość w zbiorze elementów, która powtarza się więcej niż razy. Jeśli istnieje taka wartość, to jest ona tylko jedna.
2. Przykłady:
- 8,8,1,4,3,8,8,9,0,88 - w tym ciągu liczba 8 jest liderem, bo na 11 elementów tego zbioru, aż sześć elementów przypada liczbie osiem
- Czy Chińczycy są liderem w liczbie ludności na Ziemi? - NIE, bo na 7 miliardów ludzi, Chińczycy stanowią zaledwie 2/7 ludności ziemskiej
Spotkanie 35. Maksymalny i minimalny element.
Omawiamy algorytm optymalnie wyszukuje ze zbioru liczb jednocześnie wartość najmniejszą i największą wykonując minimalną liczbę porównań. Metoda ta zaliczana jest do technik programistycznych typu "dziel i zwyciężaj".
Zasada algorytmu jest bardzo prosta. Do badania bierzemy jednorazowo po dwie liczby, porównujemy je ze sobą i większą z nich przydzielamy do zbioru potencjalnych maksimów, a mniejszą lub równą do potencjalnych minimów. W ten sposób otrzymaliśmy dwa zbioru, gdzie w pierwszym występuje wartość, która jest maksymalna oraz w drugim wartość, która jest minimalna. Aby znaleźć teraz maksimum i minimum wykorzystujemy klasyczne przeszukiwanie liniowe dla tych dwóch podzbiorów. Szukanie to można wykonywać już podczas wczytywania danych nie wykorzystując tablic.
Zasada algorytmu jest bardzo prosta. Do badania bierzemy jednorazowo po dwie liczby, porównujemy je ze sobą i większą z nich przydzielamy do zbioru potencjalnych maksimów, a mniejszą lub równą do potencjalnych minimów. W ten sposób otrzymaliśmy dwa zbioru, gdzie w pierwszym występuje wartość, która jest maksymalna oraz w drugim wartość, która jest minimalna. Aby znaleźć teraz maksimum i minimum wykorzystujemy klasyczne przeszukiwanie liniowe dla tych dwóch podzbiorów. Szukanie to można wykonywać już podczas wczytywania danych nie wykorzystując tablic.
Spotkanie 34. Liniowe przeszukiwanie ciągu liczbowego z wartownikiem.
1. "Wartownik".
"Wartownik" - to taka wartość, którą ustawiamy na końcu zbioru. Cechuje się ona tym, że nie występuje w badanym ciągu. Jeśli na nią natrafimy to mamy pewność, że przeszukaliśmy już cały zbiór i szukana wartość nie istnieje.
2. Przykład.
W naszym przykładzie zakładamy, że zbiór składa się z liczb naturalnych. Ilość liczb jest mniejsza od 1000 Jako wartownik posłuży nam liczba -1 (nie jest to liczba naturalna i nie wystąpi wcześniej).
Prześledźmy przykład:
9, 0, 8, 2, 1, 6, -1
Załóżmy, że chcemy wyszukać liczbę 2. Jak widać znajduje się ona na 4 pozycji i ta liczba powinna znaleźć się na wyjściu.
Gdy spróbujemy wyszukać liczbę 7, algorytm zatrzyma się na wartości wartownika. Na wyjściu powinien pojawić się stosowny komunikat.
"Wartownik" - to taka wartość, którą ustawiamy na końcu zbioru. Cechuje się ona tym, że nie występuje w badanym ciągu. Jeśli na nią natrafimy to mamy pewność, że przeszukaliśmy już cały zbiór i szukana wartość nie istnieje.
2. Przykład.
W naszym przykładzie zakładamy, że zbiór składa się z liczb naturalnych. Ilość liczb jest mniejsza od 1000 Jako wartownik posłuży nam liczba -1 (nie jest to liczba naturalna i nie wystąpi wcześniej).
Prześledźmy przykład:
9, 0, 8, 2, 1, 6, -1
Załóżmy, że chcemy wyszukać liczbę 2. Jak widać znajduje się ona na 4 pozycji i ta liczba powinna znaleźć się na wyjściu.
Gdy spróbujemy wyszukać liczbę 7, algorytm zatrzyma się na wartości wartownika. Na wyjściu powinien pojawić się stosowny komunikat.
Spotkanie 33. Przeszukiwanie ciągu liczbowego.
1. Przeszukiwanie liniowe.
Przeszukiwanie liniowe ( lub wyszukiwanie sekwencyjne) - najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.
Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych – wynosi od 1 do ^n, gdzie n to całkowita liczba elementów.
Dla dużej liczby danych algorytm jest bardzo nieefektywny, jednak gdy danych jest względnie mało, jest z powodzeniem stosowany (np. w tablicach mieszających, w których problem kolizji rozwiązuje się metodą łańcuchową).
Przeszukiwanie liniowe ( lub wyszukiwanie sekwencyjne) - najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście. Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.
Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych – wynosi od 1 do ^n, gdzie n to całkowita liczba elementów.
Wyszukiwanie liniowe może być jedynym sposobem wyszukiwania, gdy nie wiadomo niczego na temat kolejności kluczy.
Dla dużej liczby danych algorytm jest bardzo nieefektywny, jednak gdy danych jest względnie mało, jest z powodzeniem stosowany (np. w tablicach mieszających, w których problem kolizji rozwiązuje się metodą łańcuchową).
Spotkanie 32. Generowanie liczb pierwszych. Sprawdznie czy dana liczba jest liczbą pierwszą.
1. Liczby pierwsze.
.Liczby pierwsze to liczby naturalne, które posiadają dokładnie dwa dzielniki (liczbę 1 i samą siebie).
Nasuwa się pytanie, czy liczba naturalna jest pierwsza, czy też nie jest liczbą pierwszą. Jeśli liczba naturalna większa od 1 nie jest pierwszą, to jest iloczynem dwóch liczb naturalnych od niej mniejszych. Liczby takie nazywamy liczbami złożonymi.
.Liczby pierwsze to liczby naturalne, które posiadają dokładnie dwa dzielniki (liczbę 1 i samą siebie).
2. Sito Eratostenesa.
Sito Eratostenesa - przypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału.
Spotkanie 30. Systemy liczbowe - kod U2.
1. Ważne pojęcia.
system liczbowy - zbiór reguł jednolitego zapisu i nazewnictwa liczb.
Do zapisywania liczb używa się skończonego zbioru znaków, zwanych cyframi, które można łączyć w dowolnie długie ciągi, otrzymując nieskończoną liczbę kombinacji.
2. Przykłady.
system liczbowy - zbiór reguł jednolitego zapisu i nazewnictwa liczb.
Do zapisywania liczb używa się skończonego zbioru znaków, zwanych cyframi, które można łączyć w dowolnie długie ciągi, otrzymując nieskończoną liczbę kombinacji.
2. Przykłady.
- Dwójkowy system liczbowy, system binarny, bin – pozycyjny system liczbowy, w którym podstawą jest liczba 2. Do zapisu liczb potrzebne są tylko dwie cyfry: 0 i 1
- Czwórkowy
- Ósemkowy
- Szesnastkowy
Konwersja ujemna liczb dziesiętnych na zapis U2.
Jeśli do liczby 2^n (n - ilość bitów w formacie U2) dodamy przetwarzana liczbę dziesiętną, to zapisany dwójkowo wynik będzie równoważny bitowo (tzn. o takiej samej postaci) kodowi U2 przetwarzanej liczby.
Przykład:
Wyznacz 8-mio bitowy kod U2 dla liczby dziesiętnej -45(10)
2^8+(-45)=256-45=211=11010011(2)
Stąd (-45)(10) = 11010011(U2)
Subskrybuj:
Posty (Atom)